Sub FindGoodMultiplier( _
ByVal Modulus As Long, _
Optional ByVal OverflowAt As Long = 32767)
Dim Multiplier As Long
Dim Hit() As Boolean
Dim m As Long
Dim x As Long
Dim i As Long
Do While Modulus > 1
ReDim Hit(1 To Modulus - 1) As Boolean
m = OverflowAt \ Modulus
If m >= Int(Modulus ^ (2 / 3)) Then m = Int(Modulus ^ (2 / 3))
For Multiplier = m To 2 Step -1
For i = 1 To Modulus - 1: Hit(i) = False: Next i
x = 1
For i = 2 To Modulus - 1
If x = 0 Then Exit For
If Hit(x) Then Exit For
Hit(x) = True
x = (x * Multiplier) Mod Modulus
Next i
If i > Modulus - 1 Then
Debug.Print Multiplier & " is a good multiplier for modulus " & Modulus
Exit Sub
End If
Next Multiplier
Modulus = Modulus - 1
DoEvents
Loop
Debug.Print "No good multiplier was found"
End Sub
' 1020 is a good multiplier for modulus 32749
' 63 is a good multiplier for modulus 509
' 21 is a good multiplier for modulus 97
' 23 is a good multiplier for modulus 127
Comments
0 B
|0 👍
/0 👎
0 B
|👍
/👎