Motivation
The companion chapter defines the strong sequence, gives the algorithm and proves prime inputs always pass. We now run that algorithm on concrete inputs and examine the cost of implementing it.
Theorem/proposition
Theorem 8.2.1
(Correctness of each round)
For an odd prime every eligible base passes; for any odd input a failing round certifies compositeness. The companion chapter proves both assertions.
Theorem 8.2.2
(Computational cost)
With schoolbook multiplication and division, one strong round on a -bit input takes bit operations, plus an expected random bits to choose a uniform base. The operation count below proves the bound.
Worked examples
In the traces below, "stage values" are the residues in . The value appears as .
A blank later stage in a trace table means that the round has already stopped, not that the corresponding power is undefined. If a base is rejected at the gcd check, no modular exponentiation is performed; if it passes at some stage, the later squares are not computed. By contrast, the extra final terms listed to compare the strong test with Fermat's test are supplementary computations for teaching, and must be kept separate from the steps the pseudocode actually executes. This distinction also matters for the cost analysis: below we bound what a round may use, and a round that stops early can perform far fewer operations.
Worked example 8.2.3
(Trace for )
We have , so and . The round inspects for and , for . The column is not computed by the round. It is listed to interpret failures.
| base | verdict | |||||
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | pass (stage 0) | |||
| 2 | 1 | 2 | 4 | 7 | 4 | fail |
| 3 | 3 | fail (gcd) | ||||
| 4 | 1 | 4 | 7 | 4 | 7 | fail |
| 5 | 1 | 5 | 7 | 4 | 7 | fail |
| 6 | 3 | fail (gcd) | ||||
| 7 | 1 | 7 | 4 | 7 | 4 | fail |
| 8 | 1 | 8 | pass (stage 0) |
For example, for : , , .
Each coprime failing base ends with , so each is a Fermat witness. This is no accident. Modulo the only square roots of are (the exercise on square roots of one in the companion chapter), so failures of type 2 cannot occur. The passing bases are : two of the eight bases, comfortably within . The companion chapter studies this example using a subgroup bound.
Worked example 8.2.4
(Trace for )
We have , so and . The loop is empty, and the verdict for a coprime base is decided by whether is . We also list , which the round does not compute.
| base | verdict | interpretation | ||
|---|---|---|---|---|
| 1 | 1 | 1 | pass | |
| 2 | 8 | 4 | fail | Fermat witness |
| 4 | 4 | 1 | fail | is a nontrivial root of |
| 7 | 13 | 4 | fail | Fermat witness |
| 8 | 2 | 4 | fail | Fermat witness |
| 11 | 11 | 1 | fail | is a nontrivial root of |
| 13 | 7 | 4 | fail | Fermat witness |
| 14 | 14 | 1 | pass |
The six bases fail at the gcd step.
Some sample computations: . Since , we get . Since , we get .
The bases and are Fermat liars, since , but strong witnesses. Each is a square root of other than , and the companion chapter’s lemma on nontrivial square roots factors from them: and , or and . Only and pass, so of the bases pass.
Worked example 8.2.5
(Trace for )
We have , so and . The round inspects for and for .
A structural shortcut simplifies the computation. We have , and every unit satisfies . So , and is simply the inverse of modulo . Then .
| base | verdict | ||
|---|---|---|---|
| 1 | 1 | pass (stage 0) | |
| 2 | 11 | 16 | fail |
| 4 | 16 | 4 | fail |
| 5 | 17 | 16 | fail |
| 8 | 8 | 1 | fail: is a nontrivial root of |
| 10 | 19 | 4 | fail |
| 11 | 2 | 4 | fail |
| 13 | 13 | 1 | fail: is a nontrivial root of |
| 16 | 4 | 16 | fail |
| 17 | 5 | 4 | fail |
| 19 | 10 | 16 | fail |
| 20 | 20 | pass (stage 0) |
The bases fail at the gcd step.
Check a few entries directly: , and . Also , so .
For the round computes and then , and line 7 returns FAIL with the certificate . Then and . The base similarly gives and .
No unit reaches at stage . Modulo , every even power of a unit is , not . So two of the twenty bases pass. The Fermat liars are , so the strong test rejects two bases that Fermat's test accepts.
Worked example 8.2.6
(A larger trace: , base )
We have , so and . Since is a Carmichael number (see the companion chapter), Fermat's test accepts every coprime base. We run the strong round with , which is coprime to .
It is efficient to compute modulo , and separately and recombine by CRT.
- Mod : , so , and every further square is .
- Mod : and , so , and every further square is .
- Mod : and , so . Squaring gives , then , then .
| stage | mod 3 | mod 11 | mod 17 | mod 561 |
|---|---|---|---|---|
| 0 | 2 | 10 | 8 | 263 |
| 1 | 1 | 1 | 13 | 166 |
| 2 | 1 | 1 | 16 | 67 |
| 3 | 1 | 1 | 1 | 1 |
The recombined values can be checked directly. , , and .
The round proceeds as follows. Line 2 gives , which is not . Iteration gives , iteration gives , and iteration gives . Line 7 returns FAIL with , a nontrivial square root of . The companion chapter’s lemma on nontrivial square roots extracts factors:
and indeed .
The CRT columns show where the nontrivial root came from. The components modulo and reached earlier than the component modulo . At stage the residues had mixed signs, modulo and modulo . The companion chapter uses this mixed-sign idea in its proof.
Concept lensAlgebraic
A pass as a synchronized arrival
Reducing the stage values modulo each prime power that exactly divides splits a round into separate sequences, one per component. Because is odd, exactly when with the same sign modulo every such . So a base passes exactly when either every component starts at , or every component equals at one common stage. Components that arrive at different stages force failure, as in the trace, where the component modulo lagged behind.
Quick check
(Run the strong round for and . Where does it stop, and which factors of does the stop reveal?)
Here , so .
Solution · Answer
Since and , line 2 gives , which is neither nor . In iteration , , so line 7 returns FAIL with , a square root of other than . Then and . The round stops after one squaring, although would allow four iterations.
Cost: arithmetic operations versus bit operations
Let be the number of bits of . This is the size of the input.
Arithmetic-operation count. Computing by left-to-right square-and-multiply uses at most multiplications modulo . After that, the loop performs at most squarings. Since , the total number of modular multiplications in one round is at most
So one round uses modular multiplications, and rounds use (see the exercise on the cost of a round).
Quick check
(Count the modular multiplications in the round for , traced above, and compare the count with the bound .)
Write in binary.
Solution · Answer
In binary . Left-to-right square-and-multiply starts from for the leading bit, then squares once for each of the remaining five bits and multiplies by for the two final bits: multiplications, within . The loop then squares in iterations , three more multiplications. The round uses in total. Since , , and the bound is .
Bit-operation count. Counting modular multiplications as unit-cost operations hides the size of the numbers being multiplied. Each multiplication is between residues of up to bits and produces a product of up to bits, which must then be reduced modulo .
- With schoolbook multiplication and long division, each modular multiplication costs bit operations. One round then costs bit operations, and rounds cost .
- If denotes the cost of multiplying two -bit integers with a faster algorithm, and reduction modulo is done by a technique whose cost is comparable to a multiplication, one round costs .
- The gcd step uses the Euclidean algorithm. This takes division steps on numbers of at most bits, so bit operations under the crude schoolbook count. A finer analysis gives . Either way it does not dominate the exponentiation.
- Drawing a base costs an expected random bits. The rejection loop has no finite deterministic worst-case bound; including sampling, the stated total running time is an expectation.
Comparison with trial division. Trial division by all integers up to needs, for prime , about divisions. This is exponential in the input size . Miller–Rabin is polynomial in .
Common mistake
(Quoting the multiplication count as the running time)
A statement such as “the test takes steps” is correct only when a step is a multiplication modulo . Each such step multiplies numbers of up to bits, so with schoolbook arithmetic a round costs bit operations, and rounds cost . State which cost model is meant before comparing running times.
Quick check
(With schoolbook arithmetic, by roughly what factor does the bound on the bit cost of one round grow when the bit length of doubles? Compare with trial division up to .)
Compare with , and with .
Solution · Answer
The bound becomes , so the bound grows by a factor of . The number of trial divisions, about , becomes about : it is multiplied by , a factor that itself grows exponentially with .
A probable prime is not a proven prime
The two verdicts have very different logical status.
- COMPOSITE is a proof. The failing base, together with its type of failure as classified in the companion chapter, is a certificate that anyone can verify with one exponentiation or one gcd computation.
- PROBABLE-PRIME is not a proof. It means that independently chosen bases all passed. The companion chapter bounds the probability of this event for a composite input. It does not exclude the event, and nothing produced by the test lets a third party verify that is prime.
When primality must actually be established, a separate primality-proving method is needed. Such a method produces a certificate whose verification does not depend on randomness. Those methods are beyond this note. In practice, Miller–Rabin is often used as a fast filter before them, discarding the vast majority of composite candidates cheaply.
Worked example 8.2.7
(A square root that forces an early stop)
For and , write . The first residue is , which is neither nor . The next is , so the round rejects immediately. In fact and , giving the two prime factors. The later values would all be , but the algorithm has already stopped: their presence cannot turn the failure into acceptance.
This root has a concrete CRT explanation: and . Squaring removes the different signs, producing modulo each factor. The mixed signs show why is neither global nor global . For a prime modulus the corresponding factorization argument forbids this behavior.
A Fermat witness need not give an immediate factor. For and we have and . Since , the round computes , which is neither nor , and fails at line 9. The uncomputed value is , so is a Fermat witness and is proved composite. Yet and : none of the values of this round exposes a proper factor through these gcds. A certificate of compositeness and an explicit factor are different kinds of output.
Exercises
Quick check
(Cost of a round: Let be odd with bit length , and with odd.)
(a) Prove that left-to-right square-and-multiply computes using at most modular multiplications. Deduce that one round uses at most modular multiplications.
(b) Assuming schoolbook multiplication and division, so that one multiplication modulo costs at most bit operations for a constant , bound the bit cost of rounds, excluding the gcd and base generation.
(c) For a -bit odd , give an explicit upper bound on the number of modular multiplications per round. Compare it with the number of trial divisions needed to confirm primality by trial division up to .
(d) Explain why "polynomial in " would be the wrong efficiency criterion.
Solution
(a) Let have bits. Left-to-right square-and-multiply starts from , which accounts for the leading bit. For each of the remaining bits, it squares once and, if the bit is , multiplies by once. This is at most multiplications.
Since , we have , and because is an integer, . The loop adds at most squarings. The total is at most
(b) One round costs at most bit operations, so rounds cost less than . This is bit operations.
(c) An odd -bit satisfies . So and . With , the bound is at most modular multiplications per round.
Trial division up to would, for prime , test every candidate divisor up to . Even restricted to odd candidates, that is more than divisions, an astronomically larger number.
(d) The input is written with bits, so efficiency must be measured as a function of . An algorithm polynomial in , such as trial division with cost about , is exponential in and infeasible for numbers of cryptographic size. Miller–Rabin's cost with schoolbook arithmetic is polynomial in , which is what makes it practical.