Test de primalité de Fermat — Wikipédia

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]

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 , (i.e. 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 [2].

Si on fixe a, il se peut que 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 est premier, pour tout entier a. Les nombres de Carmichael sont aussi les nombres composés vérifiant 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 ap–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 aN-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

[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 1020 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 1041 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. . C'est un sous-groupe strict du groupe multiplicatif (car N n'est pas un nombre de Carmichael). Par le théorème de Lagrange, (où 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/2k.

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

[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 × 109.

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

, 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.

Notes et références

[modifier | modifier le code]
  1. a b c d e et f (en) Sanjoy Dasgupta, Christos Papadimitriou et Umesh Vazirani, Algorithms, McGraw-Hill,
  2. a et b Demazure 2008, p. 66-67.
  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,‎ (lire en ligne)

Bibliographie

[modifier | modifier le code]