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 ; par contre, 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 FermatModifier

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 : en effet, si   non premier, considérons un diviseur non trivial   de  . On a  , et pour tout  ,   est divisible par  , donc  , donc  .

Par contre, si on fixe la base  , il se peut que   sans que   ne soit premier; un tel nombre est dit pseudo-premier de Fermat de base  . D'après la remarque précédente, il n'existe pas de nombre   qui soit pseudo-premier de Fermat pour toute base   .


Une conséquence du petit théorème de Fermat est que, lorsque   est premier,   pour tout  . Cette fois, la réciproque est fausse, par exemple :  n'est pas premier et pourtant, pour tout entier a < 561, on a  . Les nombres p qui font échouer la réciproque sont appelés nombres de Carmichaël, et forment un ensemble infini.

Test de primalitéModifier

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
             retourner oui (N est probablement premier)
     sinon
             retourner non (N est composé)

Le calcul de aN-1 se fait avec un algorithme d'exponentiation modulaire. Cormen et al. (voir p. 889 de [2]) 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
             retourner oui (N est probablement premier)
     sinon
             retourner non (N est composé)


Taux d'erreurModifier

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 [2]). La probabilité que cet algorithme fasse une erreur sur un entier N tend vers 0 quand le nombre de bits de N tend vers 0 (voir p. 890 dans [2]). Pomerance a étudié une estimation précise des nombres pseudo-premiers de Fermat[3], que Cormen et al. (voir p. 890 dans [2]) 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 échoue le 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 : aN-1 ≡ 1 mod N}. On a |B| < N-1. C'est un sous-groupe strict du groupe multiplicatif  . Par le théorème de Lagrange,  . 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
             retourner oui (N est probablement premier)
     sinon
             retourner non (N est composé)

Génération de nombres premiersModifier

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

Test PGPModifier

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.

HistoireModifier

Voir aussiModifier

Notes et référencesModifier

  1. a b c d e et f (en) Sanjoy Dasgupta, Christos Papadimitriou et Umesh Vazirani, Algorithms, McGraw-Hill,
  2. 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
  3. (en) Carl Pomerance, « On the distribution of pseudoprimes », Mathematics of computation,‎ (lire en ligne)