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 
. 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 
is a positive integer
and 
is the set of prime factors
of 
.
Suppose there exists an integer 
(called a "witness")
such that 
but 
(mod 
)
whenever 
is one of 
.
Then Fermat's little theorem converse
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. Stated another way, the Pratt certificate gives a proof
that a number 
is a primitive root of the multiplicative group
(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 are witnesses
to the numbers to left. The set 
for 
is given by 
. Since 
but 
, 
, 
(mod 7919), 7 is a witness
for 7919. The prime divisors of 
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 
, the method of Pratt certificates
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 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 (
by default), and a Pratt certificate for smaller numbers.
