![]() ![]() ![]() ![]() |
![]() ![]() ![]() ![]() |
A recursive Primality Certificate for a Prime . The certificate consists of a list of
A Pratt Certificate is quicker to generate for small numbers. The Mathematica
(Wolfram Research, Champaign,
IL) task ProvablePrime[n] therefore generates an Atkin-Goldwasser-Kilian-Morain certificate only for numbers above a
certain limit (
by default), and a Pratt Certificate for smaller numbers.
See also Elliptic Curve Primality Proving, Elliptic Pseudoprime, Pratt Certificate, Primality Certificate, Witness
References
Atkin, A. O. L. and Morain, F. ``Elliptic Curves and Primality Proving.'' Math. Comput. 61, 29-68,
1993.
Bressoud, D. M. Factorization and Prime Testing. New York: Springer-Verlag, 1989.
Goldwasser, S. and Kilian, J. ``Almost All Primes Can Be Quickly Certified.'' Proc. 18th STOC.
pp. 316-329, 1986.
Morain, F. ``Implementation of the Atkin-Goldwasser-Kilian Primality Testing Algorithm.'' Rapport de Recherche 911,
INRIA, Octobre 1988.
Schoof, R. ``Elliptic Curves over Finite Fields and the Computation of Square Roots mod
Wunderlich, M. C. ``A Performance Analysis of a Simple Prime-Testing Algorithm.'' Math. Comput. 40,
709-714, 1983.
.'' Math. Comput.
44, 483-494, 1985.