Motivation
Many algorithms in number theory and cryptography need large primes. For example, they may need an integer with several hundred or several thousand binary digits that is prime. The most direct primality test is trial division: try every possible divisor up to . Its cost is roughly proportional to , and the size of the input is the number of bits of , about . So trial division takes time exponential in the input length. For a 1024-bit number, is about , and no computation of that size is feasible.
Fermat's little theorem gives a fast necessary condition. If is prime and , then . This can be checked with modular exponentiation in time polynomial in . The condition is not sufficient, however, and some composite numbers satisfy it for every base coprime to them. This note studies a strengthening of Fermat's condition, the strong probable-prime condition, and the randomized test built on it, the Miller–Rabin test.
The strengthening uses a fact about primes that Fermat's test ignores. Modulo a prime, the only square roots of are and . The Miller–Rabin test does not stop at . It examines the chain of repeated square roots leading up to and checks that this chain behaves the way it must behave modulo a prime.
This chapter proves prime inputs always pass. The companion chapter proves the composite error bound:
- If is prime, every base in passes.
- If is an odd composite, at most half of the bases in pass.
Together with independent random choice of bases, these results give a test with a clean guarantee. A composite verdict is always correct. For any fixed composite input, a probable-prime verdict after rounds occurs with probability less than . We will also be careful about what this guarantee does not say.
Throughout, we assume you are comfortable with the Chinese Remainder Theorem (CRT), Fermat's little theorem, square-and-multiply exponentiation, group homomorphisms and Lagrange's theorem, and elementary divisibility by prime powers.
From Fermat's test to square roots of one
Fermat liars
Definition 8.1.1
(Fermat liar)
Let be odd. Call an integer with a Fermat liar for if is composite and still . Fermat liars are the bases for which Fermat's test gives the wrong impression.
Worked example 8.1.2
(Why every unit fools Fermat at )
Some composite numbers have only Fermat liars among their units. A standard example is . We can check it directly. Let . Then:
- modulo : , and , so ;
- modulo : , and , so ;
- modulo : , and (since ), so .
By CRT, for every unit . A composite number with this property is called a Carmichael number. For such , Fermat's test can only detect compositeness by hitting a base that shares a factor with . The probability of hitting a nonunit is at most , where the sum runs over distinct prime divisors; the number of factors matters.
So we need more information from the base than the single value .
Square roots of one
The extra information comes from the following lemma.
Lemma 8.1.3
(Square roots of modulo a prime)
Let be an odd prime and let be an integer with . Then or .
Proof
(Factor the difference of squares)
We have . Since is prime, or .
The proof uses exactly one property of : if a prime divides a product, it divides one of the factors. For a composite modulus this property fails. Failure of the lemma then exposes a factor of .
Lemma 8.1.4
(A nontrivial square root of reveals a factor)
Let and suppose but . Then and are both proper divisors of , that is, both lie strictly between and .
Proof
(Neither gcd can be trivial)
Since and , we have . If , then forces , which contradicts . Hence . The same argument with the roles of and exchanged gives .
We call such an a nontrivial square root of modulo . Modulo a prime there are none, by the lemma on square roots of modulo a prime. Modulo an odd composite with at least two distinct prime factors there always are some, as the exercise on square roots of one below shows.
Definitions
Let be odd. Then is even, so we can write uniquely
Definition 8.1.5
(Strong sequence and stage)
For an integer , the strong sequence of modulo is
Each term is the square of the previous one: . The last term is the Fermat value, . We refer to the index as the stage.
If is prime and , the sequence ends at . Consider the first stage at which the value appears. Either it appears at stage , or the previous value squared to without being , so by the lemma on square roots of modulo a prime the previous value is . This motivates the definition.
Definition 8.1.6
(Strong probable prime, strong liar and strong witness)
Let be odd with , odd. A base is said to make a strong probable prime to base if and
In this case we also say that passes. If is composite and passes, is a strong liar for . If does not pass, is a strong witness for the compositeness of .
Three features of this definition deserve comment.
Which stages are inspected. At stage we accept either value or . At stages we accept only the value . A value at a stage does not by itself justify acceptance, because what matters is how the value was reached. If appears for the first time at stage and the round has not already stopped, the previous value is neither nor . It is therefore a nontrivial square root of , and is composite. If appeared earlier, the round has already stopped, either by accepting or rejecting.
Stage is never an accepting stage. The value at stage means . This is incompatible with Fermat's theorem for a prime , since when . So the definition stops at .
The condition depends on only modulo . We therefore regard bases as residues and draw them from . The residue is excluded because it is never coprime to .
The bases and always pass: , and because is odd. They are passing bases that carry no information. The companion chapter proves an error bound despite these bases.
Quick check
(Show that the base passes for , so that is a strong liar for .)
Note that .
Solution · Answer
Here , so and . Since , we get . Thus , and passes at stage although is composite.
The algorithm
Pseudocode
The test takes an integer and a number of rounds . It returns one of three verdicts.
- PRIME is returned only for , and it is certain.
- COMPOSITE is always correct.
- PROBABLE-PRIME is the verdict whose reliability we must analyze.
MILLER-RABIN(n, k): # n ≥ 2, k ≥ 1
1 if n = 2: return PRIME
2 if n is even: return COMPOSITE # n ≥ 4 even, so 2 is a proper divisor
3 d ← n − 1; s ← 0
4 while d is even:
5 d ← d / 2; s ← s + 1
# now n − 1 = 2^s · d with d odd and s ≥ 1
6 repeat k times:
7 draw a uniformly at random from 1, 2, ..., n − 1,
independently of all previous draws
8 if STRONG-ROUND(n, s, d, a) = FAIL: return COMPOSITE
9 return PROBABLE-PRIME
STRONG-ROUND(n, s, d, a):
1 if gcd(a, n) > 1: return FAIL # gcd(a, n) is a proper divisor of n
2 x ← a^d mod n # square-and-multiply; this is x_0
3 if x = 1 or x = n − 1: return PASS # stage 0
4 for r ← 1 to s − 1:
5 y ← x^2 mod n # y = x_r
6 if y = n − 1: return PASS # stage r
7 if y = 1: return FAIL # x is a square root of 1 other than ±1
8 x ← y
9 return FAIL
Some details are worth spelling out.
- The cases and even . The decomposition with needs odd. For even the number is odd, so and the strong condition has no stages at which could be accepted. The definition was not designed for this case. We handle it directly: is prime, and every even is composite because is a proper divisor.
- The case . Here , so and . The loop in lines 4–8 of the round runs for from to , so it does not run at all. The bases are and , and both pass at stage . This is correct, since is prime.
- Drawing a base. One way to draw uniformly from is rejection sampling. Draw fresh random bits, where is the bit length of . Interpret them as an integer with . Accept if , and otherwise draw again. As odd implies , each attempt succeeds with probability at least , and the expected number of attempts is at most . What matters for the analysis is that the base is exactly uniform on and that each round uses new random bits.
- The gcd step. Line 1 of the round is not needed for correctness, because a non-coprime base can never have a power congruent to or modulo . It is included because, when it fires, it produces an explicit factor of cheaply. It is not what makes the test strong. The chance of a nonunit is bounded by over distinct prime divisors. If this sum is small, detecting compositeness mainly depends on the strong condition.
The round computes exactly the strong condition
Line 7 of the round stops early, so we should check that the round decides precisely the strong condition.
Lemma 8.1.7
(The round decides the strong condition)
Let be odd, with odd, and . Then STRONG-ROUND returns PASS if and only if is a strong probable-prime base for .
Proof
(A loop invariant on the inspected stages)
If , the round returns FAIL and the definition also fails. So assume .
Line 2 sets . If , both the round and the definition accept.
Otherwise we prove the following loop invariant: at the start of iteration , the variable holds , and none of is congruent to or . This holds at by the previous paragraph. During iteration , the variable becomes , and there are three cases.
- If , the round returns PASS, and the definition accepts at stage .
- If , the round returns FAIL. We check that the definition also rejects. We know and . Since , every later term satisfies for , and because . So no term at stages equals , and the definition rejects.
- Otherwise . The round sets , and the invariant holds for .
If the loop finishes, the invariant shows that are all different from , so the definition rejects. The round also rejects, at line 9.
Reading a failing round
A FAIL is not just a negative verdict. It always comes with evidence that is composite, of one of three kinds.
- A common factor. The gcd step fires, and satisfies . So is a proper divisor of .
- A nontrivial square root of . Line 7 fires. Then satisfies and . By the lemma on nontrivial square roots, is a proper divisor.
- Exhaustion at line 9. We know . Consider the term the round never computes, . Either , in which case is a Fermat witness and is composite by Fermat's theorem. Or , in which case is a nontrivial square root of .
In cases 1 and 2, and in case 3 when , we even obtain a proper factor of . When , the loop is empty, and every FAIL with a coprime base is of type 3, decided entirely by the value .
Anyone can recheck any of these certificates using a single modular exponentiation or gcd. Thus the COMPOSITE verdict is not merely probable. It is proved, and the proof is the failing base.
Quick check
(Run the strong round for and . Which kind of failure occurs, and which factors of does it reveal?)
Write and compute first.
Solution · Answer
Here , and . Since , we get , which is neither nor . In iteration , , so line 7 returns FAIL. This is a failure of type 2: is a square root of other than , and , .
Two ways to interpret an exhausted round
The two possibilities within failure type 3 above become concrete if we follow the variables in two short rounds. In each case the gcd is , so rejection comes from the strong condition rather than from finding a common factor at the start.
Worked example 8.1.8
(Exhausting the round: , base )
Write , so and . Since , line 2 gives . This is neither nor , so line 3 does not accept. At we compute ; this is neither nor , so the loop continues with . At we obtain , again neither nor . There are no more inspected stages, so line 9 returns FAIL.
For interpretation, compute the additional value . This last square is not performed by the round. It shows that , so the base is already a Fermat witness. No nontrivial square root of appeared along this trace: the round rejected because it exhausted the permitted stages, not because line 7 detected such a root.
Worked example 8.1.9
(An empty loop still detects a Fermat liar: , base )
Here , so and . The base is a unit because . Since ,
The initial value is neither nor . The loop would run from to , so it performs no iterations and line 9 returns FAIL. Nevertheless, the Fermat value is . Thus a final value of is insufficient for the strong condition: its predecessor is a nontrivial square root of . The lemma on nontrivial square roots makes the certificate explicit:
This is the second possibility within failure type 3. Although line 7 never runs, the value already held in supplies the root and hence a factorization. By comparison, the base passes immediately because ; that one passing base does not prove that is prime.
Theorem/proposition
Theorem 8.1.10
(Primes always pass)
Let be an odd prime and . Then passes. Consequently, MILLER-RABIN returns PROBABLE-PRIME for every odd prime and every outcome of the random draws. It returns PRIME for .
Proof
(Look at the first stage that reaches )
Since and is prime, . By Fermat's little theorem, . So the set of stages with is nonempty. Let be its least element.
- If , then , and passes.
- If , then and by minimality. By the lemma on square roots of modulo a prime, . The stage lies between and , so passes.
Since the round decides the strong condition, every round returns PASS, so the algorithm reaches line 9 and returns PROBABLE-PRIME. The case is handled at line 1.
Proof X-ray
What each ingredient does in the proof that primes pass
The proof uses three facts, each exactly once. Fermat's little theorem guarantees that the value occurs in the strong sequence, at the latest at stage ; it needs , which for prime follows from . Without that occurrence the least stage would not exist.
The key move is to take least. Minimality supplies a predecessor that squares to without being . Primality enters only here, through the lemma on square roots of , which forces that predecessor to be . Since , the accepting stage lies in , which is why stage never needs to be inspected.
For a composite modulus the argument breaks at exactly that lemma. For and , the first occurs at , but its predecessor is a square root of other than ; the base fails although . The proof uses neither the gcd step nor the random draws: the statement concerns every base.
The test therefore has one-sided error. It never calls a prime composite. Every possible mistake is a composite number reported as a probable prime. The companion chapter proves how often that can happen.
Common mistakes
Counterexample mode
Fermat liars of a Carmichael number need not be strong liars
A plausible claim is that the strong test only reorganizes the computation of , so that for a Carmichael number every unit, being a Fermat liar, is also a strong liar. Take , so and , and the base . Squaring repeatedly gives
Indeed . So is a Fermat liar, but none of the inspected values is or , and the round fails at line 9. This is failure type 3 with : the value is a nontrivial square root of , and , . The correct statement is that the strong condition is strictly stronger than Fermat's: it examines the path to , not only its endpoint.
Common mistake
(Quoting the error bound for fixed bases)
The bound below needs bases drawn independently and uniformly for the given input. A fixed list of bases carries no such guarantee for a particular composite. For the base passes, as the quick check above shows, so repeating the base any number of times returns PROBABLE-PRIME every time. A different base can still expose : , which is neither nor , and since the round with base fails.
Exercises
Quick check
(Square roots of one and the two kinds of failure: Let be odd, .)
(a) Show that if with an odd prime and , the only solutions of are .
(b) Show that if has exactly distinct prime factors, then has exactly solutions modulo . Conclude that nontrivial square roots of exist if and only if .
(c) Show that if is an odd prime power and a coprime base fails the strong round, then is a Fermat witness: . Check this for , .
(d) Show that if is a nontrivial square root of modulo an odd composite , then is a Fermat liar but a strong witness. Identify the failure type, as classified in “Reading a failing round”.
Solution
(a) Suppose . If divided both factors, it would divide their difference , which is impossible for odd . So divides only one factor, and then the whole power must divide that factor. Hence or , and these are distinct since .
(b) Write . By CRT, if and only if for each . By (a), each component has exactly solutions, and CRT gives a bijection between solution tuples and solutions modulo . So there are solutions. Since are two of them, nontrivial ones exist if and only if , that is, .
(c) By the classification of failing rounds, a coprime base that fails either has or produces a nontrivial square root of modulo . For , part (a) rules out the second possibility. For and , the strong sequence is and then , so is a Fermat witness.
(d) Since and is even, , so is a Fermat liar. Since is odd, , which is not . So does not pass at stage . Then , so for all , and never appears.
- If , the round fails at line 7 in iteration . This is type 2, with certificate itself.
- If , the round fails at line 9. This is type 3 with , so is again the nontrivial root.
The bases and for , and and for , are instances.