Pratt Certificate

A primality certificate based on Fermat's Little Theorem Converse. Although the general idea had been well-established for some time, Pratt became the first to prove that the certificate tree was of polynomial size and could also be verified in polynomial time. He was also the first to observe that the tree implies that Primes are 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}\equiv 1\ \left({{\rm mod\ } {n}}\right)$ but $x^e\not\equiv 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.

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}\equiv 1\ \left({{\rm mod\ } {7919}}\right)$ but $7^{7918/2}$, $7^{7918/37}$, $7^{7918/107} \not\equiv 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 Mathematica ${}^{\scriptstyle\circledRsymbol}$ (Wolfram Research, Champaign, IL) task ProvablePrime[n] 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, Primality Certificate, Witness

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.