A recursive primality certificate for a prime 
. The certificate consists of a list of
1. A point on an elliptic curve 
 |
for some numbers 
and 
.
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.
." Math. Comput. 44, 483-494, 1985.Wunderlich,
M. C. "A Performance Analysis of a Simple Prime-Testing Algorithm."
Math. Comput. 40, 709-714, 1983.