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.

Petit théorème de Fermat 

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

La réciproque du théorème est vraie car si  n'est pas premier, un diviseur non trivial  de , plus généralement un  non premier avec , n'est pas inversible modulo , donc ne peut a fortiori avoir une puissance congrue à 1 modulo . Mais les témoins de non primalité réellement apportés par le théorème de Fermat sont les  premiers avec  tels que .

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

Test de primalité 

Le test de primalité de Fermat repose sur l'idée suivante   : si  est composé, alors il est peu probable que  soit congru à  modulo  pour une valeur arbitraire de . 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
              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 ) 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 ). 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 ). 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 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 ). 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 
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 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 ), 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.

Test PGP 
Le logiciel de chiffrement PGP (Pretty Good Privacy) tire profit 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  en utilisant quatre valeurs de  (appelées témoins) en employant la formule ci-dessus. Ces quatre valeurs sont , ,  et , les quatre premiers nombres premiers.

Si
, alors nous savons que le nombre  est probablement premier.

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

Bibliographie 
  ;

Fermat
Pierre de Fermat