Test de primalité de Fermat

Si le test de Fermat échoue, alors le nombre est composé. Si le test réussit, il y a de fortes chances que le nombre soit premier (illustration inspirée de , p. 30).

En algorithmique, le test de primalité de Fermat est un test de primalité probabiliste basé sur le petit théorème de Fermat. Il est de type Monte-Carlo : s'il détecte qu'un nombre est composé alors il a raison ; en revanche, il peut se tromper s'il prétend que le nombre est premier.

Petit théorème de Fermat

Le petit théorème de Fermat s'énonce en termes de congruence sur les entiers :

Théorème — si p est un nombre premier alors pour tout $1\leq a<p$, $a^{p-1}\equiv 1{\bmod {p}}$ (i.e. $a^{p-1}-1$ est divisible par p)

La réciproque du théorème est vraie : en effet, si $p$ non premier, considérons un diviseur non trivial $d$ de $p$. On a $1<d<p$, et pour tout $k\in \mathbb {Z}$, $d^{p-1}-kp$ est divisible par $d$, donc $d^{p-1}-kp\neq 1$, donc $d^{p-1}\not \equiv 1\mod p$.

Par contre, si on fixe la base $a$, il se peut que $a^{p-1}\equiv 1\mod p$ sans que $p$ ne soit premier; un tel nombre est dit pseudo-premier de Fermat de base $a$. D'après la remarque précédente, il n'existe pas de nombre $p$ qui soit pseudo-premier de Fermat pour toute base $1\leq a<p$ .

Une conséquence du petit théorème de Fermat est que, lorsque $p$ est premier, $a^{p}\equiv a\mod p$ pour tout $1\leq a<p$. Cette fois, la réciproque est fausse, par exemple :$561=3\times 11\times 17$ n'est pas premier et pourtant, pour tout entier a < 561, on a $a^{561}\equiv a\mod 561$. Les nombres p qui font échouer la réciproque sont appelés nombres de Carmichaël, et forment un ensemble infini.

Test de primalité

Le test de primalité de Fermat repose sur l'idée suivante  : si p est composé, alors il est peu probable que a^p–1 soit congru à 1 modulo p pour une valeur arbitraire de a. Voici un pseudo-code pour le test de Fermat, comme présenté par Dasgupta et al. :

fonction testPrimaliteFermat(N)
     choisir un entier positif a < N au hasard
     si aN-1 ≡ 1 mod N alors
             retourner oui (N est probablement premier)
     sinon
             retourner non (N est composé)

Le calcul de a^N-1 se fait avec un algorithme d'exponentiation modulaire. Cormen et al. (voir p. 889 de ) ne donne l'algorithme que pour a = 2 et appelle pseudo-premier de base 2 un nombre N composé qui passe le test suivant :

fonction testPrimaliteFermat2(N)
     si 2N-1 ≡ 1 mod N alors
             retourner oui (N est probablement premier)
     sinon
             retourner non (N est composé)

Taux d'erreur

Pour le test testPrimaliteFermat2 (uniquement avec a = 2), il n'existe que 22 valeurs de N inférieures à 10000 pour lesquelles le test se trompe. Les premières valeurs sont 341, 561, 645 et 1105 (A001567, voir p. 890 dans ). La probabilité que cet algorithme fasse une erreur sur un entier N tend vers 0 quand le nombre de bits de N tend vers 0 (voir p. 890 dans ). Pomerance a étudié une estimation précise des nombres pseudo-premiers de Fermat, que Cormen et al. (voir p. 890 dans ) résume par :

• un nombre de 512 bits déclaré premier par l'algorithme avec a = 2, a 1 chance sur 10²⁰ de ne pas être premier (i.e. d'être pseudo-premier de Fermat de base 2) ;
• un nombre de 1024 bits déclaré premier par l'algorithme avec a = 2 a 1 chance sur 10⁴¹ de ne pas être premier (i.e. d'être pseudo-premier de Fermat de base 2).

Pour le test testPrimaliteFermat, si un nombre N échoue le test de Fermat pour une certaine valeur de a, alors il échoue pour au moins la moitié des choix de a (cf. p. 26 dans ). Pour le voir, considérons l'ensemble B des valeurs de a qui n'échouent pas, i.e. B = {a : a^N-1 ≡ 1 mod N}. On a |B| < N-1. C'est un sous-groupe strict du groupe multiplicatif $(\mathbb {Z} /N\mathbb {Z} )^{\times }$. Par le théorème de Lagrange, $|B|\leq {\frac {N-1}{2}}$. Ainsi, en itérant k fois le test de Fermat de la façon suivante, la probabilité de retourner "oui" si N est composé est plus petite que 1/2^k.

fonction testPrimaliteFermatItere(N)
     choisir k entiers positifs a1, ... ak < N au hasard
     si aiN-1 ≡ 1 mod N pour tout i = 1, ..., k alors
             retourner oui (N est probablement premier)
     sinon
             retourner non (N est composé)

Génération de nombres premiers

Dasgupta et al. (cf. p. 28 dans ) argumente le fait d'utiliser un test de primalité pour générer des nombres premiers.L'algorithme fonctionne suit :

• Choisir un nombre N de n bits aléatoirement ;
• Lancer un test de primalité
• Si le test réussit, afficher N sinon recommencer le processus.

A chaque itération, il y a 1/n chances de s'arrêter. Ainsi, la procédure s'arrête en O(n) étapes. Selon Dasgupta et al. (cf. p. 30 dans ), le test de Fermat avec a = 2 permet de générer des nombres premiers, avec une erreur de 10^-5 pour des nombres N < 25 × 10⁹.

Test PGP

Le logiciel de chiffrement PGP (Pretty Good Privacy) tire profit^{[réf. nécessaire]} 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

$1\equiv 2^{x-1}\equiv 3^{x-1}\equiv 5^{x-1}\equiv 7^{x-1}{\bmod {x}}$, 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 de façon certaine 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.

Voir aussi

• Test de primalité de Miller-Rabin