TOPICS

# Atkin-Goldwasser-Kilian-Morain Certificate

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.

Elliptic Curve Primality Proving, Elliptic Pseudoprime, Pratt Certificate, Primality Certificate, Witness

## Explore with Wolfram|Alpha

More things to try:

## References

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.

## Referenced on Wolfram|Alpha

Atkin-Goldwasser-Kilian-Morain Certificate

## Cite this as:

Weisstein, Eric W. "Atkin-Goldwasser-Kilian-Morain Certificate." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Atkin-Goldwasser-Kilian-MorainCertificate.html