cryptosec

Test de primalité Miller-Rabin

A la recherche de nombres premiers...

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...


 
cryptosec
14 février 2002

 
 
 
 
 
Partager sur Twitter  |  Partager sur LinkedIn
 

Afficher les commentairesMasquer les commentaires


 
modération a priori

Ce forum est modéré a priori : votre contribution n’apparaîtra qu’après avoir été validée par les responsables.

Qui êtes-vous ?
Votre message

Pour créer des paragraphes, laissez simplement des lignes vides.

Creative Commons - BY - NC - ND

Tous les textes, images et sons de cryptosec sont publiés selon les termes de la licence Creative Commons - Attribution - Pas d’Utilisation Commerciale - Pas de Modification - 3.0