Test de primalité de Miller-Rabin

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

Nombre entier

Bases

Aléatoire

Liste

Nombre de tours

Bases

Détails

Calculer

Peut être premier

 

Puissances de 2 facteurs

 

Le fichier est très volumineux; un ralentissement du navigateur peut se produire pendant le chargement et la création.

Télécharger 

 Lien  sauvegarder  Widget

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 2^sd, 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 :

1. 
2. 
   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 faible¹.
Selon les recherches de Rabin, moins d'un quart des nombres dans l'intervalle [1..n-1] n'est pas témoin² (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/4^k.