Test de primalité de Fermat

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.

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 ^[1], p. 30).

Petit théorème de Fermat

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

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

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

Si on fixe a, il se peut que ${\displaystyle a^{p-1}\equiv 1{\bmod {p}}}$ sans que p ne soit premier ; un tel nombre a est nécessairement premier avec p. Le nombre p est dit alors pseudo-premier de Fermat de base a. Un nombre p qui est pseudo-premier pour toute base a telle que a est premier avec p, est appelé nombre de Carmichael (on peut se restreindre à 1 < a < p). 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 ${\displaystyle p}$ est premier, ${\displaystyle a^{p}\equiv a{\bmod {p}}}$ pour tout entier a. Les nombres de Carmichael sont aussi les nombres composés vérifiant ${\displaystyle a^{p}\equiv a{\bmod {p}}}$ pour tout a (on peut se restreindre à 1 < a < p).

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.^[1] :

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 ^[3]) 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 ^[3]). 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 ^[3]). Pomerance a étudié une estimation précise des nombres pseudo-premiers de Fermat^[4], que Cormen et al. (voir p. 890 dans ^[3]) 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 ^[1]). Pour le voir, considérons l'ensemble B des valeurs de a qui n'échouent pas, i.e. ${\displaystyle B=\{a\mid a^{N-1}\equiv 1\mod N\}}$. C'est un sous-groupe strict du groupe multiplicatif ${\displaystyle (\mathbb {Z} /N\mathbb {Z} )^{\times }}$ (car N n'est pas un nombre de Carmichael). Par le théorème de Lagrange, ${\displaystyle |B|\leq {\frac {\varphi (N)}{2}}\leq {\frac {N-1}{2}}}$ (où ${\displaystyle \varphi }$ 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 ^[1]) 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 ^[1]), 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

${\displaystyle 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.

Histoire

Voir aussi

• Test de primalité de Miller-Rabin

Notes et références

1. (en) Sanjoy Dasgupta, Christos Papadimitriou et Umesh Vazirani, Algorithms, McGraw-Hill, 2008
2. Demazure 2008, p. 66-67.
3. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, et Clifford Stein, Introduction à l'algorithmique, 1176 p., Section 31.2
4. (en) Carl Pomerance, « On the distribution of pseudoprimes », Mathematics of computation,‎ 1981 (lire en ligne)

Bibliographie

• Michel Demazure, Cours d'algèbre : Primalité. Divisibilité. Codes., 2008 [détail de l’édition] ;

• Portail des mathématiques
• Portail de l'informatique théorique