2. A prime with , such that for some other number and with , is the identity on the curve, but is not the identity. This guarantees primality
of by a theorem of Goldwasser and Kilian (1986).

3. Each has its recursive certificate following it. So if the smallest
is known to be prime, all
the numbers are certified prime up the chain.

A Pratt certificate is quicker to generate for small numbers. The Wolfram Language
task ProvablePrimeQ[n]
in the Wolfram Language package PrimalityProving`
therefore generates an Atkin-Goldwasser-Kilian-Morain certificate only for numbers
above a certain limit ( by default), and a Pratt
certificate for smaller numbers.

Atkin, A. O. L. and Morain, F. "Elliptic Curves and Primality Proving." Math. Comput.61, 29-68, 1993.Bressoud,
D. M. Factorization
and Primality 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.