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 ^[1], 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[modifier | modifier le code]

Article détaillé : 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 $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 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 $a^{p-1}\not \equiv 1{\bmod {p}}$ ^[2].

Si on fixe $a$ , il se peut que $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 $p$ est premier, $a^{p}\equiv a{\bmod {p}}$ pour tout entier $a$ . Les nombres de Carmichael sont aussi les nombres composés vérifiant $a^{p}\equiv a{\bmod {p}}$ pour tout $a$ (on peut se restreindre à $1 < a < p$ ).

Test de primalité[modifier | modifier le code]

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 a^N-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 2^N-1 ≡ 1 mod N alors
             renvoyer oui (N est probablement premier)
     sinon
             renvoyer non (N est composé)

Taux d'erreur[modifier | modifier le code]

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. $B=\{a\mid a^{N-1}\equiv 1\mod N\}$ . C'est un sous-groupe strict du groupe multiplicatif $(\mathbb {Z} /N\mathbb {Z} )^{\times }$ (car N n'est pas un nombre de Carmichael). Par le théorème de Lagrange, $|B|\leq {\frac {\varphi (N)}{2}}\leq {\frac {N-1}{2}}$ (où $\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 a₁, ... a_k < N au hasard
     si a_i^N-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[modifier | modifier le code]

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[modifier | modifier le code]

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.

Histoire[modifier | modifier le code]

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

Voir aussi[modifier | modifier le code]

Test de primalité de Miller-Rabin

Notes et références[modifier | modifier le code]

↑ ^{a b c d e et f} (en) Sanjoy Dasgupta, Christos Papadimitriou et Umesh Vazirani, Algorithms, McGraw-Hill, 2008
↑ ^{a et b} Demazure 2008, p. 66-67.
↑ ^{a b c et d} Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, et Clifford Stein, Introduction à l'algorithmique, 1176 p., Section 31.2
↑ (en) Carl Pomerance, « On the distribution of pseudoprimes », Mathematics of computation,‎ 1981 (lire en ligne)

Bibliographie[modifier | modifier le code]

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

[:2-1] {a b c d e et f} (en) Sanjoy Dasgupta, Christos Papadimitriou et Umesh Vazirani, Algorithms, McGraw-Hill, 2008

[Demazure200866-67-2] {a et b} Demazure 2008, p. 66-67.

[:0-3] {a b c et d} 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)

[1]

[2]

[3]

[4]