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