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 .'' Math. Comput.
44, 483-494, 1985.
Wunderlich, M. C. ``A Performance Analysis of a Simple Prime-Testing Algorithm.'' Math. Comput. 40,
709-714, 1983.