Cryptography Reference
In-Depth Information
to be prime belongs in the computational complexity class P. The algorithm was
declared “brilliant and beautiful” by Carl Pomerance. The proof is elegant and
surprisingly without any deep complexity, in contrast to what had been supposed,
since a solution to the problem had been sought for centuries. Above all, we note
that the proof does not rely on any unproven conjectures (see [AgKS]).
AKS algorithm for determining whether an integer
n
is prime
1.
If
n
is a power of a natural number, go to step 8.
2.
Set
r
←
2
.
3.
If
gcd(
r, n
)
=1
, go to step 8.
4.
If
r
is not prim
e,
go to step 5. Otherwise, let
q
be the largest prime factor of
r
√
r
log
n
and
n
(
r
−
1)
/q
−
1
.If
q
≥
=
r
, go to step 6.
4
5.
Set
r ← r
+1
and go to step 3.
{
1
,...,
2
√
r
log
n}
it is the case that
(
X − a
)
n
6.
If for some
a
in the set
≡
X
n
a
(
mod
X
r
1
,n
)
, go to step 8.
12
−
−
7.
Output “
n
is prime.”
8.
Output “
n
is composite.”
To exclude powers of natural numbers in step 1 of the AKS test it suffices to
test whether
n
1
/b
b
=
b
for
2
≤ b<
log
n
. The integer part of the root
n
1
/b
is calculated with the algorithm previously presented in this chapter.
The AKS algorithm is based on a variant of Fermat's little theorem together
with the binomial theorem, according to which for
1
<n∈
N
and
a ∈
Z
n
,the
integer
n
is prime precisely when in the polynomial ring
Z
n
[
X
]
(see [AgKS], page
2), one has
(
X
+
a
)
n
=(
X
n
+
a
)
.
(10.30)
n
[
X
]
would then be able to
determine definitively whether an integer
n
is prime. However, there would be
considerable computation to determine the
n
coefficients of the polynomial
(
X
+
a
)
n
, even more than in applying the sieve of Eratosthenes. Following the
idea of Agrawal, Kayal, and Saxena, it turns out that both sides of equation (10.30)
can be reduced modulo
(
X
r
A test based on this fact for an element
a
of
Z
−
1)
for a suitable value of
r
.Iffor
sufficiently
many
values of
a
one has the equality
(
X
+
a
)
n
=(
X
n
+
a
)
(10.31)
12
q
(
x
)(
mod
x
r
According to the notation of Agrawal, Kayal and Saxena,
p
(
x
)
≡
−
1
,n
)
if
p
(
x
)
and
q
(
x
)
have the same remainders on division by both
x
r
−
1
and
n
.
