Cryptography Reference
In-Depth Information
Miller-Rabin Primality Test
Input
: prime candidate
p
with
p
1 = 2
u
r
and security parameter
s
Output
: statement “
p
is composite” or “
p
is likely prime”
Algorithm
:
−
1
R
i
= 1TO
s
choose random
a
∈{
2
,
3
,...,
p
−
2
}
a
r
1.2
z
≡
mod
p
1.3
IF
z
≡
1 and
z
≡
p
−
1
1.4
FOR
j
= 1TO
u
−
1
z
2
mod
p
IF
z
= 1
RETURN (“
p
is composite”)
z
≡
1.5
IF
z
1
RETURN (“
p
is composite”)
=
p
−
2
RETURN (“
p
is likely prime”)
Step 1.2 is computed by using the square-and-multiply algorithm. The IF statement
in Step 1.3 tests the theorem for the case
j
= 0. The FOR loop 1.4 and the IF state-
ment 1.5 test the right-hand side of the theorem for the values
j
= 1
,...,
u
1.
It can still happen that a composite number
p
gives the incorrect statement
“prime”. However, the likelihood of this rapidly decreases as we run the test with
several different random base elements
a
. The number of runs is given by the secu-
rity parameter
s
in the Miller-Rabin test. Table 7.2 shows how many different values
a
must be chosen in order to have a probability of less than 2
−
80
that a composite is
incorrectly detected as a prime.
−
Table 7.2
Number of runs within the Miller-Rabin primality test for an error probability of less
than 2
−
80
Bit lengths of
p
Security parameter
s
250
11
300
9
400
6
500
5
600
3
Example 7.9.
Miller-Rabin Test
Let
p
= 91. Write
p
as
p
1 = 2
1
−
·
45. We select a security parameter of
s
= 4. Now,
choose
s
times a random value
a
:
1. Let
a
= 12:
z
= 12
45
≡
90 mod 91, hence,
p
is likely prime.
2. Let
a
= 17:
z
= 17
45
≡
90 mod 91, hence,
p
is likely prime.
3. Let
a
= 38:
z
= 38
45
≡
90 mod 91, hence,
p
is likely prime.
