Test de primalité de Miller-Rabin

Frichfrouch Messages postés 3 Date d'inscription lundi 30 juin 2008 Statut Membre Dernière intervention 29 novembre 2009 - 26 nov. 2009 à 18:33
 nouno02 - 18 mars 2013 à 14:35
Bonsoir à tous,

Comme vous le savez tous, il existe de très nombreux algorithmes (notamment sur le site de VBFrance) permettant de chercher les nombres premiers parmi une liste de nombres. Toutefois, la plupart d'entre-eux sont relativement peu efficients dès que le nombre à tester devient très grand puisque l'idée consiste à observer le reste de sa division de 2 à sa racine carrée.

Il existe des tests de primalité probabilistique tels que celui de Miller-Rabin et qui permettent assez rapidement (en théorie) de déterminer si un nombre est premier avec un taux de certitude élevé. Il ne vous échappera pas que les grands nombres premiers issus de ces tests sont directement utilisables dans des algorithmes de cryptage asymétrique tel que RSA.

L'idée de ce test de primalité est très simple, on la retrouve sur wikipedia (http://fr.wikipedia.org/wiki/Test_de_primalité_de_Miller-Rabin) mais sa mise en pratique me pose problème en raison des très grands nombres qu'il s'agit de manipuler.

Malgré l'idée que j'ai eu pour rendre le calcul de l'exponentiation modulo plus simple, je crois que cette méthode n'est pas appropriée :

Dim NombrePremierPossible As Long, NombreHasardTest As Integer, TestOK As Boolean, X As String
Dim m As Long, k As Integer, n As Integer, TestNumero As Integer, r As Integer, i As Integer

'On détermine NombrePremierPossible au hasard (ne soyons pas vicieux et saisissons un nombre impair).
'Assumons que NombrePremierPossible = 1 + m * 2^k (où m est impair et k un entier).

m 0: k 0: TestOK = False
Do Until m Mod 2 <> 0
k = k + 1
m = (NombrePremierPossible - 1) / (2 ^ k)
Loop

'On détermine au hasard NombreHasardTest tel qu'il soit compris entre 1 et (NombrePremierPossible - 1).

Randomize Timer
NombreHasardTest = Int(Rnd * (NombrePremierPossible - 1)) + 1

'On vérifie que NombreHasardTest ^ (m * 2 ^ i) est congru à -1 modulo NombrePremierPossible OU
'OU NombreHasardTest ^ m est congru à 1 modulo NombrePremierPossible. Nb : 0 <= i <= k -1
'Si c'est le cas, le test est répété 40 fois pour être (presque) sûr de la primalité de NombrePremierPossible
'sinon, le nombre n'est pas premier.

For TestNumero = 1 To 40
For n = 0 To k - 1
r = 1
For i = 1 To m * (2 ^ n)
r = (r * NombreHasardTest) - NombrePremierPossible * Int((r * NombreHasardTest) / NombrePremierPossible)
Next i
If r 1 Or r NombrePremierPossible - 1 Then TestOK = True: Exit For
Next n
If TestOK False Then X "Le nombre n'est pas premier": Exit Sub Else TestOK = False
Next TestNumero

X = "Le nombre est probablement premier"

Avez-vous des suggestions pour que ce test de primalité fonctionne le plus rapidement possible et avec de grands nombres (100 chiffres par exemple) ? Je vois qu'il existe des solutions pour le C++ et toutes sortes de langages sans doute plus adapté aux mathématiques. Je pense qu'il serait assez intéressant de proposer ce type de code sur VBFrance aussi

Merci pour votre aide !

Fred

8 réponses

us_30 Messages postés 2065 Date d'inscription lundi 11 avril 2005 Statut Membre Dernière intervention 14 mars 2016 10
26 nov. 2009 à 22:11
Bonsoir,

Il faudrait déjà faire une fonction de calcul de l'exponentiation modulo rapide... indépendamment du reste...

Amicalement,
Us.
us_30 Messages postés 2065 Date d'inscription lundi 11 avril 2005 Statut Membre Dernière intervention 14 mars 2016 10
26 nov. 2009 à 22:56
Re,

Voici une fonction optimisée que je viens de faire :

Function ExpoMod(ByVal p As Long, ByVal j As Long, ByVal n As Long) As Long
' EXPONENTIATION MODULAIRE RAPIDE

ExpoMod = 1
Do
    If j And 1 Then j j - 1: ExpoMod p * ExpoMod
    ExpoMod = ExpoMod Mod n
    j = j / 2
    p = (p * p) Mod n
Loop Until j = 0

End Function


Amicalement,
Us.
Frichfrouch Messages postés 3 Date d'inscription lundi 30 juin 2008 Statut Membre Dernière intervention 29 novembre 2009
29 nov. 2009 à 21:01
Hello et merci à toi Us pour ta contribution.

L'implémentation de cette exponentiation modulaire rapide a effectivement du succès et permet d'éviter pas mal d'overflow. J'ai également ajouté un module existant déjà sur VBFrance et permettant de manipuler de grands nombres (ou plutôt les variables string qui les représentent).

Résultat, le test de primalité fonctionne parfaitement et je serais heureux d'en déposer une copie sur le forum si cela pouvait être utile à quelqu'un.

Malheureusement, la victoire n'est pas totale puisque lorsque les nombres à tester font plus de 15-16 chiffres, le temps de calcul devient relativement long... le programme se limite donc à la création de clés RSA de 256 bits (ce qui est, avouons le, bien dérisoire).
jmf0 Messages postés 1566 Date d'inscription mardi 26 décembre 2000 Statut Membre Dernière intervention 5 avril 2013 8
29 nov. 2009 à 21:23
Bonsoir,

Si tu cherches à battre le record de la détermination du plus grand nombre premier, t'es pas sorti de l'auberge.
Je crois qu'il est en ce moment entre les mains d'un Indien, si ma mémoire est bonne ...et... qu'il n'est pas prêt d'être battu, ce record-là

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
jmf0 Messages postés 1566 Date d'inscription mardi 26 décembre 2000 Statut Membre Dernière intervention 5 avril 2013 8
29 nov. 2009 à 21:28
Hé bien non, ce n'est plus un Indien ...
http://www.sciencepresse.qc.ca/node/22189
Si tu arrives à aller plus loin qu'eux, tu vas être riche
Frichfrouch Messages postés 3 Date d'inscription lundi 30 juin 2008 Statut Membre Dernière intervention 29 novembre 2009
29 nov. 2009 à 23:08
J'aime l'argent... je vais m'y mettre tout de suite
Plus sérieusement, les nombres premiers c'est pas ma grande passion et pour l'instant je n'ai rien trouvé de mieux...
ESSLAM 3LAÏKOM à tous
nouri .......
nouri .......
nouri .......[size=300]/size
Rejoignez-nous