info prev up next book cdrom email home

Primality Certificate

A short set of data that proves the primality of a number. A certificate can, in general, be checked much more quickly than the time required to generate the certificate. Varieties of primality certificates include the Pratt Certificate and Atkin-Goldwasser-Kilian-Morain Certificate.

See also Atkin-Goldwasser-Kilian-Morain Certificate, Compositeness Certificate, Pratt Certificate


Wagon, S. ``Prime Certificates.'' §8.7 in Mathematica in Action. New York: W. H. Freeman, pp. 277-285, 1991.

© 1996-9 Eric W. Weisstein