TOPICS
Search

Pratt Certificate


The Pratt certificate is a primality certificate based on Fermat's little theorem converse. Prior to the work of Pratt (1975), the Lucas-Lehmer test had been regarded purely as a heuristic that worked a lot of the time (Knuth 1969). Pratt (1975) showed that Lehmer's primality heuristic could be made a nondeterministic procedure by applying it recursively to the factors of n-1. As a consequence of this result, Pratt (1975) became the first to demonstrate that the resulting tree implies that prime factorization lies in the complexity class NP.

To generate a Pratt certificate, assume that n is a positive integer and {p_i} is the set of prime factors of n-1. Suppose there exists an integer x (called a "witness") such that x^(n-1)=1 (mod n) but x^e≢1 (mod n) whenever e is one of (n-1)/p_i. Then Fermat's little theorem converse states that n is prime (Wagon 1991, pp. 278-279).

By applying Fermat's little theorem converse to n and recursively to each purported factor of n-1, a certificate for a given prime number can be generated. Stated another way, the Pratt certificate gives a proof that a number a is a primitive root of the multiplicative group (mod p) which, along with the fact that a has order p-1, proves that p is a prime.

PrattCertificate

The figure above gives a certificate for the primality of n=7919. The numbers to the right of the dashes are witnesses to the numbers to left. The set {p_i} for n-1=7918 is given by {2,37,107}. Since 7^(7918)=1 (mod 7919) but 7^(7918/2), 7^(7918/37), 7^(7918/107)≢1 (mod 7919), 7 is a witness for 7919. The prime divisors of 7918=7919-1 are 2, 37, and 107. 2 is a so-called "self-witness" (i.e., it is recognized as a prime without further ado), and the remainder of the witnesses are shown as a nested tree. Together, they certify that 7919 is indeed prime. Because it requires the factorization of n-1, the method of Pratt certificates is best applied to small numbers (or those numbers n known to have easily factorable n-1).

A Pratt certificate is quicker to generate for small numbers than are other types of primality certificates. The Wolfram Language function ProvablePrimeQ[n] in the Wolfram Language package PrimalityProving` therefore generates an Atkin-Goldwasser-Kilian-Morain certificate only for numbers above a certain limit (10^(10) by default), and a Pratt certificate for smaller numbers.


See also

Atkin-Goldwasser-Kilian-Morain Certificate, Fermat's Little Theorem Converse, Lucas-Lehmer Test, Primality Certificate, Witness

Explore with Wolfram|Alpha

References

Knuth, D. E. §4.5.4 in The Art of Computer Programming, Vol. 2: Seminumerical Algorithms. Reading, MA: Addison-Wesley, 1969.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.

Referenced on Wolfram|Alpha

Pratt Certificate

Cite this as:

Weisstein, Eric W. "Pratt Certificate." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PrattCertificate.html

Subject classifications