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

^{2}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

^{4}**∙**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

^{3}**∙**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.

## No comments:

## Post a Comment