Pratt Certificate
A primality certificate based on Fermat's Little Theorem Converse. Although the general idea had been well-establishedfor some time, Pratt became the first to prove that the certificate tree was of polynomial size and could also be verified inpolynomial time. He was also the first to observe that the tree implies that Primes are in the complexity classNP.
To generate a Pratt certificate, assume that 
is a Positive Integer and 
is the set of PrimeFactors of 
. Suppose there exists an Integer 
(called a ``Witness'') such that
but 
(mod ) whenever 
is one of 
. Then Fermat's Little TheoremConverse states that is Prime (Wagon 1991, pp. 278-279).
By applying Fermat's Little Theorem Converse to and recursively to each purported factor of , a certificate for a given Prime Number can be generated. Statedanother way, the Pratt certificate gives a proof that a number 
is a Primitive Root of the multiplicativeGroup (mod 
) which, along with the fact that has order 
, proves that is a Prime.
The figure above gives a certificate for the primality of 
. The numbers to the right of the dashes areWitnesses to the numbers to left. The set for 
is given by 
. Since
but 
, 
, 
(mod 7919), 7 is a Witness for7919. The Prime divisors of 
are 2, 37, and 107. 2 is a so-called ``self-Witness'' (i.e., it isrecognized as a Prime without further ado), and the remainder of the witnesses are shown as a nested tree. Together, theycertify that 7919 is indeed Prime. Because it requires the Factorization of , the Method of Prattcertificates is best applied to small numbers (or those numbers known to have easily factorable ).
A Pratt certificate is quicker to generate for small numbers than are other types of primality certificates. The Mathematica
(Wolfram Research, Champaign, IL) task ProvablePrime[n] therefore generates anAtkin-Goldwasser-Kilian-Morain Certificate only for numbers above a certain limit (
by default), and a Prattcertificate for smaller numbers.
References
Pratt, V. ``Every Prime Has a Succinct Certificate.'' SIAM J. Comput. 4, 214-220, 1975. Wagon, S. Mathematica in Action. New York: W. H. Freeman, pp. 278-285, 1991. Wilf, H. §4.10 in Algorithms and Complexity. Englewood Cliffs, NJ: Prentice-Hall, 1986.
- Psi Function
- p-Signature
- PSLQ Algorithm
- PSOS Algorithm
- P-Symbol
- Ptolemy Inequality
- Ptolemy's Theorem
- Public-Key Cryptography
- Puiseaux's Theorem
- Pullback Map
- Pulse Function
- Purser's Theorem
- Pursuit Curve
- Push
- Puzzle
- P-Value
- Pyramid
- Pyramidal Frustum
- Pyramidal Number
- Pyritohedron
- Pythagoras's Constant
- Pythagoras's Theorem
- Pythagoras Tree
- Pythagorean Fraction
- Pythagorean Quadruple