Cryptography Reference
In-Depth Information
The answer is yes and it only arrived in 2002 when Agrawal, Kayal and Saxena
introduced their remarkable algorithm, now known as the
AKS algorithm
or
AKS test
[3]. This result is striking because the algorithm is rather simple and the proof, while
being very ingenious, uses only elementary methods. The algorithm is based on the
following theorem:
∈ Z
n
,
Theorem 6.10
Let n
>
1
be an integer. Then n is prime if and only if for all a
n
X
n
the following identity in the ring
Z
n
[
X
]
holds:
(
X
+
a
)
=
+
a.
The AKS algorithm shows that the decision problem 'Is
n
prime?' belongs to the
class
but, despite being a major breakthrough, the algorithm is only of theoretical
interest and is not currently useful for selecting primes for cryptographic applications.
Its running time is
O
P
ln
12
+
ε
n
and, under a widely believed conjecture about
Sophie
Germain primes
,
3
i.e., primes
p
such that 2
p
(
)
+
1 is also prime, it comes down to
ln
6
+
ε
n
. This is slow not only in comparison to Miller-Rabin's test but also in
comparison to the expected time of ECPP. Several people are currently working on
improving the algorithm (and its running time) but whether it will become useful to
find large primes in practice remains to be seen. Detailed discussions of the AKS
algorithm can be found in [60, 180].
O
(
)
Remark 6.7
The comparison between CPP and AKS provides an example of a rare
situation in which a superpolynomial-time test is more efficient than a polynomial-
time test in practice. Of course, this is not so surprising if one bears in mind the slow
growth of the exponent ln ln ln
n
appearing in the time estimate of CPP.
6.3 Generating Random Primes
For many cryptographic applications it is necessary to generate large random primes.
These can be either primes of a specified bit length
k
or primes less than a given
bound. In both cases, the idea (sketched at the beginning of this chapter when studying
the distribution of primes) is simple enough: given a primality test, integers in the
required range are randomly generated and submitted to the primality test until a
prime is found.
The simplest way to generate a random integer in the interval
[
0
,
n
−
1
]
(i.e., a
random element of
r
, is just to generate
r
random bits
and to check whether the integer defined in the standard way by the
r
-bit string
thus obtained is less than
n
, repeating the process until this condition is satisfied.
This condition can be checked in polynomial time and, clearly, the probability that
a random
r
-bit string satisfies it is equal to
n
Z
n
), where len
(
n
−
1
)
=
2
r
/
and hence
≥
1
/
2. Thus the ex-
pected number of trials is
≤
2 and the algorithm runs in expected polynomial
3
This conjecture postulates that Sophie Germain primes are fairly frequent, see [180, Conjecture
5.24] and the discussions in [180, 21.2, 21.3] and [60, 4.5.1, 4.5.2]. There is some heuristic evidence
in favor of this hypothesis, however it is not even known whether or not there are infinitely many
of these primes.
