En mathématiques, 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 pour conclure soit de façon certaine que celui-ci est composé, soit qu'il est probablementpremier. La probabilité qu'un nombre déclaré premier par l'algorithme soit 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 toujours plus efficace que ce dernier.
Comme 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.
Le test de Miller-Rabin étend le test de Fermat : la propriété est un raffinement du petit théorème de Fermat[1]. Elle s'appuie 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. Autrement dit, 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[2].— Soit p > 2 un nombre premier, soient s et d les deux entiers naturels, s non nul et dimpair, 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 :
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 2r ≡ –1 mod p (ad 2i ≡ 1 mod p pour r< i ≤ s), seule autre racine carrée possible de 1 modulo p (voir ci-dessus).
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.
Un témoin potentiel a peut être choisi sans perte de généralité entre 1 et 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[3] —, mais de plus :
Proposition[2].— 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é indépendamment par Michael Rabin et Louis Monier en 1980[4] (φ est la fonction indicatrice d'Euler) :
Théorème de Rabin[5].— 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 2r ≡ –1 mod n pour un certain r tel que 0 ≤ r < s[6].
Algorithme et temps d'exécution
Test d'un témoin
L'algorithme suivant permet de déterminer si un entier a est un témoin de Miller pour l'entier n[2],[7].
Témoin_de_Miller(n, a): 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 := admod n x entier reste de la division de ad par nsi x = 1 ou x = n - 1
renvoyer FauxFin d'exécution : a n'est pas un témoin de MillerRépéter s - 1 fois
x := x2mod n reste de la division de x2 par nsi x = n - 1
renvoyer FauxSortie de boucle et fin d'exécution: a n'est pas un témoin de MillerFin de boucle Répéterrenvoyer Vraia est un témoin de Miller, n est composé
La décomposition n – 1 = 2sd, d impair se calcule en O (log(n)) par une boucle simple : la représentation binaire de n – 1 est la représentation binaire de d, terminée par le bit 1 de poids le plus faible, suivie de s bits à 0. Ce calcul pourrait être effectué une seule fois dans le test de Miller-Rabin pour tous les appels à la procédure de test d'un témoin_de_Miller.
Le calcul du reste x0 de la division de ad par n puis les élévations au carré successives (pour calculer les xi = ad2i mod n) sont des calculs d'exponentiation modulaire. Par exponentiation rapide, le calcul se fait en O((log d)(log n)2) pour le calcul de ad, suivi d'au plus s (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[8] en O((log n)3).
Test de Miller-Rabin
Le test de Miller-Rabin[9],[10] est alors décrit par la procédure suivante : Miller-Rabin(n, k) renvoie « Vrai » si n est fortement pseudo-premier en base a pour k entiers a choisis aléatoirement, « Faux » s'il est composé. Quand Miller-Rabin(n, k) valide n pour un nombre k est suffisamment grand, le nombre n peut être déclaré premier avec une faible probabilité d'erreur (voir la section #Utilisation pour des exemples de valeur numérique).
Miller-Rabin(n,k): entrées : n un entier impair ≥ 3, k un entier ≥ 1répéter k fois :
choisir a aléatoirement dans l'intervalle [2, n – 1]
si Témoin_de_Miller(n,a)
renvoyer Fauxsortie de boucle, n est composéFin de boucle répéterrenvoyer Vrain est probablement premier (si k est suffisamment grand)
Le temps de calcul du test de Miller-Rabin est 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 × log2n).
Exemples
Le nombre composé 561 (divisible par 3) est le plus petit nombre de Carmichael. On a :
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
Le théorème de Rabin permet de montrer que la probabilité qu'un nombre composé impair m de p bits (compris pris entre m = 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 à 4−k. 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[11]. Ceci donne, pour k suffisamment grand pour que 4−k 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[12]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é[13] inférieure à 4−k.
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[14].
Versions déterministes
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[15] à 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.
Par exemple le test de Miller-Rabin devient déterministe pour un entier qui s'écrit sur 64 bits quand on prend pour bases les 12 premiers entiers premiers, soit 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37.
Utilisation
Le test de Miller-Rabin est très utilisé en cryptographie pour produire les nombres premiers nécessaires, pour les chiffres asymé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[16].
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)[17].
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[16].
↑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 O((log m)(log n)). Voir également p 31 pour l'exponentielle modulaire.
↑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 (DOI10.2307/2152945, lire en ligne), où l'on trouve des calculs explicites pour certaines valeurs du nombre de bits.
↑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.
↑ a et bLes recommandations du NIST sont décrites dans le standard FIPS 186-4, p 69-71.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein (trad. de l'anglais), Introduction à l'algorithmique : cours et exercices, Paris, Dunod, , 2e éd., 1146 p. (ISBN2-10-003922-9), chapitre 31 (Algorithmes de la théorie des nombres) ;
(en) Alfred J. Menezes, Paul C. van Oorschot et Scott A. Vanstone, Handbook of applied cryptography, Boca Raton, CRC Press, , 816 p. (ISBN0-8493-8523-7, lire en ligne) (chap. 4) ;
(en) Gary L. Miller, « Riemann's Hypothesis and Tests for Primality », Journal of Computer and System Sciences, vol. 13, no 3, , p. 300-317 (DOI10.1145/800116.803773) ;
(en) Michael O. Rabin, « Probabilistic algorithm for testing primality », Journal of Number Theory, vol. 12, no 1, , p. 128-138 (DOI10.1016/0022-314X(80)90084-0).
Seventh Mahathir cabinet20th Cabinet of Malaysia2018–2020Date formed21 May 2018Date dissolved24 February 2020People and organisationsHead of stateSultan Muhammad V 2018-2019Al-Sultan Abdullah 2019-2020Head of governmentDr. Mahathir MohamadDeputy head of governmentDr. Wan Azizah Wan IsmailNo. of ministers28 ministers and 27 deputy ministersMember parties PH PKR DAP BERSATU AMANAH WARISAN UPKO MAP Status in legislature Majority (coalition)139 / 222Opposition parties BN UMNO MCA MIC PAS GPS PBB P…
此條目需要补充更多来源。 (2021年7月4日)请协助補充多方面可靠来源以改善这篇条目,无法查证的内容可能會因為异议提出而被移除。致使用者:请搜索一下条目的标题(来源搜索:美国众议院 — 网页、新闻、书籍、学术、图像),以检查网络上是否存在该主题的更多可靠来源(判定指引)。 美國眾議院 United States House of Representatives第118届美国国会众议院徽章 众议院旗帜…
Public university in Covilhã, Portugal This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: University of Beira Interior – news · newspapers · books · scholar · JSTOR (August 2014) (Learn how and when to remove this message) University of Beira InteriorUniversidade da Beira InteriorMottoScientia et Labore Altiora P…
Canadian internet personality (born 1990) Cody KoKo in June 2023BornCody Michael Kolodziejzyk (1990-11-22) 22 November 1990 (age 33)Calgary, Alberta, CanadaOccupationsYouTuberpodcastercomedianrapperSpouse Kelsey Kreppel (m. 2023)Children1RelativesGreg Kolodziejzyk (father)Musical careerGenres Hip hop Years active2017–presentLabels Arista Records Member ofTiny Meat Gang Musical artistYouTube informationChannel Cody Ko Years active2014–presentGenres Com…
Untuk jenis makanan, lihat otak-otak. Untuk otak manusia dan otak hewan, lihat otak. Lingkungan Akihabara di Tokyo, sebuah lokasi berkumpul yang populer bagi otaku Bagian dari seri tentangAnime dan manga Anime Sejarah Industri Animasi net orisinal Animasi video orisinal Fansub Fandub Perusahaan Seri terpanjang Daftar Manga Sejarah Pasar internasional Mangaka Dōjinshi Scanlation Alternatif Gekiga Yonkoma Penerbit Seri terlaris Seri terpanjang Daftar Kelompok demografi Anak-anak Dewasa Shōnen Sh…
أروناجل برديش अरुणाचल प्रदेश Aruṇācal Pradeś (بالآسامية: অৰুণাচল প্ৰদেশ) الموقع الجغرافي تاريخ التأسيس 20 فبراير 1987 تقسيم إداري البلد الهند[1][2] العاصمة يتاناغار التقسيم الأعلى الهند خصائص جغرافية إحداثيات 27°04′N 93°22′E / 27.06°N 93.37°E …
BonabElectoral district constituencyfor the East AzerbaijanMalekan shown within East Azerbaijan ProvinceEast AzerbaijanMalekan CountyCurrent constituencyAssembly MembersSalman Khodadadi Malekan (electoral district) is the 9th electoral district in the East Azerbaijan Province of Iran. The district has 106,118 residents and elects one member of parliament. Malekan and Bonab were a joint electoral district from 1st to 5th Iranian legislative election and in just the first election returned two mem…
TV series or program Angry BoysGenre Mockumentary Sitcom Created byChris LilleyWritten byChris LilleyDirected by Chris Lilley Stuart McDonald Anthony Rose Jeffrey Walker StarringChris LilleyTheme music composerChris LilleyComposerBryony MarksCountry of origin Australia United States Original languageEnglishNo. of series1No. of episodes12ProductionExecutive producers Chris Lilley Debbie Lee Laura Waters Producers Chris Lilley Laura Waters Production locations Melbourne, Australia Los Angeles, Uni…
American politician and governor of Connecticut (1854–1925) Rollin S. Woodruff62nd Governor of ConnecticutIn officeJanuary 9, 1907 – January 6, 1909LieutenantEverett J. LakePreceded byHenry RobertsSucceeded byGeorge L. Lilley71st Lieutenant Governor of ConnecticutIn officeJanuary 4, 1905 – January 9, 1907GovernorHenry RobertsPreceded byHenry RobertsSucceeded byEverett J. LakeMember of the Connecticut SenateIn office1903 Personal detailsBornJuly 14, 1854Rochester, …
This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Military history of Luxembourg – news · newspapers · books · scholar · JSTOR (April 2024) (Learn how and when to remove this message) The military history of Luxembourg is central to the formation of Luxembourg as a nation from its formation around Luxembourg Cast…
This article is about ASU's physical campus in Tempe, AZ. For the university itself, see Arizona State University. Largest campus that composes Arizona State University Arizona State University Tempe campusTypeMain campus of Arizona State UniversityEstablished1885PresidentMichael M. CrowStudents54,866 (Fall 2021)[1][2]LocationTempe, Arizona, United States33°25′02″N 111°56′11″W / 33.4172°N 111.9365°W / 33.4172; -111.9365CampusUrbanTempe: 631.6 a…
Head of the Tibetan Buddhist sect of Karma Kagyu KarmapaThe 16th Karmapa, Rangjung Rigpe Dorje (1924 – 1981)Tibetan nameTibetan རྒྱལ་དབང་ཀརྨ་པ་ TranscriptionsWyliergyal ba karma paTibetan PinyinGarmabaLhasa IPA[kaːmapa]Chinese nameTraditional Chinese噶瑪巴Simplified Chinese噶玛巴TranscriptionsStandard MandarinHanyu Pinyingámǎbā Part of a series onTibetan Buddhism Schools Nyingma Kadam Sakya Bodong Kagyu Jonang Gelug Rimé Key personalit…
Renata Tebaldi Nazionalità Italia GenereOpera lirica Periodo di attività musicale1944 – 1976 EtichettaDecca, Cetra, RCA Album pubblicati52 Studio28 Live24 Sito ufficiale Modifica dati su Wikidata · Manuale Renata Tebaldi (Pesaro, 1º febbraio 1922 – Città di San Marino, 19 dicembre 2004) è stata un soprano italiano. È considerata una delle cantanti liriche più amate di tutti i tempi, acclamata in particolare come interprete di Verdi e Puccini. Indice 1 Bio…
College basketball team Texas State Bobcats 2023–24 Texas State Bobcats women's basketball team UniversityTexas State UniversityHead coachZenarae Antoine (12th season)ConferenceSun BeltLocationSan Marcos, TexasArenaStrahan Coliseum (Capacity: 7,200)NicknameBobcatsColorsMaroon and gold[1] NCAA tournament appearances1997, 2003Conference tournament champions1997, 2003Conference regular season champions2023 The Texas State Bobcats women's basketball team is the b…
Small-sized satellite dish used by Sky and Freesat This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources in this article. Unsourced material may be challenged and removed.Find sources: Minidish – news · newspapers · books · scholar · JSTOR (July 2011) (Learn how and when to remove this message) Zone 2 (57cm) minidish The Minidish is the tradename used for the small-sized sate…