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 conforme 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 Predefinição:Mvar é primo e a é coprimo com Predefinição:Mvar, então $a^{p-1}-1$ é divisível por Predefinição:Mvar. Um inteiro composto Predefinição:Mvar tal que Predefinição:Mvar divide $a^{n-1}-1$ é chamado pseudoprimo de Fermat na base a. Segue do fato de que Predefinição:Mvar é pseudoprimo na base a que Predefinição:Mvar e a são coprimos. Um inteiro Predefinição:Mvar pseudoprimo de Fermat na base a para todo a coprimo com Predefinição:Mvar é chamado número de Carmichael.