Test de primalité de Fermat

Fichier:TestDeFermat.svg

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 <ref name=":2" />, 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<ref name=":2" /> : Modèle:Théorème

La réciproque du théorème est vraie car si Modèle:Mvar n'est pas premier, un diviseur non trivial Modèle:Mvar de Modèle:Mvar, plus généralement un Modèle:Mvar non premier avec Modèle:Mvar, n'est pas inversible modulo Modèle:Mvar, donc ne peut a fortiori avoir une puissance congrue à 1 modulo Modèle:MvarModèle:Sfn. Mais les témoins de non primalité réellement apportés par le théorème de Fermat sont les Modèle:Mvar premiers avec Modèle:Mvar tels que <math>a^{p-1} \not\equiv 1 \bmod p</math>Modèle:Sfn.

Si on fixe Modèle:Mvar, il se peut que <math>a^{p-1} \equiv 1 \bmod p</math> sans que Modèle:Mvar ne soit premier ; un tel nombre Modèle:Mvar est nécessairement premier avec Modèle:Mvar. Le nombre Modèle:Mvar est dit alors pseudo-premier de Fermat de base Modèle:Mvar. Un nombre Modèle:Mvar qui est pseudo-premier pour toute base Modèle:Mvar telle que Modèle:Mvar est premier avec Modèle:Mvar, est appelé nombre de Carmichael (on peut se restreindre à Modèle:Math). Les nombres de Carmichael sont « rares » mais il en existe une infinité.

Une conséquence du petit théorème de Fermat est que, lorsque <math>p</math> est premier, <math>a^p \equiv a \bmod p</math> pour tout entier Modèle:Mvar. Les nombres de Carmichael sont aussi les nombres composés vérifiant <math>a^p \equiv a \bmod p</math> pour tout Modèle:Mvar (on peut se restreindre à Modèle:Math).

Test de primalité

Le test de primalité de Fermat repose sur l'idée suivante  : si Modèle:Mvar est composé, alors il est peu probable que Modèle:Math soit congru à Modèle:Math modulo Modèle:Mvar pour une valeur arbitraire de Modèle:Mvar. Voici un pseudo-code pour le test de Fermat, comme présenté par Dasgupta et al.<ref name=":2">Modèle:Ouvrage</ref> :

fonction testPrimaliteFermat(N)
     choisir un entier positif a < N au hasard
     si aN-1 ≡ 1 mod N alors
             renvoyer oui (N est probablement premier)
     sinon
             renvoyer 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 <ref name=":0">Modèle:Ouvrage</ref>) 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
             renvoyer oui (N est probablement premier)
     sinon
             renvoyer 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 <ref name=":0" />). La probabilité que cet algorithme fasse une erreur sur un entier N tend vers 0 quand le nombre de bits de N tend vers +∞ (voir p. 890 dans <ref name=":0" />). Pomerance a étudié une estimation précise des nombres pseudo-premiers de Fermat<ref>Modèle:Article</ref>, que Cormen et al. (voir p. 890 dans <ref name=":0" />) 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 qui n'est pas un Nombre de Carmichael échoue au 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 <ref name=":2" />). Pour le voir, considérons l'ensemble B des valeurs de a qui n'échouent pas, i.e. <math>B = \{a \mid a^{N-1}\equiv 1 \mod N\}</math>. C'est un sous-groupe strict du groupe multiplicatif <math>(\mathbb Z / N \mathbb Z)^\times</math> (car N n'est pas un nombre de Carmichael). Par le théorème de Lagrange, <math>|B| \leq \frac{\varphi(N)}2\leq \frac{N-1}2</math> (où <math>\varphi</math> désigne l'Indicatrice d'Euler). 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
             renvoyer oui (N est probablement premier)
     sinon
             renvoyer non (N est composé)

Génération de nombres premiers

Dasgupta et al. (cf. p. 28 dans <ref name=":2" />) argumente le fait d'utiliser un test de primalité pour générer des nombres premiers. L'algorithme fonctionne comme 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 <ref name=":2" />), 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 profitModèle:Référence 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 Modèle:Mvar en utilisant quatre valeurs de Modèle:Mvar (appelées témoins) en employant la formule ci-dessus. Ces quatre valeurs sont Modèle:Math, Modèle:Math, Modèle:Math et Modèle:Math, les quatre premiers nombres premiers.

Si

<math>1\equiv 2^{x-1}\equiv 3^{x-1}\equiv 5^{x-1}\equiv 7^{x-1}\bmod x</math>, alors nous savons que le nombre Modèle:Mvar est probablement premier.

Si l'une quelconque de ces équations donne une valeur autre que 1, alors Modèle:Mvar est de façon certaine composé. Utiliser des témoins supplémentaires diminue la chance qu'un nombre composé Modèle:Mvar 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

Bibliographie

• Modèle:Ouvrage ;