Cryptography Reference
In-Depth Information
7.1.5
Analysis of the Miller-Rabin Test
Proof.
Since the case of even integers is trivial we assume that
n
is odd and we write
n
2
s
t
=
+
1.
n
is in
Z
n
. We know that
b
2
s
t
When
n
is prime, any
b
such that 0
<
b
<
≡
1 (mod
n
). Since
Z
n
is a field, we know that the only square roots of 1 are
+
1 and
1 mod
n
. Hence either
b
t
−
≡
1 (mod
n
) or there exists
i
such that 0
≤
i
<
s
and
b
2
i
t
≡−
1 (mod
n
). Therefore none of the
k
iterations can lead to “composite.”
For a composite
n
, the result is quite technical to prove. We simply mention the
following two results.
If
n
passes the Miller-Rabin test for
b
, then
n
passes the Solovay-Strassen test
for
b
, and so the Miller-Rabin test is at least as efficient as the Solovay-Strassen
test.
One can prove that the probability that the test passes with
b
∈
Z
n
is less than
1
2
.
We simply prove the second result. We refer to Ref. [102] for more details. One can
easily notice that the set
G
of
b
's i n
Z
n
for which the test passes is a subgroup. If we have
G
Z
n
, then the result holds since #
G
is a factor of
=
ϕ
(
n
). Otherwise,
n
=
p
1
···
p
r
p
j
−
1
divides 2
i
t
. We know
is a Carmichael number. Let
i
j
be the smallest
i
such that
2
Z
n
we have
b
2
i
j
+
1
t
1 and
b
2
i
j
t
∈
mod
p
j
=
mod
p
j
=
that for any
b
1 if and only if
b
is a quadratic residue modulo
p
j
. Let
j
be the index for which
i
j
is the greatest and
let
k
be the index different from
j
for which
i
j
is the greatest. We know that for any
b
Z
n
we have
b
2
i
j
+
1
t
∈
mod
n
=
1. If
j
>
k
, for any quadratic nonresidue
b
modulo
p
j
,
b
2
i
j
t
mod
n
is neither
+
1 nor
n
−
1 (which is
−
1 modulo
n
) and so the test cannot pass.
k
, for any
b
with different quadratic residuosity modulo
p
j
and
p
k
,
b
2
i
j
t
If
j
=
mod
n
is neither
+
1 nor
n
−
1 and so the test cannot pass. In both cases, we cannot have
Z
n
.
G
=
7.1.6 Prime Number Generation
It should be noticed that prime numbers can be randomly generated with ease: we can
iteratively pick a random number until one primality test responds positively. Due to
the following
Prime Number Theorem
, we know that we will eventually end up with a
prime number of
n
bits within
O
(
n
) trials.
Theorem 7.7 (Prime Number Theorem).
Let p
(
N
)
denote the number of prime num-
bers in
N
{
2
,
3
,...,
N
}
. We have p
(
N
)
∼
log
N
when N increases toward infinity.
2
Thus the number of prime numbers of at most
bits is asymptotically equal to
log 2
,
which means that the probability that a random
-bit number is prime is
(1
/
).
Search WWH ::
Custom Search