Test de primalité de Miller-Rabin

Question

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

us_30 · Answer

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

us_30 · Answer

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 · Answer

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 · Answer

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à

jmf0 · Answer

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 · Answer

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

nouno02 · Answer

ESSLAM 3LAÏKOM à tous

nouno02 · Answer

nouri .......
nouri .......
nouri .......[size=300]/size

Test de primalité de Miller-Rabin

8 réponses

Votre réponse

Discussions similaires