Primzahl Prüfung Miller-Rabin Test

Hier könnt Ihr gute, von Euch geschriebene Codes posten. Sie müssen auf jeden Fall funktionieren und sollten möglichst effizient, elegant und beispielhaft oder einfach nur cool sein.
Benutzeravatar
NicknameFJ
Beiträge: 324
Registriert: 03.06.2007 14:36
Wohnort: Von der Sonne aus gesehen der dritte Planet

Re: Primzahl Prüfung Miller-Rabin Test

Beitrag von NicknameFJ »

@Helle: Meine Assembler - Kenntnisse sind doch schon ziemlich eingerostet daher bin ich gleich auf BigInt umgestiegen. Aber für Deine Variante :allright:

aus Wikipedia:
Wenn die Zahl n klein ist, ist es nicht notwendig, alle a < 2(ln n)2 zu testen, da bekannt ist, dass eine viel kleinere Anzahl ausreichend ist. Beispielsweise haben Pomerance, Selfridge und Wagstaff sowie Jaeschke folgendes verifiziert:

Wenn n < 1.373.653, genügt es, a = 2 und 3 zu testen,
wenn n < 9.080.191, genügt es, a = 31 und 73 zu testen,
wenn n < 4.759.123.141, genügt es, a = 2, 7, und 61 zu testen,
wenn n < 2.152.302.898.747, genügt es, a = 2, 3, 5, 7, und 11 zu testen,
wenn n < 3.474.749.660.383, genügt es, a = 2, 3, 5, 7, 11, und 13 zu testen,
wenn n < 341.550.071.728.321, genügt es, a = 2, 3, 5, 7, 11, 13, und 17 zu testen.
wenn n < 3.825.123.056.546.413.051, genügt es, a = 2, 3, 5, 7, 11, 13, 17, 19, und 23 zu testen.
wenn n < 318.665.857.834.031.151.167.461, genügt es, a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, und 37 zu testen.

Dabei dürfen nur solche n getestet werden, die größer sind als das jeweils größte angegebene a.
Da die angegebene Zahl 318.665.857.834.031.151.167.461 größer ist als die größte positive QUAD und die größste zu prüfende Zahl ja in eine positive QUAD passen muss, kann man den Algo mit obigen Angaben auch recht einfach in einen deterministischen ändern und wirklich sicher sein dass bei Rückgabe #True die Zahl auch eine Primzahl ist.

Wenn ich die Tage mal Zeit finde baue ich die Procedure vlt. um sodass auch Zahlen größer als QUAD getestet werden können. Dann aber wieder mit BigInt auch wenn es deutlich langsamer ist als die Variante von Helle. Oder einer von Euch kommt mir da zuvor :mrgreen:
PS: Alle im Text enthaltenen Schreibfehler sind beabsichtigt und dienen der Belustigung aller

Bild
Dextro
Beiträge: 1
Registriert: 05.01.2018 21:46

Re: Primzahl Prüfung Miller-Rabin Test

Beitrag von Dextro »

Als stiller Mitleser habe ich alle Beiträge interessiert verfolgt und kann nur staunen was Ihr Profis imstande seid zu leisten. Zu diesem Thema habe ich heute zufällig einen Bericht über einen neuen WR gelesen, den ich Euch nicht vorenthalten möchte, wenn Ihr es noch nicht gelesen habt.

https://www.mersenne.org/primes/

Schöne Grüße
Dextro
Benutzeravatar
NicknameFJ
Beiträge: 324
Registriert: 03.06.2007 14:36
Wohnort: Von der Sonne aus gesehen der dritte Planet

Re: Primzahl Prüfung Miller-Rabin Test

Beitrag von NicknameFJ »

Eine Variante die komplett mit BigInt arbeitet im ersten Post hinzugefügt. Dadurch können theoretisch beliebig große Zahlen getestet werden; vgl. Hinweise im ersten Post.
PS: Alle im Text enthaltenen Schreibfehler sind beabsichtigt und dienen der Belustigung aller

Bild
Benutzeravatar
STARGÅTE
Kommando SG1
Beiträge: 6996
Registriert: 01.11.2005 13:34
Wohnort: Glienicke
Kontaktdaten:

Re: Primzahl Prüfung Miller-Rabin Test

Beitrag von STARGÅTE »

Hallo NicknameFJ und Helle,

ich habe mal eure Codes als Vorlage für einen vollständig deterministischen Test für Primzahlen im gesamten Quad-Bereich (2^63-1) verwendet.
Zur Geschwindigkeitsoptimierung teste ich nebenbei vorher erst noch kleine Primzahlen bis 19 und nehme dann je nach Zahl ein bestimmtes Set an Witness Basen (Siehe Wiki). Damit konnte ich gegenüber Helles Version noch mal n Faktor 3 rausholen bei Zahlen zwischen 1 und 10^8

Diese Codeversion läuft jedoch nur auf x64 und im ASM-backend!

Code: Alles auswählen

CompilerIf #PB_Compiler_Processor <> #PB_Processor_x64 Or (Defined(PB_Compiler_Backend, #PB_Constant) And #PB_Compiler_Backend <> #PB_Backend_Asm)
	CompilerError "Olny for ASM-backend and x64 processor"
CompilerEndIf

Structure IntegerArray
	i.i[0]
EndStructure
Structure QuadArray
	q.q[0]
EndStructure

Procedure.i IsPrime(Value.q)
	
	; https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
	; https://en.wikipedia.org/wiki/Exponentiation_by_squaring
	; https://www.purebasic.fr/german/viewtopic.php?f=8&t=30523
	; Thanks to NicknameFJ und Helle
	
	Protected *Try.Integer, Loops.i, Exponent.q, Index.i, Base.q
	Protected *Comparison.QuadArray     = ?Lower
	Protected *Label.IntegerArray       = ?Label
	Protected *SmallPrimes.IntegerArray = ?SmallPrimes
	
	If Value < 0
		Value = -Value
	EndIf
	
	; Testing small primes and divisibility using small primes
	If Value < 20
		ProcedureReturn *SmallPrimes\i[Value]
	ElseIf Value & 1 = 0 Or Value % 3 = 0 Or Value % 5 = 0 Or Value % 7 = 0 Or
	       Value % 11 = 0 Or Value % 13 = 0 Or Value % 17 = 0 Or Value % 19 = 0
		ProcedureReturn #False
	EndIf
	
	; Determine the required determenistic list for test bases
	*Try = ?Lower_18446744073709551616
	For Index = 0 To 10
		If Value < *Comparison\q[Index]
			*Try = *Label\i[Index]
			Break
		EndIf
	Next
	
	; Solve: 2^Loops * Exponent + 1 = Value
	! MOV   rax, [p.v_Value]
	! DEC   rax
	! BSF   rcx, rax
	! MOV   [p.v_Loops], rcx
	! SHR   rax, cl
	! MOV   [p.v_Exponent], rax
	
	; Witness loop
	While *Try\i
		
		Base = *Try\i
		
		; rax = Base^Exponent % Value
		! MOV  r8, [p.v_Exponent]
		! MOV  r9, [p.v_Value]
		! MOV  rax, 1
		! BSR  rcx, r8
		Loop:
			! MUL  rax
			! DIV  r9
			! MOV  rax, rdx
			! BT   r8, rcx
			! JNC @F
				! MUL  qword [p.v_Base]
				! DIV  r9
				! MOV  rax, rdx
			!@@:
			! DEC  rcx
		! JNS ll_isprime_loop
		
		; rax = 1 or rax = Value-1 ?
		! MOV  r8, r9
		! DEC  r8
		! CMP  rax, 1
		! JE  ll_isprime_nexttry
		! CMP  rax, r8
		! JE  ll_isprime_nexttry
		
		; Square-Mod-Loop: rax = rax^2 % Value  and check for  rax = Value-1
		! MOV  rcx, [p.v_Loops]
		!@@:
			! MUL  rax
			! DIV  r9
			! MOV  rax, rdx
			! CMP  rax, r8
			! JE   ll_isprime_nexttry
			! CMP  rax, 1
			! JBE  ll_isprime_noprime
			! DEC  rcx
		! JNZ @B
		
		NoPrime:
		ProcedureReturn #False
		
		NextTry:
		*Try + SizeOf(Integer)
		
	Wend
	
	ProcedureReturn #True
	
	; IsPrime() for n = 0 to 19
	DataSection
		SmallPrimes:
		Data.i #False, #False, #True, #True, #False, #True, #False, #True, #False, #False
		Data.i #False, #True, #False, #True, #False, #False, #False, #True, #False, #True
	EndDataSection
	
	; Witness bases
	DataSection 
		Lower_2047:                 : Data.i 2, 0
		Lower_1373653:              : Data.i 2, 3, 0
		Lower_9080191:              : Data.i 31, 73, 0
		Lower_25326001:             : Data.i 2, 3, 5, 0
		Lower_3215031751:           : Data.i 2, 3, 5, 7, 0
		Lower_4759123141:           : Data.i 2, 7, 61, 0
		Lower_1122004669633:        : Data.i 2, 13, 23, 1662803, 0
		Lower_2152302898747:        : Data.i 2, 3, 5, 7, 11, 0
		Lower_3474749660383:        : Data.i 2, 3, 5, 7, 11, 13, 0
		Lower_341550071728321:      : Data.i 2, 3, 5, 7, 11, 13, 17, 0
		Lower_3825123056546413051:  : Data.i 2, 3, 5, 7, 11, 13, 17, 19, 23, 0
		Lower_18446744073709551616: : Data.i 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 0
	EndDataSection
	
	; Witness bases index
	DataSection
		Lower:
		Data.q 2047, 1373653, 9080191, 25326001, 3215031751, 4759123141, 1122004669633
		Data.q 2152302898747, 3474749660383, 341550071728321, 3825123056546413051
		Label:
		Data.i ?Lower_2047, ?Lower_1373653, ?Lower_9080191, ?Lower_25326001, ?Lower_3215031751
		Data.i ?Lower_4759123141, ?Lower_1122004669633, ?Lower_2152302898747
		Data.i ?Lower_3474749660383, ?Lower_341550071728321, ?Lower_3825123056546413051
	EndDataSection
	
EndProcedure


OpenConsole()

Define N.i, Count.i
Define Time.q = ElapsedMilliseconds()
For N = 0 To 10000000
	If IsPrime(N)
		Count + 1
	EndIf
Next
PrintN("Prime numbers: "+Str(Count))
PrintN("Evaluation time: "+Str(ElapsedMilliseconds()-Time))

Input()
PB 6.01 ― Win 10, 21H2 ― Ryzen 9 3900X, 32 GB ― NVIDIA GeForce RTX 3080 ― Vivaldi 6.0 ― www.unionbytes.de
Aktuelles Projekt: Lizard - Skriptsprache für symbolische Berechnungen und mehr
Benutzeravatar
NicknameFJ
Beiträge: 324
Registriert: 03.06.2007 14:36
Wohnort: Von der Sonne aus gesehen der dritte Planet

Re: Primzahl Prüfung Miller-Rabin Test

Beitrag von NicknameFJ »

Hallo STARGÅTE,

cool. Danke für die Verbesserung.

NicknameFJ
PS: Alle im Text enthaltenen Schreibfehler sind beabsichtigt und dienen der Belustigung aller

Bild
Antworten