Test de primalité de Miller-Rabin
Le calculateur vérifie si un nombre est premier ou non en utilisant le test de primalité de Miller-Rabin
Ce contenu est sous License Creative Commons Attribution/Partage à l'Identique 3.0(Unported). Cela signifie que vous pouvez redistribuer ou modifier librement ce contenu avec les mêmes modalités de licence et que vous devez créditer l'auteur original en plaçant un lien hypertexte de votre site vers l'œuvre https://fr.planetcalc.com/8995/. Vous ne pouvez pas modifier (le cas échéant) les références dans le contenu de l'œuvre originale.
Ce calculateur vérifie si un entier est un nombre premier en utilisant le test de primalité de Miller-Rabin. Le test utilise une série d'entiers comme base test, qui sont également appelés témoins du test. Les témoins du test peuvent être obtenus de deux manières - en les saisissant ou généré aléatoirement. Si le test renvoie non, alors le nombre donné est définitivement un nombre composite et si le test renvoie oui, le nombre a une forte probabilité d'être premier. Plus le nombre de témoins est important plus le test est précis. Vous pouvez mieux comprendre le résultat détaillé produit par le calculateur en lisant les principes de l'algoritme de Miller-Rabin décrit juste en-dessous du calculateur.
Test de primalité de Miller-Rabin
Algorithme du test de primalité de Miller–Rabin
Pour appliquer le test de primalité de Miller–Rabin à un entier impair n, nous représentons un entier pair n-1 comme 2sd, où d - entier impair, s - entier à la puissance 2. Nous obtenons les nombres s et de en divisant successivement n-1 par 2 jusqu'à ce que le reste soit impair.
Ensuite, nous vérifions successivement que l'un des éléments suivants est vrai :
où :- a - un témoins du test, nombre entier dans l'intervalle [2..n-1]
- r - un nombre naturel inférieur à s.
Si au moins l'une des conditions est respectée, alors le a choisi est un témoin de primalité du nombre n, et le nombre n a une forte probabilité d'être un nombre premier. Pour accroître la probabilité, nous répétons le test pour d'autres bases de a générées aléatoirement.
Si aucune des deux conditions n'est remplie, alors le nombre n est composite, et les tests supplémentaires peuvent être arrêtés.
Le test de primalité de Miller-Rabin gère avec succès les nombres de Carmichael, ce qui n'est pas faisable avec le test de primalité de Fermat.
Ex. le nombre 29341, mentionné incorrectement par le test de Fermat comme premier est determiné comme un nombre composite par le test de Miller-Rabin.
Contrairement au test de Fermat, il n'y a pas de "mauvais" nombres tests pour le test de Miller-Rabin. Pour chaque nombre, le test donne la bonne réponse avec une probabilité élevée. Le résultat erroné de l'algorithme est uniqement déterminé par un choix aléatoire de témoins du test, pour lesquels la probabilité est faible1.
Selon les recherches de Rabin, moins d'un quart des nombres dans l'intervalle [1..n-1] n'est pas témoin2 (ainsi, ils donnent un résultat erroné dans le test de Miller-Rabin). En conséquence, la probabilité de l'erreur finale après k-tours de test est inférieure à 1/4k.
commentaires