Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Proving primality in essentially quartic random time

Author: Daniel J. Bernstein
Journal: Math. Comp. 76 (2007), 389-403
MSC (2000): Primary 11Y11
Published electronically: September 14, 2006
MathSciNet review: 2261028
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: This paper presents an algorithm that, given a prime $ n$, finds and verifies a proof of the primality of $ n$ in random time $ (\operatorname{lg} n)^{4+o(1)}$. Several practical speedups are incorporated into the algorithm and discussed in detail.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y11

Retrieve articles in all journals with MSC (2000): 11Y11

Additional Information

Daniel J. Bernstein
Affiliation: Department of Mathematics, Statistics, and Computer Science (M/C 249), The University of Illinois at Chicago, Chicago, Illinois 60607–7045

Received by editor(s): February 13, 2004
Received by editor(s) in revised form: December 9, 2004
Published electronically: September 14, 2006
Additional Notes: The author was supported by the National Science Foundation under grant DMS–0140542, and by the Alfred P. Sloan Foundation. He used the libraries at the Mathematical Sciences Research Institute, the University of California at Berkeley, and the American Institute of Mathematics.
Article copyright: © Copyright 2006 by the author

American Mathematical Society