Test de primalité Miller-Rabin
Généralités :
Les algorithmes comme RSA ou Diffie-Hellman ont besoin de nombres premiers pour fonctionner.
Pour générer ces nombres premiers on fait appel à des tests probabilistes. Les nombres ainsi trouvés sont premiers avec une certaine probabilité (très grande) paramétrable lors des implémentations.
Factoriser un grand nombre, ou essayer de le faire, est très long. Savoir si tel nombre est premier avec telle probabilité peut par contre être très rapide.
Les tests de primalité renvoient deux types de réponses :
Soit le nombre ne passe pas le test, et le nombre est un nombre composé.
Soit le nombre passe le test, et le nombre peut être un nombre premier.
Le test de Miller-Rabin, par son efficacité et sa facilité d’implémentation est le plus utilisé.
Description de l’algorithme de Miller-Rabin :
Le test de Miller-Rabin prend en entrée un entier impair n > 1 à tester et un paramètre t (entier positif, nombre de boucles)
Il renvoie en sortie la réponse "Non premier" ou "Peut être premier"
Miller-Rabin(n,t)
Calculer b où b est le nombre de fois que 2 divise n - 1
Poser 2^b * r = n - 1 où r est un entier impair.
Répéter de 0 à t :
Choisir un entier aléatoire témoin 1 < a < n - 1
Calculer : y = a^r mod n
Si ( y != 1 et y != n - 1 ) effectuer :
j := 1
Tant que ( j < b et y != n - 1 ) effectuer :
y := y^2 mod n
Si y = 1 alors renvoie ("Non premier")
j := j + 1
Si (y != n - 1) alors renvoie ("Non premier")
Sinon renvoie ("Peut être premier")
Pour des infos plus sérieuses sur les nombres premiers :
http://www.mersenne.org pour la recherche de ces bêtes là...
http://www.utm.edu/research/primes/ pour un site sur les premiers...
http://www.math.utah.edu/ alfeld/math/largeprime.html pour voir le Mersenne cité plus haut...
Intéressez-vous aux nombres premiers, ils sont fascinants ! A les regarder, les calculer, les manipuler, les étudier on a vraiment l’impression d’avoir à faire à des êtres à part entière. Vous verrez qu’on en vient même à leur parler tendrement...
14 février 2002
Partager sur Twitter | Partager sur LinkedIn