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

Cette page existe grâce aux efforts des personnes suivantes :

Anton

Gaulthier Marrel

Créé: 2020-12-18 02:56:00, Dernière mise à jour: 2020-12-18 03:26:10

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.

PLANETCALC, Test de primalité de Miller-Rabin

Test de primalité de Miller-Rabin

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.

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 :

  1. a^{d}\equiv 1{\pmod {n}}
  2. a^{2^{r}d}\equiv -1{\pmod {n}}
    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.


  1. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. Introduction to algorithms 

  2. Michael O. Rabin, Probabilistic Algorithm for Testing Primality, Journal of number theory 12, 128-138 (1980) 

URL copiée dans le presse-papiers
PLANETCALC, Test de primalité de Miller-Rabin

commentaires