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
2:
output “prime” and stop
3:
end if
4:
if
n
is even
then
5:
output “composite” and stop
6:
end if
7:
repeat
8:
=
pic
k a
random
b
such that 0
<
b
<
n
≡
n
(mod
n
)
then
10:
output “composite” and stop
11:
end if
12:
until
k
iterations are made
13:
output “pseudo-prime” and stop
if
b
n
−
1
9:
2
Figure 7.2.
The Solovay-Strassen Primality Test.
We can also verify the definition with the factorization of
n
by
b
n
362
561
=
362
=
3
×
11
×
17
362
3
362
11
362
17
=
×
×
thus
n
=
362
2
−
1
362
11
−
1
362
17
−
1
and
mod 3
=
2,
mod 11
=
10,
mod 17
=
16,
2
2
2
1)
3
(
−
=−
1.
Instead of proving the previous theorem, we will prove an actually much stronger
theorem which is stated as follows.
Theorem 7.5 (Solovay-
Str
assen 1977 [174]).
Let n be an odd integer. If n is prime,
for any b
≡
n
(mod
n
)
. Conversely, if n is composite, this equality
holds for no more than half of all the possible b values.
Z
n
we have b
n
−
1
∈
2
This shows that when
n
is prime, the primality test in Fig. 7.2 always answers “prime”
or “pseudo-prime”; otherwise, it answers “composite” with probability greater than
1
2
−
k
,
k
being the maximum number of times the test iterates.
−
Proof.
To prove the theorem, we first let
n
be an odd prime number. The Jacobi symbol
reduces to the Legendre symbol, and all
b
such that 0
n
are in
Z
n
. We thus only
<
b
<
Search WWH ::
Custom Search