Número pseudoprimo

Um pseudoprimo é um número primo provável (um inteiro que partilha propriedades com os números primos) que não é verdadeiramente primo. Pseudoprimos são classificados de acordo com a propriedade dos primos que satisfazem.

Pseudoprimos têm importância primária na criptografia de chave pública, em algoritmos que utilizam números primos grandes em seu funcionamento, e em geral se baseiam no grande custo computacional de fatorar inteiros. Muitas vezes encontrar números primos grandes deterministicamente também é um problema de custo computacional elevado, e portanto podem ser usados testes de primalidade probabilísticos, que em raros casos dão falsos positivos, identificando números compostos como primos. Tais números são classificados como pseudoprimos em relação a este teste.

Pseudoprimo de Fermat

O pequeno teorema de Fermat afirma que se p é primo e a é coprimo com p, então $a^{p-1}-1$ é divisível por p. Um inteiro composto n tal que n divide $a^{n-1}-1$ é chamado pseudoprimo de Fermat na base a. Segue do fato de que n é pseudoprimo na base a que n e a são coprimos. Um inteiro n pseudoprimo de Fermat na base a para todo a coprimo com n é chamado número de Carmichael.