Certificado de primalidade

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 xⁿ⁻¹ mod n = 1 e x^(n−1)/p mod n ≠ 1 para todo divisor primo p de n−1.)

(A propósito, existe um algoritmo polinomial capaz de decidir se um número natural é primo ou não.)