Primality testing using elliptic curves

We present a primality proving algorithm-a probabilistic primality test tha t produces short certificates of primality on prime inputs. We prove that t he test runs in expected polynomial time for all but a vanishingly small fr action of the primes. As a corollary, we obtain an algorithm for generating large certified primes with distribution statistically close to uniform. U nder the conjecture that the gap between consecutive primes is bounded by s ome polynomial in their size, the test is shown to run in expected polynomi al time for all primes, yielding a Las Vegas primality test. Our test is based on a new methodology for applying group theory to the pro blem of prime certification, and the application of this methodology using groups generated by elliptic curves over finite fields. We note that our methodology and methods have been subsequently used and im proved upon, most notably in the primality proving algorithm of Adleman and Huang using hyperelliptic curves and in practical primality provers using elliptic curves.