Cryptography Reference
In-Depth Information
Parameter : k , an integer
Input : n , an integer of
bits
Output : notification of non-primality or pseudo-primality
Complexity :
3 )
O
( k
1: if n
2 then output “prime” and stop
2: if n is even then output “composite” and stop
3: write n
=
2 s t
=
+
1
4: repeat
5:
pick a random b such that 0
<
b
<
n
b t
x
mod n , i
0
6:
if x
=
1 then
7:
while x
=
n
1 do
8:
x 2
x
mod n , i
i
+
1
9:
1 then
11: output “composite” and stop
12: end if
13: end while
14: end if
15: until k iterations are made
16: output “pseudo-prime” and stop
if i
=
s or x
=
10:
Figure 7.3. The Miller-Rabin Primality Test.
detects prime numbers, and detects composite ones with a probability greater than
1
4 k .
1 by 2 until the result
becomes some odd t . Then, we raise b to the power of t , and square it. If we eventually
find 1 (as in the Fermat test), we check that the previous value was
The Miller-Rabin test consists of successively dividing n
1. If it was not,
we have found a square root of 1 which is neither
+
1 nor
1, which is a proof of
compositeness (see Fig. 7.4).
Theorem 7.6 (Miller-Rabin 1976, 1980 [134, 154]). Let n be an integer, and let us
consider the algorithm in Fig. 7.3 with input n and parameter k. If n is prime, then the
algorithm always outputs “prime” or “pseudo-prime.” Conversely, if n is composite,
the algorithm outputs “composite” with probability greater than 1
4 k .
This result is proven in Section 7.1.5.
at most s
=
1
=
1
=
1
=
1
=
1
1
b t
SQ
SQ
···
SQ
SQ
mod n
is it
≡−
1?
Figure 7.4. The Miller-Rabin test.
Search WWH ::




Custom Search