MANINDRA AGRAWAL, NEERAJ KAYAL, AND NITIN SAXENA
this problem (referred to as the primality testing problem) has been investi-
gated intensively. It is trivial to see that the problem is in the class co-NP: if n
is not prime it has an easily verifiable short certificate, viz., a nontrivial factor
of n. In 1974, Pratt observed that the problem is in the class NP too [Pra]
(thus putting it in NP n co-NP).
In 1975, Miller [Mil] used a property based on Fermat's Little Theorem to
obtain a deterministic polynomial-time algorithm for primality testing assum-
ing the Extended Riemann Hypothesis (ERH). Soon afterwards, his test was
modified by Rabin [Rab] to yield an unconditional but randomized polynomial-
time algorithm. Independently, Solovay and Strassen [SS] obtained, in 1974,
a different randomized polynomial-time algorithm using the property that for
a prime n, (a) = a 2 (mod n) for every a ((-) is the Jacobi symbol). Their
algorithm can also be made deterministic under ERH. Since then, a number
of randomized polynomial-time algorithms have been proposed for primality
testing, based on many different properties.
In 1983, Adleman, Pomerance, and Rumely achieved a major break-
through by giving a deterministic algorithm for primality that runs in
(log n)(l1°gl°gl°gn) time (all the previous deterministic algorithms required ex-
ponential time). Their algorithm was (in a sense) a generalization of Miller's
idea and used higher reciprocity laws. In 1986, Goldwasser and Kilian [GK]
proposed a randomized algorithm based on elliptic curves running in expected
polynomial-time, on almost all inputs (all inputs under a widely believed hy-
pothesis), that produces an easily verifiable short certificate for primality (un-
til then, all randomized algorithms produced certificates for compositeness
only). Based on their ideas, a similar algorithm was developed by Atkin [Atk].
Adleman and Huang [AH] modified the Goldwasser-Kilian algorithm to obtain
a randomized algorithm that runs in expected polynomial-time on all inputs.
The ultimate goal of this line of research has been, of course, to obtain an
unconditional deterministic polynomial-time algorithm for primality testing.
Despite the impressive progress made so far, this goal has remained elusive.
In this paper, we achieve this. We give a deterministic, O'(log15/2 n) time
algorithm for testing if a number is prime. Heuristically, our algorithm does
better: under a widely believed conjecture on the density of Sophie Germain
primes (primes p such that 2p + 1 is also prime), the algorithm takes only
O0 (log6 n) steps. Our algorithm is based on a generalization of Fermat's Little
Theorem to polynomial rings over finite fields. Notably, the correctness proof
of our algorithm requires only simple tools of algebra (except for appealing
to a sieve theory result on the density of primes p with p - 1 having a large
prime factor-and even this is not needed for proving a weaker time bound of
O (log21/2 n) for the algorithm). In contrast, the correctness proofs of earlier
algorithms producing a certificate for primality [APR], [GK], [Atk] are much
more complex.
782
This content downloaded from 162.105.94.234 on Wed, 27 Dec 2017 01:11:47 UTC
All use subject to http://about.jstor.org/terms
评论0