Understanding Rabin-Miller

I'm posting this to provide some clarification on the Rabin-Miller primality test as requested on Twitter.  My favorite reference on the test is the notes by Diane Hoffoss located here.  If you're not familiar with primality testing and/or Rabin-Miller; read the notes first then come back to this post if you need any clarification.

My purpose here is to restate a few key points from Hoffoss's notes, provide a little more exposition on the examples and to compare her description of the algorithm with the description given in the Handbook of Applied Cryptography.  This is a derivative work and I do not claim to have originated any of the ideas here.  Of course, any mistakes are my own.

This test is discussed in many books including Practical Cryptography, Understanding Cryptography and the Handbook of Applied Cryptography.

Note: For the examples below, I group digits using commas as is the convention in the U.S.  All of the numbers are integers.

First, pick a candidate prime n.  Since a prime n > 2 must be odd, n-1 is even.  So, we can factor n-1 = 2^s∙ m. 

The Rabin-Miller Primality Test is based on a few important properties regarding exponentiation modulo a prime number.

Fermat's Little Theorem

If n is a prime number then a^n-1 must be congruent to 1.  If a^n-1 ≠ 1 mod n, then n is not prime.

Square roots of 1 (Used in the Euler Test)

If n is prime, the only square roots of 1 mod n are ± 1.  Note that  -1² mod n = 1 mod n.

Also note that n-1 mod n and -1 mod n are the same thing.

If n is prime, then a^n-1 = 1 mod n.

If n is prime, then a^(n-1)/2 equals ± 1 since it is a square root of a^n-1. 

If a^(n-1)/2  ≠  ±1 mod p, then n is not prime.

The Rabin-Miller Test

Calculate a^m mod n.  If a^m = ±1 mod n, then declare n prime since any repeated squaring will only result in 1 mod n.  Note that a^m is not square since we have factored out n-1 = 2^s∙ m so that m is the largest non-square exponent.

Repeatedly square a^m mod n.  If the result is 1, we stop and declare n composite since this implies that there is a square root of 1 mod n that is not ± 1.  If we get a result of -1, we declare n to be prime since any repeated squaring of ± 1 will equal 1. 

We continue until we reach a^{m∙ 2^(s-1)} .  If the result is not ±1, we declare n to be composite since it's either a square root of 1 other than ±1 or it's not a square root at all and a^{m∙ 2^s} = a^n-1 ≠ 1 mod n which also means that n is not prime.

First Example:

This example is the first one given for the Rabin-Miller test in Hoffoss's notes.

n = 972,133,929,835,994,161

a = 2

n - 1 = 2⁴ ∙ 60,758,370,614,749,635 mod n    (m = 60,758,370,614,749,635)

2^{60,758,370,614,749,635} = 338,214,802,923,303,483 mod n    (result not ± 1, keep going)

2^{2∙ 60,758,370,614,749,635} = 332,176,174,063,516,118 mod n    (not ± 1)

2^{4 ∙ 60,758,370,614,749,635} = 779,803,551,049,098,051 mod n    (not ± 1)

2^{8 ∙ 60,758,370,614,749,635} = 1 mod n   (n is composite)

The last result (1 mod n) means that the next-to-last result was a square root of 1 mod n that was not ± 1.  This means that n is definitely composite.

Second Example:

This example was linked on Twitter; the comments are mine.  It has one less squaring than the first example, but the result is the same.  n is composite. 

n = 252,601

a = 85,132

n-1 = 2³∙ 31,575    (m = 31,575)

a^31,575 = 191,102 mod n    (result not ± 1, keep going)

a^{2 ∙ 31,575} = 184,829 mod n    (not ± 1)

a^{4 ∙ 31,575} = 1  mod n    (n is composite)

Rabin-Miller as presented in HAC:

Please refer to HAC to understand this section.  This is a partial line-for-line restatement of the algorithm as presented there.  One of the reasons that this statement of the algorithm may be confusing is that it contains a loop that runs the Rabin-Miller algorithm over multiple test values of a.  Other statements of the algorithm may only describe a single iteration.

There are two loops in this algorithm.  Step 2 (For i from 1 to t...) iterates over multiple test values of a.  Step 2.3, third line (While j ≤ s-1 and y ≠ n-1 do...) drives the repeated squarings of the value y.

1. Calculate n-1 = 2^s ∙ r.  In the description above, we used the variable m instead of r.

2.     Run the test t times.

2.1   Chose a random integer a.

2.2   Compute y = a^r

2.3   If y ≠ ± 1 then it's not a square root of 1.  If y = ± 1, then we go to step 2 and proceed to the next iteration of the outer loop; this means that we tentatively declare n to be prime but may need to test more random values for a.

Repeatedly square y.  If we get a result of 1, we declare n to be composite since this implies that the previous result was a square root of 1 that was ≠ ± 1. 

If we get a result of n-1 (note that n-1 = -1 mod n), then we go back to step 2.  Again, this tentatively declares that n is prime.

If the final squaring, y = a^{r ∙ 2^(s-1)} ≠ -1, then we declare n to be composite.  The reason is that if the result is not ±1, it's either a square root of 1 other than ±1 or it's not a square root at all and a^{r∙ 2^s} = a^n-1 ≠ 1 which also means that n is not prime.

3. If we reach step 3, then we've concluded every iteration of the loop in step 2 with a tentative declaration that n is prime.  Now, we make a final declaration that n is prime.