Cryptography Reference
In-Depth Information
An integer
N
is called a
base-
a
probable prime
if the Miller-Rabin sequence has the
good form and is called a
base-
a
pseudoprime
if it is a base-
a
probable prime that is
actually composite.
1 and 2
N
−
1
Exercise 12.1.8
Let
N
=
561. Note that gcd(2
,N
)
=
≡
1(mod
N
). Show
that the Miller-Rabin method with
a
2 demonstrates that
N
is composite. Show that this
failure allows one to immediately split
N
.
=
Theorem 12.1.9
Let n>
9
be an odd composite integer. Then N is a base-a pseudoprime
for at most ϕ
(
N
)
/
4
bases between 1 and N.
Proof
See Theorem 3.5.4 of [
150
] or Theorem 10.6 of Shoup [
497
].
Hence, if a number
N
passes several Miller-Rabin tests for several randomly chosen
bases
a
then one can believe that with high probability
N
is prime (Section 5.4.2 of Stin-
son [
532
] gives a careful analysis of the probability of success of a closely related algorithm
using Bayes' theorem). Such an integer is called a
probable prime
. In practice, one chooses
O
(log(
N
)) random bases
a
and runs the Miller-Rabin test for each. The total complexity
is therefore
O
(log(
N
)
4
) bit operations (which can be improved to
O
(log(
N
)
2
M
(log(
N
)))
where
M
(
m
) is the cost of multiplying two
m
-bit-integers).
12.1.3 Primality proving
Agrawal, Kayal and Saxena (AKS) discovered a deterministic algorithm that runs in
polynomial-time and determines whether or not
N
is prime. We refer to Section 4.5 of
[
150
] for details. The original AKS test has been improved significantly. A variant due to
Bernstein requires
O
(log(
N
)
4
+
o
(1)
) bit operations using fast arithmetic (see Section 4.5.4
of [
150
]).
There is also a large literature on primality proving using Gauss and Jacobi sums and
using elliptic curves. We refer to Sections 4.4 and 7.6 of [
150
].
In practice, the Miller-Rabin test is still widely used for cryptographic applications.
12.2 Generating random primes
Definition 12.2.1
Let
X
∈ N
, then
π
(
X
) is defined to be the number of primes 1
<p<X
.
The famous
prime number theorem
states that
π
(
X
) is asymptotically equal to
X/
log(
X
) (as always log denotes the natural logarithm). In other words, primes are rather
common among the integers. If one choose a random integer 1
<p<X
then the probabil-
ity that
p
is prime is therefore about 1
/
log(
X
) (equivalently, about log(
X
) trials are required
to find a prime between 1 and
X
). In practice, this probability increases significantly if one
choose
p
to be odd and not divisible by 3.
Theorem 12.2.2
Random (probable) prime numbers of a given size X can be gen-
erated using the Miller-Rabin algorithm in expected O
(log(
X
)
5
)
bit operations (or
O
(log(
X
)
3
M
(log(
X
)))
using fast arithmetic).
