Primzahl Prüfung Miller-Rabin Test
Verfasst: 30.12.2017 18:27
Hallo zusammen,
für ein Projekt habe ich eine schnelle (die Geschwindigkeit war zumindest für meine Zwecke mehr als ausreichend) Prüfung gebraucht ob eine Zahl (bis ca. 2^62) also positive Quad eine Primzahl ist oder nicht.
Ich habe mich mit dem Miller-Rabin Test vertraut gemacht und die Procedure IsPrime() geschrieben.
Da der Miller-Rabin Test nicht sicher sagt ob eine Zahl eine Primzahl ist, jedoch sicher sagt wenn es keine Primzahl ist, wurde der Parameter "Loop" mit eingebaut mit der an der Wahrscheinlichkeitsschraube gedreht werden kann. Damit kann die Wahrscheinlichkeit einer Fehlaussage bis zur gewünschten kleinen Wahrscheinlichkeit beeinflusst werden. Ohne Angabe ist im schlechtesten Fall eine maximale Fehlerwahrscheinlichkeit von ca. 0,0001 % gegeben. Je höher der Loop gesetzt wird desto unwahrscheinlicher ist eine Fehleinschätzung.
Die Procedure gibt #False (wenn keine Primzahl) oder #True (wenn Primzahl mit der beschriebenen Fehlereinschätzung) zurück.
Wer es gebrauchen kann, kann es nutzen (Ich wollte auch mal etwas an die Community zurückgeben).
Für Fehlerhinweise wäre ich dankbar.
NicknameFJ
Sollen nur Zahlen bis QUAD geprüft werden ist die untenstehende Variante von Helle deutlich schneller da unser Assembler-Spezialist Helle dort den BigInt Teil durch 64/128-Bit Routinen ersetzt hat.
@Helle: Danke dir dafür.
[EDIT]
Nachfolgend noch eine Variante die komplett mit BigInt arbeitet. Der Größe der zu prüfenden Zahl ist damit theoretisch nach oben hin keine Grenze gesetzt.
In der BigInt - Lib ist die Konstante #BigIntBit auf 2048 gesetzt. Daher keine Zahlen größer als 2^1024 -1 prüfen da ansonsten innerhalb dere Berechnung ein Überlauf auftreten kann und das Ergebnis dann nicht mehr stimmt. Ggfs. muss die Konstante innerhalb der Lib auf einen höheren Wert gesetzt werden.
für ein Projekt habe ich eine schnelle (die Geschwindigkeit war zumindest für meine Zwecke mehr als ausreichend) Prüfung gebraucht ob eine Zahl (bis ca. 2^62) also positive Quad eine Primzahl ist oder nicht.
Ich habe mich mit dem Miller-Rabin Test vertraut gemacht und die Procedure IsPrime() geschrieben.
Da der Miller-Rabin Test nicht sicher sagt ob eine Zahl eine Primzahl ist, jedoch sicher sagt wenn es keine Primzahl ist, wurde der Parameter "Loop" mit eingebaut mit der an der Wahrscheinlichkeitsschraube gedreht werden kann. Damit kann die Wahrscheinlichkeit einer Fehlaussage bis zur gewünschten kleinen Wahrscheinlichkeit beeinflusst werden. Ohne Angabe ist im schlechtesten Fall eine maximale Fehlerwahrscheinlichkeit von ca. 0,0001 % gegeben. Je höher der Loop gesetzt wird desto unwahrscheinlicher ist eine Fehleinschätzung.
Die Procedure gibt #False (wenn keine Primzahl) oder #True (wenn Primzahl mit der beschriebenen Fehlereinschätzung) zurück.
Wer es gebrauchen kann, kann es nutzen (Ich wollte auch mal etwas an die Community zurückgeben).
Für Fehlerhinweise wäre ich dankbar.
NicknameFJ
Sollen nur Zahlen bis QUAD geprüft werden ist die untenstehende Variante von Helle deutlich schneller da unser Assembler-Spezialist Helle dort den BigInt Teil durch 64/128-Bit Routinen ersetzt hat.
@Helle: Danke dir dafür.
Code: Alles auswählen
EnableExplicit
; Pfad zur LIB anpassen
IncludeFile "O:\Includes\BigInt\BigInt.pbi"
; Nutzung der BIGInt Lib von wilbert aus dem englischen Forum
; http://www.purebasic.fr/english/viewtopic.php?f=12&t=61309
Procedure isPrime(Zahl.q, Loop = 10)
; Ist Z keine Primzahl gibt die Proc. 0 zurück
; Ist Z eine Primzahl gibt die Proc. 1 zurück
; Rückgabe 1 kann auch bedingt durch den Algoritmus
; Miller-Rabin eine Zahl anzeigen die nicht
; prim ist. Die Fehlerwahrscheinlichkeit kann durch
; duch Erhöhung des Parameters Loop weiter gesenkt
; werden.
Protected d.q, r.q, a.q, x.q, lp.i, CheckBZE.i
Protected.BigInt::BigInt BX, BA, BD, BZahl, BEins, BZahl_1, n0, BZero
If Zahl = 2
ProcedureReturn #True
ElseIf Zahl < 2 Or Zahl % 2 = 0
ProcedureReturn #False
EndIf
If Loop < 1 : Loop = 1 : EndIf
BigInt::SetValue(BEins,1)
BigInt::SetValue(BZero,0)
BigInt::SetValue(BZahl_1,Zahl - 1)
d = Zahl - 1
r = 0
While d % 2 = 0
d = d / 2
r + 1
Wend
While Loop > 0
Loop -1
a = Random(Zahl-1,2)
BigInt::SetValue(BA,a)
BiGInt::SetValue(BD,d)
BiGInt::SetValue(BZahl,Zahl)
BIGInt::ModPow(BX,BA,BD,BZahl)
If BigInt::Compare(BX,BEins) = 0 Or BigInt::Compare(BX,BZahl_1) = 0
Continue
EndIf
lp = r
While lp > 0
BigInt::ModMul(BX,BX,BZahl)
If BigInt::Compare(BX,BEins) = 0
ProcedureReturn #False
EndIf
CheckBZE = BigInt::Compare(BX,BZahl_1)
If CheckBZE = 0
Break
EndIf
lp - 1
Wend
If CheckBZE <> 0
ProcedureReturn #False
EndIf
Wend
ProcedureReturn #True
EndProcedure
CompilerIf #PB_Compiler_IsMainFile
Define Zahl.q
For Zahl = 2 To 1000
If isprime(Zahl)
Debug Str(Zahl) + " ist prim"
EndIf
Next
CompilerEndIf
[EDIT]
Nachfolgend noch eine Variante die komplett mit BigInt arbeitet. Der Größe der zu prüfenden Zahl ist damit theoretisch nach oben hin keine Grenze gesetzt.
In der BigInt - Lib ist die Konstante #BigIntBit auf 2048 gesetzt. Daher keine Zahlen größer als 2^1024 -1 prüfen da ansonsten innerhalb dere Berechnung ein Überlauf auftreten kann und das Ergebnis dann nicht mehr stimmt. Ggfs. muss die Konstante innerhalb der Lib auf einen höheren Wert gesetzt werden.
Code: Alles auswählen
EnableExplicit
; Pfad zur LIB anpassen
IncludeFile "O:\Includes\BigInt\BigInt.pbi"
; Nutzung der BIGInt Lib von wilbert aus dem englischen Forum
; http://www.purebasic.fr/english/viewtopic.php?f=12&t=61309
Procedure isPrime(*pZahl.BigInt::BigInt, Loop.i = 10)
; wird 0 zurückgegeben ist die zu testende Zahl keine Primzahl
; wird 1 zurückgegeben ist die zu testende Zahl eine Primzahl
; Rückgabe 1 kann auch bedingt durch den Algoritmus
; Miller-Rabin eine Zahl anzeigen die nicht
; prim ist. Die Fehlerwahrscheinlichkeit kann durch
; die Erhöhung des Parameters Loop weiter gesenkt
; werden.
Protected r.q, lp.i, CheckBZE.i, length, BitMask = $8000000000000000
Protected.BigInt::BigInt BX, BA, BD, BZahl, BEins, BZahl_1, BZero, BZwei, BReminder
BigInt::Assign(BZahl,*pZahl)
BigInt::SetValue(BZwei,2)
BigInt::SetValue(BEins,1)
BigInt::SetValue(BZero,0)
If BigInt::Compare(*pZahl,BZwei) = 0
ProcedureReturn #True
EndIf
length = BigInt::#BigIntBits >> 6
If length
If *pZahl\q[length-1] & BitMask
ProcedureReturn #False
EndIf
EndIf
If *pZahl\q[0] & 1 = 0
ProcedureReturn #False
EndIf
If Loop < 1 : Loop = 1 : EndIf
BigInt::Assign(BZahl_1,BZahl)
BigInt::Subtract(BZahl_1,BEins)
BigInt::Assign(BD,BZahl_1)
r = 0
While BD\q[0] & 1 = 0
BigInt::Divide(BD,BD,BZwei,BReminder)
r + 1
Wend
While Loop > 0
Loop - 1
length = 0
While length = 0 Or (length = 1 And BA\q[0] < 2)
RandomData(@BA,BigInt::#BigIntBits >> 6)
If BA\q[(BigInt::#BigIntBits >> 6)-1] & BitMask
BigInt::NEG(BA)
EndIf
BigInt::Divide(BA,BA,BZahl_1,BReminder)
BigInt::Assign(BA,BReminder)
length = BigInt::NumberSize(BA)
Wend
BigInt::ModPow(BX,BA,BD,BZahl)
If BigInt::Compare(BX,BEins) = 0 Or BigInt::Compare(BX,BZahl_1) = 0
Continue
EndIf
lp = r
While lp > 0
BigInt::ModMul(BX,BX,BZahl)
If BigInt::Compare(BX,BEins) = 0
ProcedureReturn #False
EndIf
CheckBZE = BigInt::Compare(BX,BZahl_1)
If CheckBZE = 0
Break
EndIf
lp -1
Wend
If CheckBZE <> 0
ProcedureReturn #False
EndIf
Wend
ProcedureReturn #True
EndProcedure
CompilerIf #PB_Compiler_IsMainFile
Procedure.s GetDec(*Original.BigInt::BigInt)
Protected Result.s, BitMask.q, Sign, length
Protected.BigInt::BigInt Teiler, r, n
BitMask = $8000000000000000
length = BigInt::#BigIntBits >> 6
BigInt::Assign(n,*Original)
BigInt::SetValue(Teiler,10)
If n\q[length-1] & BitMask
BigInt::Neg(n)
Sign = #True
EndIf
Repeat
BigInt::Divide(n, n, Teiler, r)
Result = Str(r\q[0]) + Result
Until BigInt::isZero(n) <> 0
If Sign
Result= "-" + Result
EndIf
ProcedureReturn Result
EndProcedure
Define.BigInt::BigInt n0
BigInt::SetHexValue(n0,"7ffffffffffffffffffffffffff")
; #BigIntBits ist in der BigInt-Lib auf 2048 gesetzt
; daher maximal 2^1024-1 = 1797693134862315907729305190789024733617976978
; übergeben 9423065727343008115773267580550096313270847732
; 2407536021120113879871393357658789768814416622
; 4928474306394741243777678934248654852763022196
; 0124609411945308295208500576883815068234246288
; 1473913110540827237163350510684586298239947245
; 938479716304835356329624224137215
; für größere Werte muss die #BigIntBits-Konstante erhöht werden
Debug "zu prüfende Zahl: $" + BigInt::GetHex(n0) + " = " + GetDec(n0)
If isPrime(n0)
Debug "ist eine Primzahl"
Else
Debug "ist keine Primzahl"
EndIf
CompilerEndIf