Test de primalité de Fermat
Un article de Wikipédia, l'encyclopédie libre.
Le petit théorème de Fermat affirme que si p est un nombre premier et si a est premier avec p, alors ap-1 - 1 est divisible par p. Ceci peut être aussi écrit
(pour mod voir arithmétique modulaire)
La réciproque de ce théorème est fausse, par exemple : 561=3×11×17 n'est pas premier et pourtant pour tout entier a premier avec 561, on a 
(voir les nombres de Carmichaël)
Mais nous pouvons tout de même écrire :
Si p est composé, alors ap − 1 est de façon improbable, congru à 1 modulo p pour une valeur arbitraire de a
ce qui représente une sorte de réciproque probabiliste du théorème.
Le programme de chiffrage PGP tire profit de cette propriété du théorème pour examiner si les grands nombres aléatoires qu'il choisit sont premiers. Il examine les valeurs que nous appellerons x en utilisant quatre valeurs de a (appelées témoins) en employant la formule ci-dessus. Ces quatre valeurs sont 2, 3, 5 et 7, les quatre premiers nombres premiers.
Si
, alors nous savons que le nombre x est probablement premier.
Si l'une quelconque de ces équations donne une valeur autre que 1, alors x est définitivement composé. Utiliser des témoins supplémentaires diminue la chance qu'un nombre composé x soit considéré premier, bien que très peu de grands nombres puissent duper les 4 témoins.
L'article sur les nombres pseudopremiers donne une explication détaillée sur les nombres qui dupent les tests de primalité de ce type.
