1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84
| '---------------------------------------------------------------------------------------
' http://fordom.free.fr/
'---------------------------------------------------------------------------------------
Option Explicit
'---------------------------------------------------------------------------------------
Public Function TestMillerRabinGN(ByVal n As String) As Boolean
'---------------------------------------------------------------------------------------
' Test MILLER RABIN pour les grands nombres.
' Retourne Vrai si n a une forte probabilité d'être un nombre premier.
'---------------------------------------------------------------------------------------
Dim a As Long, BaseMaxi As Long, i As Integer
Dim Base As Variant
Dim x() As Byte
Dim nm1 As String
' Convertit la chaîne en nombres:
x = StrConv(n, vbFromUnicode)
' Si le dernier chiffre est différent de 1, 3, 7, 9 alors quitter:
Select Case Chr(x(UBound(x)))
Case "0", "2", "4", "5", "6", "8": Exit Function
End Select
' Si la somme des nombres de n modulu 3 donne 0 alors quitter:
For i = 0 To UBound(x): a = a + x(i) - 48: Next i
If a Mod 3 = 0 Then Exit Function
' Base à tester:
Base = Array(2, 3, 5, 7, 11, 13, 17, 19, 23)
' Test si n est divisible par un (très petit) nombre de la base, en
' commençant par 7 car 2, 3, et 5 déjà testés:
For a = 3 To UBound(Base)
If ModGNPD(n, Base(a)) = 0 Then Exit Function
Next a
' Calcul rapide de n - 1 (car n ne finit jamais par 0):
nm1 = n
Mid(nm1, Len(nm1), 1) = Chr(x(UBound(x)) - 1)
' Si 2^n-1 MOD n <> 1 alors quitter:
If ExpoModGN(2, nm1, n) <> "1" Then Exit Function
' Optimisation nb base à tester:
BaseMaxi = Int(4 + LogGN(n) / 8 - Abs(4 - LogGN(n) / 8))
' Algo:
a = 0
Do
If MillerRabinGN(n, Base(a), nm1) = False Then Exit Function
a = a + 1
Loop Until a > BaseMaxi
TestMillerRabinGN = True
End Function
'---------------------------------------------------------------------------------------
Private Function MillerRabinGN(ByVal n As Variant, ByVal a As Variant, ByVal nm1 As String) As Boolean
'---------------------------------------------------------------------------------------
' RQ : IMPOSSIBILITE DE REPONDRE SI n multiple de a
'---------------------------------------------------------------------------------------
' Paramètres:
Dim H As Long, d As Variant, i As Long, Reste As Variant
' Calcul de n-1 = 2^h * d avec d impair:
Do
H = H + 1: If H > 30 Then Exit Do
d = DGN(nm1, 2 ^ H, Reste)
Loop Until Reste = 0 And Right(d, 1) Mod 2 = 1
' Test a^d=1 mod n:
MillerRabinGN = (Val(ExpoModGN(a, d, n)) = 1)
If MillerRabinGN Then Exit Function
' Test s'il existe un 0<= i <= h-1 tel que a^(h*2^i)=-1 mod n:
For i = 0 To H - 1
MillerRabinGN = (ExpoModGN(a, PGN(d, 2 ^ i), n) = nm1)
If MillerRabinGN Then Exit For
Next i
End Function
'---------------------------------------------------------------------------------------
'--------------------------------------------------------------------------------------- |