Test de primalité de Miller-Rabin

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Le test de primalité de Miller-Rabin est un test de primalité probabiliste, de type Monte Carlo : étant donné un nombre entier, il donne une réponse oui/non qui permet de conclure soit de façon certaine que celui-ci est composé, soit qu'il est probablement premier. La probabilité, qu'un nombre choisi aléatoirement, soit déclaré premier alors qu'il est en réalité composé peut être rendue aussi faible que souhaité, en fonction des paramètres d'entrées de l'algorithme. En cela il est analogue au test de primalité de Solovay-Strassen, mais cependant toujours plus efficace que ce dernier.

Sa version originale, due à Gary L. Miller, est déterministe, mais ce déterminisme dépend de l'hypothèse de Riemann généralisée (qui n'est pas démontrée) ; Michael Rabin l'a modifiée pour obtenir un algorithme probabiliste inconditionnel.

Le test de Miller-Rabin est très utilisé en cryptographie asymétrique pour engendrer les grands nombres premiers nécessaires pour le chiffrement RSA, et pour beaucoup des utilisations du chiffrement El Gamal ou de l'échange de clés Diffie-Hellman.

Principes mathématiques[modifier | modifier le code]

De la même façon que les tests de primalité de Fermat ou de Solovay-Strassen, celui de Miller-Rabin tire parti d'une propriété de l'entier n, qui dépend d'un entier auxiliaire, le témoin, et qui est vraie dès que n est un nombre premier. Le principe du test est de vérifier cette propriété pour « suffisamment » de témoins.

Dans le cas du test de Miller-Rabin, la propriété en question est un raffinement du petit théorème de Fermat (utilisé pour le test de Fermat), s'appuyant sur le fait que dans un corps, ce qui est le cas de ℤ/p si p est premier, l'équation X2 = 1 n'a pour solutions que 1 et -1, soit en termes de congruences, les seuls entiers dont le carré est congru à 1 modulo un nombre premier p sont eux-mêmes congrus à 1 ou à -1 modulo p. On déduit alors du petit théorème de Fermat que :

Proposition.— Soit p > 2 un nombre premier, soient s et d les deux entiers naturels, s non nul et d impair, vérifiant p − 1 = 2s × d (s est le nombre maximum de fois que l'on peut mettre 2 en facteur dans p − 1). Alors, pour tout entier a qui n'est pas divisible par p  :

En effet, d'après le petit théorème de Fermat,

et en prenant de façon répétée des racines carrées à partir de ap − 1, on obtient soit toujours 1 modulo p, jusqu'à ad ≡ 1 mod p, soit pour un certain 0 ≤ r < s, ad 2 r ≡ -1 mod p (ad 2 i ≡ 1 mod p pour r< is), seule autre racine carrée possible de 1 selon ce qui précède.

Par contraposition, si : alors n est composé, et a est appelé un témoin de Miller pour le fait que n est composé.

A contrario, si la conclusion de la proposition est réalisée, n n'est pas nécessairement premier. On dit alors que n est fortement probablement premier en base a. Lorsque n n'est pas premier mais pourtant fortement probablement premier en base a, on dit que a est un menteur fort (pour n premier), et que n est fortement pseudo-premier en base a.

Le nombre a peut être choisi sans perte de généralité inférieur à n, plus précisément 1 < a < n. Le test de Miller-Rabin s'appuie sur le fait que, contrairement au test de Fermat, non seulement un nombre composé possède toujours un témoin de Miller —c'est-à-dire que l'équivalent des nombres de Carmichael n'existe pas pour le test de Miller Rabin —, mais de plus :

Proposition.— Pour un nombre impair composé n, 3/4 au moins des entiers a, 1 < a < n, sont des témoins de Miller pour n.

Il suffit donc de répéter le test pour suffisamment d'entiers a choisis indépendamment, pour que la probabilité qu'un entier n composé soit déclaré premier devienne très faible.

Cette dernière proposition est un corollaire du théorème suivant, publié par Rabin en 1980 (et indépendamment la même année par Monier)[1].

Théorème de Rabin.— Soit n un entier impair composé > 9, avec n -1 = 2s × d pour d impair. Alors il existe au plus φ(n)/4 menteurs forts a, pour 1 < a < n, c'est-à-dire des entiers a dans cet intervalle vérifiant soit ad ≡ 1 mod n, soit, ad 2 r ≡ -1 mod n pour un certain r tel que 0 ≤ r < s (φ est la fonction indicatrice d'Euler)[2].

Algorithme et temps d'exécution[modifier | modifier le code]

La recherche d'un témoin de Miller peut se décrire algorithmiquement de la façon suivante, l'affectation est notée « := » , Témoin_de_Miller(a, n) renvoie Vrai si a est un témoin de Miller que n est composé, Faux si n est fortement pseudo-premier en base a :

Témoin_de_Miller(a, n):                                     entrées : n un entier impair ≥ 3, a un entier > 1
     calculer s et d tels que n - 1 = 2s×d  avec d impair  s > 0 car n impair
     x := ad % n    x entier reste de la division de ad par n
     si x = 1 ou x = n - 1
       renvoyer(Faux)                                       sortie : a n'est pas un témoin de Miller
     Tant que s > 1
          x := x2 % n    reste de la division de x2 par n
          si x = n - 1
            renvoyer(Faux)                                  sortie : a n'est pas un témoin de Miller
          s := s - 1
     Fin de boucle tant que
     renvoyer(Vrai)                                         a est un témoin de Miller, n est composé

Le test de Miller-Rabin peut alors être décrit comme suit, Miller-Rabin(n, k) renvoie Vrai si n est fortement pseudo-premier en base a pour k entiers a, Faux s'il est composé.

Miller-Rabin(n,k):                                          entrées : n un entier impair ≥ 3, k un entier ≥ 1
   répéter k fois :
      choisir a aléatoirement dans l'intervalle [2, n – 2]
      si Témoin_de_Miller(a,n)
        renvoyer(Faux)                                      sortie, n est composé
   Fin de boucle répéter
   renvoyer(Vrai)                                           sortie, n est probablement premier si k est suffisamment grand

La décomposition n - 1 = 2sd, d impair se calcule en O(log(n)) par une boucle simple. Ce calcul pourrait être factorisé pour être effectué une seule fois dans le test de Miller-Rabin.

Le calcul du reste de la division ad par n puis les élévations au carré successives sont des calculs d'exponentiation modulaire. Par exponentiation rapide, le calcul se fait en O((log d)(log n)2) pour le calcul initial, suivi de s (≤ log(n)) élévations au carré en O((log n)2). Le temps de calcul du premier algorithme, le test que a est ou non un témoin de Miller pour n est donc[3] en O((log n)3). Le temps de calcul du test de Miller-Rabin est donc en O(k(log n)3) ; ainsi cet algorithme est en temps polynomial et efficace.

La multiplication rapide FFT peut abaisser le temps d'exécution à Õ(k × log2 n).

Exemples[modifier | modifier le code]

561 -1 = 560 = 35×24
0 235 263 mod 561 335 78 mod 561 5035 560 mod 561
1 2632 166 mod 561 782 474 mod 561
2 1662 67 mod 561 4742 276 mod 561
3 672 1 mod 561 2762 441 mod 561
2 est un témoin de Miller 3 est un témoin de Miller 50 est un menteur fort
On observe que 2 est un témoin de Miller, ce qui suffit pour assurer que 561 est composé ; 3 est également un témoin de Miller. Le nombre 50 est un menteur fort.
  • Le nombre 1373653 est le plus petit nombre composé qui n'a ni 2 ni 3 pour témoin de Miller (suite A014233 de l'OEIS) :
1373653 - 1 = 1373652 = 343413×22
0 2343413 890592 mod 1373653 3343413 1 mod 1373653 5343413 1199564 mod 1373653
1 8905922 1373652 mod 1373653 11995642 73782 mod 1373653
2 est un menteur fort 3 est un menteur fort 5 est un témoin de Miller
Le nombre 5 est un témoin de Miller et donc 1373653 est composé.

Probabilité d'erreur et nombre d'itérations[modifier | modifier le code]

Le théorème de Rabin permet de montrer que la probabilité qu'un nombre composé impair de p bits (compris pris entre 2p - 1 et m = 2p), soit déclaré probablement premier par l'algorithme de Miller-Rabin pour k nombres a tirés aléatoirement est inférieure à 4k. C'est une probabilité conditionnelle (n est déclaré probablement premier sachant qu'il est composé). Pour la fiabilité de l'algorithme on s'intéresse plutôt à celle de produire un faux positif, c'est-à-dire à la probabilité que l'algorithme déclare premier un nombre composé, qui est une autre probabilité conditionnelle (n est composé sachant que l'algorithme termine sur Vrai). Pour l'évaluer, la première probabilité (n déclaré probablement premier sachant qu'il est composé) est à comparer avec la probabilité pour un nombre impair quelconque de p bits d'être premier qui est de l ordre de 2/ln(m) quand m est suffisamment grand, par le théorème des nombres premiers[4]. Ceci donne, pour k suffisamment grand pour que 4k soit négligeable devant 2/ln(m), une probabilité qu'un nombre de p bits soit composé, sachant que l'algorithme le déclare premier, de l'ordre de[5] ln(m)/(2×4k). Cette probabilité, celle que l'algorithme déclare faussement un nombre premier, devient rapidement très faible quand k augmente.

Il s'avère que dans beaucoup de cas un nombre composé possède nettement plus de 3 témoins de Miller sur 4, et le résultat précédent peut être fortement amélioré. On peut montrer par exemple que la probabilité que l'algorithme déclare faussement premier un nombre de p bits, est en réalité[6] inférieure à 4k.

Pour un grand nombre de bits, cette borne peut encore être améliorée : la probabilité qu'un seul test de Miller-Rabin déclare faussement premier un nombre de p bits est inférieure à p242 − √p, et cette borne peut être encore plus faible pour certaines valeurs de p[7].

Versions déterministes[modifier | modifier le code]

L'algorithme original de Miller est déterministe, mais repose sur l'hypothèse de Riemann généralisée, plus précisément si l'hypothèse de Riemann généralisée est vraie, alors le plus petit témoin de Miller pour un nombre impair composé n est strictement inférieur[8] à 2(ln n)2. Ceci donne immédiatement un algorithme déterministe polynômial pour tester la primalité, en itérant dans l'algorithme de Rabin-Miller sur tous les entiers < 2(ln n)2. Cependant outre que la validité de cet algorithme repose sur une hypothèse non démontrée, il existe d'autres tests déterministes plus efficaces en pratique. Par ailleurs, sur le plan théorique, on sait depuis, sans utiliser d'hypothèse non démontrée, que la primalité est un problème polynomial, par le test de primalité AKS.

Pour certaines bases, on a calculé le plus petit entier composé dont un test de Miller-Rabin utilisant ces bases ne détecte pas qu'il est premier, ce qui fournit un test déterministe jusqu'à ce nombre. Ainsi la suite A014233 de l'OEIS donne en fonction de n le plus petit entier impair composé dont les n premiers entiers premiers ne sont pas des témoins de Miller.

On obtient par exemple un test déterministe pour un entier qui s'écrit sur 64 bits par le test de Miller-Rabin en prenant pour base les 12 premiers entiers premiers, soit 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37.

Utilisation[modifier | modifier le code]

Le test de Miller-Rabin est très utilisé en cryptographie pour produire les nombres premiers nécessaires, pour les chiffres aymétriques en particulier le RSA, mais aussi ceux reposant sur le problème du logarithme discret dans le groupe multiplicatif d'un corps fini premier. La taille des nombres premiers dont on a besoin a augmenté avec les progrès des attaques et des moyens de calcul. Dans une recommandation du NIST de 2013, les tailles des nombres premiers utiles sont toujours au delà de 100 bits et vont jusqu'à 3072 bits[9].

Une question est de déterminer le nombre d'itérations de l'algorithme, c'est-à-dire le nombre k d'entiers a dont on va tester qu'ils ne sont pas des témoins de Miller. Par exemple le manuel de la bibliothèque GMP (version 6.0.0) recommande de prendre k = 25, pour obtenir une probabilité d'erreur inférieure à 2-50 (~10-15)[10].

Le nombre d'itérations dépend de la façon dont le nombre à tester a été obtenu : s'agit-il de tester un nombre produit aléatoirement ou de vérifier un nombre dont on ignore comment il a été produit (possiblement pour tromper certains tests) ? L'utilisation d'un nombre qui n'est pas réellement premier n'a pas forcément des conséquences importantes. Ainsi dans le chiffrement RSA, utiliser pour le module un produit de nombres qui ne sont pas premiers peut produire une erreur lors des opérations de chiffrement/déchiffrement, erreur qui assure d'ailleurs qu'il y a un problème de primalité, mais pas révéler un secret. De plus un nombre très grand dont on sait qu'il est produit aléatoirement peut requérir moins d'itérations (voir #Probabilité d'erreur et nombre d'itérations). On trouve diverses valeurs, qui dépendent de l'utilisation, dans les recommandations du NIST de 2013 qui vont de 3, pour des entiers premiers de 1536 bits utilisés pour produire un module RSA de 3072 bits, à 64 pour des nombres de 3072 et 256 bits utilisés pour un schéma de signature DSA, fondé sur un chiffrement de type El Gamal[9].

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

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Miller–Rabin primality test » (voir la liste des auteurs).

  1. Crandall et Pomerance 2001, p. 125.
  2. Pour une démonstration voir par exemple Demazure 2008, p. 94-97, ou Crandall et Pomerance 2001, p. 125-128.
  3. Demazure 2008, p. 69, voir aussi p 28 pour la définition du « modèle à coûts bilinéaires » d'évaluation des coûts des opérations élémentaires, qui prend sens pour le calcul sur les grands entiers, en particulier la multiplication de m et n est supposé avoir un coût en 0((log m)(log n)). Voir également p 31 pour l'exponentielle modulaire.
  4. Crandall et Pomerance 2001, p. 127.
  5. Un calcul analogue est détaillé dans Delahaye 2000, p. 310.
  6. Crandall et Pomerance 2001, p. 127, citant (en) Ronald Joseph Burthe, « Further investigations with the strong probable prime test », Mathematics of computation, vol. 65, no 213,‎ , p. 373-381 (DOI 10.1090/S0025-5718-96-00695-3).
  7. Crandall et Pomerance 2001, p. 127, d'après I. Damgård, P. Landrock et C. Pomerance, « Average case error estimates for the strong probable prime test », Mathematics of Computation, vol. 61, no 203,‎ , p. 177–194 (DOI 10.2307/2152945, lire en ligne), où l'on trouve des calculs explicites pour certaines valeurs du nombre de bits.
  8. Crandall et Pomerance 2001, p. 127, cette borne, avec une constante meilleure que celle originale de Miller, a été obtenue en 1985 par Eric Bach.
  9. a et b Les recommandations du NIST sont décrites dans le standard FIPS 186-4, p 69-71.
  10. GNU MP 6.0.0 Manual, Number Theoretic Functions.

Bibliographie[modifier | modifier le code]

Liens externes[modifier | modifier le code]

(en) Eric W. Weisstein, « Rabin-Miller Strong Pseudoprime Test », MathWorld