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