Test de primalité de Miller-Rabin - Miller–Rabin primality test

Le test de primalité de Miller-Rabin ou test de primalité de Rabin-Miller est un test de primalité probabiliste : un algorithme qui détermine si un nombre donné est susceptible d'être premier , similaire au test de primalité de Fermat et au test de primalité de Solovay-Strassen .

Il est d'une importance historique dans la recherche d'un test de primalité déterministe en temps polynomial. Sa variante probabiliste reste largement utilisée en pratique, comme l'un des tests les plus simples et les plus rapides connus.

Gary L. Miller a découvert le test en 1976 ; La version du test de Miller est déterministe , mais son exactitude repose sur l' hypothèse étendue de Riemann non prouvée . Michael O. Rabin l'a modifié pour obtenir un algorithme probabiliste inconditionnel en 1980.

Concepts mathématiques

De la même manière que les tests de Fermat et Solovay-Strassen, le test de primalité de Miller-Rabin vérifie si une propriété spécifique, dont on sait qu'elle est valable pour les valeurs premières, est valable pour le nombre testé.

Nombres premiers probables forts

La propriété est la suivante. Pour un entier impair donné n > 2 , écrivons n comme 2 ^s ⋅ d + 1 où s et d sont des entiers positifs et d est impair. Considérons un entier  a , appelé base , tel que 0 < a < n . Alors, n est dit être un nombre premier fort probable pour fonder a si l'une de ces relations de congruence est vérifiée :

• ${\displaystyle a^{d}\equiv 1{\pmod {n}}}$;
• ${\displaystyle a^{2^{r}\cdot d}\equiv -1{\pmod {n}}}$ pour un certain 0 r < s .

L'idée sous-jacente à ce test est que lorsque n est un nombre premier impair, il réussit le test à cause de deux faits :

• par le petit théorème de Fermat , (cette propriété définit à elle seule la notion plus faible de premier probable pour fonder a , sur laquelle est basé le test de Fermat) ;${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$
• les seules racines carrées de 1 modulo n sont 1 et -1.

Par conséquent, par contraposition , si n n'est pas un nombre premier fort probable pour baser a , alors n est définitivement composé et a est appelé témoin de la composition de n (parfois appelé à tort un témoin fort ).

Cependant, cette propriété n'est pas une caractérisation exacte des nombres premiers. Si n est composite, il peut néanmoins être un nombre premier fort probable pour baser a , auquel cas on l'appelle un pseudo-premier fort , et a est un fort menteur .

Choix de socles

Heureusement, aucun nombre composé n'est un pseudo-premier fort pour toutes les bases en même temps. Cependant, aucun moyen simple de trouver un témoin n'est connu. Une solution naïve consiste à essayer toutes les bases possibles, ce qui donne un algorithme déterministe inefficace. Le test de Miller en est une variante plus efficace (voir la section Test de Miller ci-dessous ).

Une autre solution consiste à choisir une base au hasard. Cela donne un test probabiliste rapide . Lorsque n est composite, la plupart des bases sont des témoins, donc le test détectera n comme composite avec une probabilité raisonnablement élevée (voir la section Précision ci-dessous ). Nous pouvons réduire rapidement la probabilité d'un faux positif à un taux arbitrairement faible, en combinant le résultat d'autant de bases choisies indépendamment que nécessaire pour atteindre ledit taux. C'est le test de Miller-Rabin. Le nombre de bases à essayer ne dépend pas de n . Il semble y avoir des rendements décroissants en essayant de nombreuses bases, car si n est un pseudo-premier d'une base, alors il semble plus probable qu'il soit un pseudo-premier d'une autre base.

Pour tester n arbitrairement grand , choisir des bases au hasard est essentiel, car nous ne connaissons pas la répartition des témoins et des grands menteurs parmi les nombres 1, 2, …, n −1 .

Cependant, un ensemble présélectionné de quelques petites bases garantit l'identification de tous les composites jusqu'à un maximum pré-calculé. Ce maximum est généralement assez grand par rapport aux bases. Cela donne des tests déterministes très rapides pour un n suffisamment petit (voir la section Tester sur de petits ensembles de bases ci-dessous ).

Preuves

Voici une preuve que, lorsque n est un nombre premier impair, les seules racines carrées de 1 modulo n sont 1 et -1.

Voici une preuve que si n est un nombre premier impair, alors c'est un nombre premier fort probable pour baser a .

Exemple

Supposons que nous souhaitions déterminer si n  = 221 est premier. Nous écrivons n −1 comme 2 ² ·55, de sorte que nous avons s  = 2 et d  = 55. Nous sélectionnons au hasard un nombre a tel que 1 <  a  <  n - 1, disons a = 174. Nous procédons au calcul :

• a ^{2 0 · d} mod n = 174 ⁵⁵ mod 221 = 47 1, n − 1
• a ^{2 1 · d} mod n = 174 ¹¹⁰ mod 221 = 220 = n − 1.

Depuis 220 ≡ -1 mod n , soit 221 est premier ou 174 est un menteur fort pour 221. Nous essayons un autre hasard a , cette fois en choisissant un = 137:

• a ^{2 0 · d} mod n = 137 ⁵⁵ mod 221 = 188 1, n − 1
• a ^{2 1 · d} mod n = 137 ¹¹⁰ mod 221 = 205 n − 1.

Ainsi 137 est un témoin de la composition de 221, et 174 était en fait un fort menteur. Notez que cela ne nous dit rien sur les facteurs de 221 (qui sont 13 et 17). Cependant, l'exemple avec 341 dans une section ultérieure montre comment ces calculs peuvent parfois produire un facteur de n .

Test de Miller-Rabin

L'algorithme peut être écrit en pseudocode comme suit. Le paramètre k détermine la précision du test. Plus le nombre de tours est grand, plus le résultat est précis.

Input #1: n > 3, an odd integer to be tested for primality
Input #2: k, the number of rounds of testing to perform
Output: “composite” if n is found to be composite, “probably prime” otherwise

write n as 2r·d + 1 with d odd (by factoring out powers of 2 from n − 1)
WitnessLoop: repeat k times:
    pick a random integer a in the range [2, n − 2]
    x ← ad mod n
    if x = 1 or x = n − 1 then
        continue WitnessLoop
    repeat r − 1 times:
        x ← x2 mod n
        if x = n − 1 then
            continue WitnessLoop
    return “composite”
return “probably prime”

Complexité

En utilisant la quadrature répétée , le temps d'exécution de cet algorithme est O ( k  log ³ n ) , où n est le nombre testé pour la primalité et k est le nombre de tours effectués ; il s'agit donc d'un algorithme efficace en temps polynomial. FFT à base de multiplication peut pousser le temps de fonctionnement jusqu'à O ( k log ² n log log n log log log n ) = Õ ( k  log ² n ) .

Précision

L'erreur commise par le test de primalité est mesurée par la probabilité qu'un nombre composé soit déclaré probablement premier. Plus on essaie de bases a , meilleure est la précision du test. On peut montrer que , si n est composite, puis au plus une / 4 des bases d' un sont des menteurs solides pour n . En conséquence, si n est composite, l'exécution de k itérations du test de Miller-Rabin déclarera n probablement premier avec une probabilité d'au plus 4 ^{− k} .

Il s'agit d'une amélioration par rapport au test de Solovay-Strassen , dont la borne d'erreur dans le pire des cas est 2 ^{− k} . De plus, le test de Miller-Rabin est strictement plus fort que le test de Solovay-Strassen en ce sens que pour tout composé n , l'ensemble des menteurs forts pour n est un sous-ensemble de l'ensemble des menteurs d'Euler pour n , et pour de nombreux n , le le sous-ensemble est approprié.

De plus, pour de grandes valeurs de n , la probabilité qu'un nombre composé soit déclaré probablement premier est souvent significativement plus petite que 4 ^{− k} . Par exemple, pour la plupart des nombres n , cette probabilité est bornée par 8 ^{− k} ; la proportion de nombres n qui invalident cette borne supérieure s'annule lorsque nous considérons des valeurs plus grandes de n . Par conséquent, le cas moyen a une bien meilleure précision que 4 ^{− k} , un fait qui peut être exploité pour générer des nombres premiers probables (voir ci - dessous ). Cependant, de telles limites d'erreur améliorées ne devraient pas être invoquées pour vérifier les nombres premiers dont la distribution de probabilité n'est pas contrôlée, car un adversaire cryptographique pourrait envoyer un pseudo-premier soigneusement choisi afin de vaincre le test de primalité. Dans de tels contextes, seule la borne d'erreur dans le pire des cas de 4 ^{− k} peut être invoquée.

La mesure d'erreur ci-dessus est la probabilité qu'un nombre composé soit déclaré comme un nombre premier fort probable après k séries de tests ; en termes mathématiques, il s'agit de la probabilité conditionnelle où P est l' événement selon lequel le nombre testé est premier et MR _k est l'événement selon lequel il réussit le test de Miller-Rabin avec k tours. On s'intéresse souvent plutôt à la probabilité conditionnelle inverse : la probabilité qu'un nombre qui a été déclaré comme premier fort probable soit en fait composite. Ces deux probabilités sont liées par la loi de Bayes : ${\displaystyle \Pr(M\!R_{k}\mid \lnot P)}$${\displaystyle \Pr(\lnot P\mid M\!R_{k})}$

${\displaystyle \Pr(\lnot P\mid M\!R_{k})={\frac {\Pr(\lnot P\land M\!R_{k})}{\Pr(\lnot P\land M\!R_{k})+\Pr(P\land M\!R_{k})}}={\frac {1}{1+{\frac {\Pr(M\!R_{k}\ mid P)}{\Pr(M\!R_{k}\mid \lnot P)}}\cdot {\frac {\Pr(P)}{\Pr(\lnot P)}}}}={\ frac {1}{1+{\frac {1}{\Pr(M\!R_{k}\mid \lnot P)}}\cdot {\frac {\Pr(P)}{1-\Pr( P)}}}}}$

Dans la dernière équation, nous avons simplifié l'expression en utilisant le fait que tous les nombres premiers sont correctement rapportés comme des nombres premiers probables forts (le test n'a pas de faux négatif ). En supprimant la partie gauche du dénominateur , nous dérivons une simple borne supérieure :

${\displaystyle \Pr(\lnot P\mid M\!R_{k})<\Pr(M\!R_{k}\mid \lnot P)\cdot \left({\tfrac {1}{\Pr (P)}}-1\droit)}$

Par conséquent, cette probabilité conditionnelle est liée non seulement à la mesure d'erreur discutée ci-dessus — qui est bornée par 4 ^{− k}  — mais aussi à la distribution de probabilité du nombre d'entrée. Dans le cas général, comme dit précédemment, cette distribution est contrôlée par un adversaire cryptographique, donc inconnu, on ne peut donc pas en déduire grand-chose sur . Cependant, dans le cas où nous utilisons le test de Miller-Rabin pour générer des nombres premiers (voir ci - dessous ), la distribution est choisie par le générateur lui-même, nous pouvons donc exploiter ce résultat. ${\displaystyle \Pr(\lnot P\mid M\!R_{k})}$

Variantes déterministes

essai de Miller

L'algorithme Miller-Rabin peut être déterministe en essayant autant que possible un dessous d' une certaine limite. Prendre n comme limite impliquerait O( n ) essais, donc le temps d'exécution serait exponentiel par rapport à la taille log n de l'entrée. Pour améliorer le temps d'exécution, l'enjeu est alors d'abaisser au maximum la limite tout en gardant le test fiable.

Si le nombre testé n est composite, les menteurs forts a premiers de n sont contenus dans un sous - groupe propre du groupe ( Z / n Z )*, ce qui signifie que si l'on teste tous les a d'un ensemble qui génère ( Z / n Z )*, l'un d'eux doit se situer à l'extérieur dudit sous-groupe, doit donc être un témoin de la composition de n . En supposant la vérité de l' hypothèse de Riemann généralisée (GRH), on sait que le groupe est généré par ses éléments plus petits que O(( ln n ) ² ) , ce qui a déjà été noté par Miller. La constante impliquée dans la notation Big O a été réduite à 2 par Eric Bach . Cela conduit à l'algorithme de test de primalité déterministe suivant, connu sous le nom de test de Miller :

Input: n > 1, an odd integer to be tested for primality
Output: “composite” if n is composite, “prime” otherwise

write n as 2r·d + 1 with d odd (by factoring out powers of 2 from n − 1)
WitnessLoop: for all a in the range [2, min(n−2, ⌊2(ln n)2⌋)]:
    x ← ad mod n
    if x = 1 or x = n − 1 then
        continue WitnessLoop
    repeat r − 1 times:
        x ← x2 mod n
        if x = n − 1 then
            continue WitnessLoop
    return “composite”
return “prime”

La pleine puissance de l'hypothèse de Riemann généralisée n'est pas nécessaire pour assurer l'exactitude du test : comme nous traitons des sous-groupes d' indice pair , il suffit de supposer la validité de GRH pour les caractères de Dirichlet quadratiques .

Le temps d'exécution de l'algorithme est, dans la notation soft-O , ((log n ) ⁴ ) (en utilisant la multiplication basée sur la FFT).

Le test de Miller n'est pas utilisé en pratique. Dans la plupart des cas, une utilisation appropriée du test probabiliste de Miller-Rabin ou du test de primalité Baillie-PSW donne une confiance suffisante tout en s'exécutant beaucoup plus rapidement. Il est également plus lent en pratique que les méthodes de preuve couramment utilisées telles que APR-CL et ECPP qui donnent des résultats qui ne reposent pas sur des hypothèses non prouvées. À des fins théoriques nécessitant un algorithme de temps polynomial déterministe, il a été remplacé par le test de primalité AKS , qui ne repose pas non plus sur des hypothèses non prouvées.

Tests sur de petits ensembles de bases

Lorsque le nombre n à tester est petit, il n'est pas nécessaire d' essayer tout a < 2(ln n ) ² , car on sait que des ensembles beaucoup plus petits de témoins potentiels suffisent. Par exemple, Pomerance, Selfridge, Wagstaff et Jaeschke ont vérifié que

• si n < 2 047, il suffit de tester a = 2 ;
• si n < 1 373 653, il suffit de tester a = 2 et 3 ;
• si n < 9 080 191, il suffit de tester a = 31 et 73 ;
• si n < 25 326 001, il suffit de tester a = 2, 3 et 5 ;
• si n < 3 215 031 751, il suffit de tester a = 2, 3, 5 et 7 ;
• si n < 4 759 123 141, il suffit de tester a = 2, 7 et 61 ;
• si n < 1 122 004 669 633, il suffit de tester a = 2, 13, 23 et 1662803 ;
• si n < 2 152 302 898 747, il suffit de tester a = 2, 3, 5, 7 et 11 ;
• si n < 3 474 749 660 383, il suffit de tester a = 2, 3, 5, 7, 11 et 13 ;
• si n < 341 550 071 728 321, il suffit de tester a = 2, 3, 5, 7, 11, 13 et 17.

En utilisant les travaux de Feitsma et Galway énumérant tous les pseudo-premiers en base 2 en 2010, cela a été étendu (voir OEIS :  A014233 ), avec le premier résultat montré plus tard en utilisant différentes méthodes dans Jiang et Deng :

• si n < 3 825 123 056 546 413 051, il suffit de tester a = 2, 3, 5, 7, 11, 13, 17, 19 et 23.
• si n < 18 446 744 073 709 551 616 = 2 ⁶⁴ , il suffit de tester a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 et 37.

Sorenson et Webster vérifient ce qui précède et calculent des résultats précis pour ces résultats supérieurs à 64 bits :

• si n < 318 665 857 834 031 151 167 461, il suffit de tester a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 et 37.
• si n < 3 317 044 064 679 887 385 961 981, il suffit de tester a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 et 41.

D'autres critères de ce type, souvent plus performants (moins de bases nécessaires) que ceux présentés ci-dessus, existent. Ils donnent des tests de primalité déterministes très rapides pour les nombres dans la plage appropriée, sans aucune hypothèse.

Il existe une petite liste de témoins potentiels pour chaque taille d'entrée possible (au plus b valeurs pour les nombres de b bits). Cependant, aucun ensemble fini de bases n'est suffisant pour tous les nombres composés. Alford, Granville et Pomerance ont montré qu'il existe une infinité de nombres composés n dont le plus petit témoin de composition est au moins (ln n ) ^{1/(3ln ln ln n n )} . Ils soutiennent également de manière heuristique que le plus petit nombre w tel que chaque nombre composé inférieur à n ait un témoin de composition inférieur à w devrait être d'ordre Θ (log n log log n ).

Variantes pour trouver des facteurs

En insérant les plus grands calculs de diviseur commun dans l'algorithme ci-dessus, nous pouvons parfois obtenir un facteur de n au lieu de simplement déterminer que n est composite. Cela se produit par exemple lorsque n est une base première probable a mais pas une base première probable forte a . Nous pouvons détecter ce cas dans l'algorithme en comparant x dans la boucle interne non seulement à -1, mais aussi à 1.

Si à une itération 1 ≤ i < r de la boucle interne, l'algorithme découvre que la valeur a ^{d ·2 i} mod n de la variable x est égale à 1, alors, sachant que la valeur précédente x ₀ = a ^{d ·2 s -1} de la variable x a été vérifié comme différent de ±1, on peut en déduire que x ₀ est une racine carrée de 1 qui n'est ni 1 ni -1. Comme cela n'est pas possible lorsque n est premier, cela implique que n est composite. De plus:

• puisque x ₀ ² ≡ 1 (mod n ) , on sait que n divise x ₀ ² − 1 = ( x ₀ − 1)( x ₀ + 1) ;
• puisque x ₀ ±1 (mod n ) , nous savons que n ne divise pas x ₀ − 1 ni x ₀ + 1 .

On en déduit que A = PGCD( x ₀ − 1, n ) et B = PGCD( x ₀ + 1, n ) sont des facteurs non triviaux (pas nécessairement premiers) de n (en fait, puisque n est impair, ces les facteurs sont premiers entre eux et n = A · B ). Par conséquent, si la factorisation est un objectif, ces calculs GCD peuvent être insérés dans l'algorithme à peu de frais de calcul supplémentaires. Cela conduit au pseudo-code suivant, où le code ajouté ou modifié est mis en évidence :

Input #1: n > 3, an odd integer to be tested for primality
Input #2: k, the number of rounds of testing to perform
Output: (“multiple of”, m) if a non‐trivial factor m of n is found,
        “composite” if n is otherwise found to be composite,
        “probably prime” otherwise

write n as 2r·d + 1 with d odd (by factoring out powers of 2 from n − 1)
WitnessLoop: repeat k times:
    pick a random integer a in the range [2, n − 2]
    x ← ad mod n
    if x = 1 or x = n − 1 then
        continue WitnessLoop
    repeat r − 1 times:
        y ← x2 mod n
        if y = 1:
            return (“multiple of”, GCD(x − 1, n))
        x ← y
        if x = n − 1 then
            continue WitnessLoop
    return “composite”
return “probably prime”

Cet algorithme ne donne pas d' algorithme de factorisation probabiliste car il n'est capable de trouver des facteurs que pour des nombres n pseudo-premiers pour baser a (c'est-à-dire pour des nombres n tels que a ^{n −1} 1 mod n ). Pour les autres nombres, l'algorithme ne renvoie que « composite » sans autre information.

Par exemple, considérons n = 341 et a = 2. Nous avons n − 1 = 85,4. Alors 2 ⁸⁵ mod 341 = 32. et 32 ² mod 341 = 1. Cela nous dit que n est une base pseudo-prime 2, mais pas une base pseudo-prime forte 2. En calculant un PGCD à ce stade, on trouve un facteur de 341 : PGCD(32 − 1, 341) = 31. En effet, 341 = 11·31 .

Afin de trouver des facteurs plus souvent, les mêmes idées peuvent également être appliquées aux racines carrées de -1 (ou de tout autre nombre). Cette stratégie peut être mise en œuvre en exploitant les connaissances des séries précédentes du test Miller-Rabin. Dans ces tours, nous avons peut-être identifié une racine carrée modulo n de -1, disons R . Ensuite, lorsque x ² mod n = n −1 , on peut comparer la valeur de x contre R : si x n'est ni R ni n − R , alors PGCD( x − R , n ) et PGCD( x + R , n ) sont des facteurs non triviaux de n .

Génération de nombres premiers probables

Le test de Miller-Rabin peut être utilisé pour générer des nombres premiers probables forts, simplement en tirant des nombres entiers au hasard jusqu'à ce que l'on réussisse le test. Cet algorithme se termine presque sûrement (puisqu'à chaque itération, il y a une chance de tirer un nombre premier). Le pseudocode pour générer des nombres premiers probables forts de b ‐ bits (avec le bit le plus significatif défini) est le suivant :

Input #1: b, the number of bits of the result
Input #2: k, the number of rounds of testing to perform
Output: a strong probable prime n

while True:
    pick a random odd integer n in the range [2b−1, 2b−1]
    if the Miller–Rabin test with inputs n and k returns “probably prime” then
        return n

Complexité

Bien sûr, le temps d'exécution dans le pire des cas est infini, car la boucle externe peut ne jamais se terminer, mais cela se produit avec une probabilité zéro. Selon la distribution géométrique , le nombre attendu de tirages est (en réutilisant les notations du précédent ). ${\displaystyle {\tfrac {1}{\Pr(M\!R_{k})}}}$

Comme tout nombre premier réussit le test, la probabilité d'être premier donne une limite inférieure grossière à la probabilité de réussir le test. Si nous tirons uniformément des entiers impairs dans l'intervalle [2 ^{b −1} , 2 ^b −1], alors nous obtenons :

${\displaystyle \Pr(M\!R_{k})>\Pr(P)={\frac {\pi \left(2^{b}\right)-\pi \left(2^{b-1 }\right)}{2^{b-2}}}}$

où est la fonction de comptage des nombres premiers . En utilisant un développement asymptotique de (une extension du théorème des nombres premiers ), nous pouvons approximer cette probabilité lorsque b croît vers l'infini. Nous trouvons:

${\displaystyle \Pr(P)={\tfrac {2}{\ln 2}}b^{-1}+{\mathcal {O}}\left(b^{-3}\right)}$

${\displaystyle {\tfrac {1}{\Pr(P)}}={\tfrac {\ln 2}{2}}b+{\mathcal {O}}\left(b^{-1}\right) }$

Par conséquent, nous pouvons nous attendre à ce que le générateur n'exécute pas plus de tests de Miller-Rabin qu'un nombre proportionnel à b . En tenant compte de la complexité dans le pire des cas de chaque test de Miller-Rabin (voir plus haut ), le temps de fonctionnement attendu du générateur avec les entrées b et k est alors borné par O( k b ⁴ ) (ou Õ( k b ³ ) en utilisant multiplication basée sur la FFT).

Précision

La mesure d'erreur de ce générateur est la probabilité qu'il produise un nombre composé.

En utilisant la relation entre les probabilités conditionnelles (montrées dans une section précédente ) et le comportement asymptotique de (montré juste avant), cette mesure d'erreur peut recevoir une borne supérieure grossière : ${\style d'affichage \Pr(P)}$

${\displaystyle \Pr(\lnot P\mid M\!R_{k})<\Pr(M\!R_{k}\mid \lnot P)\cdot \left({\tfrac {1}{\Pr (P)}}-1\right)\leq 4^{-k}\cdot \left({\tfrac {\ln 2}{2}}b-1+{\mathcal {O}}\left(b ^{-1}\droit)\droit)}$

Par conséquent, pour un b suffisamment grand , cette mesure d'erreur est inférieure à . Cependant, il existe de bien meilleures limites. ${\displaystyle {\tfrac {\ln 2}{2}}\cdot b\cdot 4^{-k}}$

En utilisant le fait que le test de Miller-Rabin lui-même a souvent une borne d'erreur beaucoup plus petite que 4 ^{− k} (voir plus haut ), Damgård , Landrock et Pomerance ont dérivé plusieurs bornes d'erreur pour le générateur, avec différentes classes de paramètres b et k . Ces limites d'erreur permettent à un implémenteur de choisir un k raisonnable pour une précision souhaitée.

L'une de ces bornes d'erreur est 4 ^{− k} , qui est valable pour tout b 2 (les auteurs ne l'ont montré que pour b 51, tandis que Ronald Burthe Jr. a complété la preuve avec les valeurs restantes 2 ≤ b ≤ 50). Encore une fois, cette simple borne peut être améliorée pour les grandes valeurs de b . Par exemple, une autre borne dérivée par les mêmes auteurs est :

${\displaystyle \left({\tfrac {1}{7}}b^{15/4}2^{-b/2}\right)\cdot 4^{-k}}$

ce qui est vrai pour tout b 21 et k ≥ b ⁄ 4 . Cette borne est inférieure à 4 ^{− k} dès que b 32.

Remarques

Les références

Liens externes

• Weisstein, Eric W. "Test de pseudo-premier fort de Rabin-Miller" . MathWorld .
• Implémentation interactive en ligne de la variante déterministe (parcours pas à pas de l'algorithme)
• Applet (allemand)
• Test de primalité Miller-Rabin en C#
• Test de primalité Miller-Rabin en JavaScript en utilisant l'arithmétique de précision arbitraire