Almost all primes can be quickly certified

This paper presents a new probabilistie primality test. Upon termination the test outputs "composite" or "prime", along with a short proof of correctness, which can be verified in deterministic polynomial time. The test is different from the tests of Miller [M], Solovay-Strassen [SSI, and Rabin [R] in that its assertions of primality are certain, rather than being correct with high probability or dependent on an unproven assumption. Thc test terminates in expected polynomial time on all but at most an exponentially vanishing fraction of the inputs of length k, for every k. This result implies: • There exist an infinite set of primes which can be recognized in expected polynomial time. • Large certified primes can be generated in expected polynomial time. Under a very plausible condition on the distribution of primes in "small" intervals, the proposed algorithm can be shown ' to run in expected polynomial t ime on eve ry i n p u t . This * R e s e a r c h s u p p o r t e d i n p a r t by N S F G r a n t 8 5 0 9 9 0 5 D C R Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, a n d notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. © 1986 ACM 0-89791-193-8/86/0500/0316 $00.75 316 condition is implied by Cramer 's conjecture. The methods employed are from the theory of elliptic curves over finite fields. 1. I N T R O D U C T I O N I . I T e s t i n g P r i m a l i t y : B r i e f R e v i e w Distinguishing prime numbers from composites has intrigued mathemat ic ians as early as about 274 B.C, when the sieve algorithm of Eratosthenes has been allegedly recorded. Much progress has been made on this problem since tile 17th century by Fermat, Euler, Legendre and Gauss. With the arrival of fast computat ional devices new algorithmic ideas based on the work of Fermat and Gauss were proposed and implemented (see [D],[BLS]). These algorithms mostly relied on factoring and thus where impractical for even moderate size inputs. The interest in primality in complexity theory was invoked by the exciting primality tests of Miller[M], Solovay and Srassen [SS], and Rabin [R]. Miller's algorithm [M] is a deterministic polynomial t ime procedure, which when answering "composite" gives a proof of correctness, and when answering "prime" does not. The assertions of primality made by the algori thm are always correct if if the Extended Riemann Hypothesis (ERH) is true. However, if the ERII is false, the numbers declared prime may still be composite. Thus, tile ERII is not used to bound the running time of the algorithm, but to vouch for the correctness of the answer. The probabilistic primality tests of SolovayStrassen [SS] and Rabin [SS], essentially perform a probabilistic search for a proof of compositeness. The failure of this search, provides circumstantial evidence that the number is not composite. These algorithms always terminate in polynomial time on every input. Upon termination they declare the input either composite or probably prime. When a number is declared "composite", a short (verifiable in deterministic polynomial time) proof (certificate) of compositeness is provided. When a number is declared "probably prime", then it is a prime with very high probability, but no certainty is provided. The fastest deterministic algorithm known is due to Adleman, Pomerance and Rumley [APR] (followed by Choen-Lenstra[CL]) and runs in time O(kc log los k) on inputs of length k. The answers of this algorithm are always correct. Unfortunately, it is not only slow but, like its predecessors, does do not provide us with a short certificate (i.e polynomial time verifiable proof) of its assertions of primality. As discussed above, finding a short certificate of compositeness can be done quickly probabilistically. But, how about short proofs of primality? Although it is not as obvious as in the case of compositeness, Pra t t [P] has shown that short proofs of primality do exist (i.e the set PRIMES is in NP). Unfortunately, finding a Pratt-certificate for a given prime involves being able to factor quickly, which is hard. Partial progress toward finding short proof of primality quickly was made by Furer IF]. He shows a Las Vegas (always correct, probably fast) algorithm distinguishing between n a product of two primes and the n a prime (provided n ~ 1 mod 24). To summarize, the following questions remain open: • Is there an infinite set of primes which can be recognized in expected polynomial time ? • Can random large certified primes be generated in expected polynomial time? • Is there a probabilistic primality test which is alaways correct and probably fast on every prime input, i.e a Las Vegas primality test ? 1.2 O u r Resul t s In this paper, we propose a probabilistic algorithm which upon termination outputs either "prime" or "composite", along with a short proof (certificate) of correctness. The proof of correctness can be verified by a deterministic polynomial Lime algorithm. We prove the following. T h e o r e m 1: Given any prime p of length k, our algorithm outputs a certificate of correctness of size O(k2), which can be verified correct in O(k 4) deterministic time. T h e o r e m 3: For every size k ~> 0, our algorithm terminates in expected polynomial time on at least 1 0(2 ' ~ ' ~ ' ~ ) of the prime inputs of length k. Note that the fraction of primes for which we could not prove that the algorithm terminates in expected polynomial time is smaller than any polynomial in k fraction. Let ~(x) denote the number of primes smaller than z. Theorem 2: Our algorithm terminates in expected polynomial time on every input if the following conjecture is true: