Cryptography Reference
In-Depth Information
n
[
x
]
/
(
X
r
1)
,then
n
is prime. Conversely, for a composite
number
n
, there exist values of
a
and
r
such that
(
X
+
a
)
n
Z
−
in the ring
=(
X
n
+
a
)
in
n
[
x
]
/
(
X
r
Z
1)
. What is decisive here is that such values of
a
and
r
can be found
in polynomial time if
n
is not prime, while if
n
is prime, it can be determined
in polynomial time that such values do not exist. The size of the polynomial
coefficients are bounded by
r
, and thus the calculation is faster, the smaller
r
is. If
r
is of order
log
n
, the polynomial residue can be computed in polynomial time.
Agrawal, Kayal, and Saxena showed that suitable values of
r
can be
−
found of size
O
log
5
n
and that the AKS test must be run only for values
1
≤ a ≤
2
√
r
log
n
. The running time of the AKS test is therefore polynomial in
log
2
n
,givenby
O
log
7
.
5+
ε
n
.
13
The problem is solved.
There remains the fascinating question what practical relevance the AKS
test has from the point of view of cryptography: The expected calculation time
determines whether it is of any practical use.
Crandall gives the values in Table 10-4 for small values of
n
from a small
experimental C implementation on a “decent workstation.”
Table 10-4. Approximate calculation times for the AKS test, after [CrPa]
n
Approximate Time
70 001
3 seconds
700 001
15 seconds
2 147 483 647
200 seconds
1125 899 906 842 679
4000 seconds (ca. 1 hour)
618 970 019 642 690 137 449 562 111
100 000 seconds (ca. 1 day)
The times in the table correspond to about
10
−
6
log
6
n
seconds. An
implementation by F. Bornemann based on the Pari-GP library requires nine
seconds on a 1.7-GHz PC for proving the primality of
628 363 443 011
(see
http://www-m3.ma.tum.de/m3/ftp/Bornemann/PARI/aks2.txt
). The running time
for a 512-bit prime number would then take several days. We thus obtain a
definitive result, whose certainty we can approach only asymptotically using
probabilistic primality tests. Since we can make the remaining probability of
error, say by using the Miller-Rabin test, arbitrarily small, the disadvantage of not
having that last bit of certainty is not very large in practice.
13
Improvements in these numbers have been considered on the basis of suggestions by H.
Lenstra and D. Bernstein (see [Bern]). If we consider a conjecture about the density of Sophie
Germain primes (prime numbers
n
for which
2
n
+1
is also prime) by Hardy and Littlewood
(1922), we would have a run time for the AKS test of
O
log
6+
ε
n
. Hardy and Littlewood
conjectured that the cardinality of the set
{
p
≤
x
|
p
and
2
p
+1
are prime
}
is asymptotic to
2
C
2
/
ln
2
x
, with
C
2
=0
.
6601618158
...
, the so-called twin-primes constant. This conjec-
ture has been verified up to
x
= 10 000 000 000
, and therefore, the more favorable run-time
estimate for the AKS test holds at least for numbers with up to
100 000
digits (see [Born]).
