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[1].
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.
O pequeno teorema de Fermat afirma que se p é primo e a é coprimo com p, então é divisível por p. Um inteiro composto n tal que n divide é chamado pseudoprimo de Fermat na base a[2]. 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[3].
