Veja Primality certificate na Wikipedia.
V. Pratt, "Every prime has a succinct certificate", SIAM Journal on Computing 4 (1975), p.214-220.
(A ideia é que um inteiro ímpar n > 2 é primo se e somente se existe um inteiro x entre 1 e n−1 tal que xn−1 mod n = 1 e x(n−1)/p mod n ≠ 1 para todo divisor primo p de n−1.)