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


A propósito, descobriu-se recentemente um algoritmo polinomial capaz de decidir se um número natural é primo ou não.

Valid HTML 4.01 Strict Valid CSS!