Mersenne-Primzahlen mit Lucas-Lehmer-Test

Übersicht

BlitzBasic

Codearchiv

	Triton Betreff: Mersenne-Primzahlen mit Lucas-Lehmer-Test	Mo, Okt 31, 2005 22:17 Antworten mit Zitat
Joa, Mersenne-Primzahlen sind die Primzahlen, die eine spezielle Form haben. Die aktuell höchste Primzahl ist zugleich eine M-Pz. Diese besonderen Form lautet 2^p -1 wobei p selbst eine Pz ist. Anders als bei normalen Pz-Tests (auch hier im Codearchiv, u.A von mir) wird die Zahl nicht auf mögliche Teiler geprüft, sondern...naja, es werden sich verschiedene spezielle Eigenschaften dieser Zahlen zunutze gemacht. Genau erklären kann ich es nicht - und es würde auch den Rahmen sprengen. Ein LLT für p=13 würde dann jedenfalls so aussehen: Code: [AUSKLAPPEN] [EINKLAPPEN] 2^13 -1= 8191 s(1) = 4 s(2) = (4² - 2) mod 8191 = 14 s(3) = (14² - 2) mod 8191 = 194 s(4) = (194² - 2) mod 8191 = 4870 s(5) = (4870² - 2) mod 8191 = 3953 s(6) = (3953² - 2) mod 8191 = 5970 s(7) = (5970² - 2) mod 8191 = 1857 s(8) = (1857² - 2) mod 8191 = 1294 s(9) = (1294² - 2) mod 8191 = 3470 s(10) = (3470² - 2) mod 8191 = 128 s(11) = (128² - 2) mod 8191 = 0 Wenn 0 rauskommt, handelt es sich um eine M-Pz. nach diesem Prinzip funktioniert auch die GIMPS (great internet mersenne primes search), mit der 2^25964951 -1 gefunden wurde, die derzeit größte Pz. BB kann es jedenfalls Standardmäßig nur bis p=13. Darüber braucht man spezielle Rechenfunktionen auf Stringbasis, welche z.B. Rallimen schonmal irgendwo beigesteuert hat. Für folgene p liegt die Mersenne-Primzahl noch im von BB bearbeitbaren Bereich: 2,3,5,7,13 Code: [AUSKLAPPEN] [EINKLAPPEN] ; Lucas-Lehmer-Test zum testen von Mersenne-Primzahlen ; 2^p -1 ; 31.10.2005 by Triton ;Probleme: zu kleiner zahlenbereich - schon bei p=17 wird 2^31 gesprengt ; http://www.silizium-net.de AppTitle "Mersenne-Primzahlen" Graphics 640,480,16,2 p=13 Print "2^"+p+" -1" a=llt(p) If a = 1 Then Print "-> "+Str(zweihochx(p)-1)+" ist eine M-Primzahl" If a = 0 Then Print "-> "+Str(zweihochx(p)-1)+" ist keine M-Primzahl" WaitKey End ;--- Function llt(p) pz=zweihochx(p)-1 s=4 For oft1 = 2 To p-1 s=(ss-2) Mod pz DebugLog s Print oft1+" - "+s+" - "+Str(ss-2) Next If s=0 Then Return 1 End Function ;--- Function zweihochx(x) b=2 For oft2=1 To x-1 b=b+b Next Return b End Function
Coding: silizium-net.de \| Portfolio: Triton.ch.vu

Triton

Betreff: Mersenne-Primzahlen mit Lucas-Lehmer-Test

Mo, Okt 31, 2005 22:17
Antworten mit Zitat

Joa, Mersenne-Primzahlen sind die Primzahlen, die eine spezielle Form haben. Die aktuell höchste Primzahl ist zugleich eine M-Pz.
Diese besonderen Form lautet 2^p -1 wobei p selbst eine Pz ist.

Anders als bei normalen Pz-Tests (auch hier im Codearchiv, u.A von mir)
wird die Zahl nicht auf mögliche Teiler geprüft, sondern...naja, es werden sich verschiedene spezielle Eigenschaften dieser Zahlen zunutze gemacht.
Genau erklären kann ich es nicht - und es würde auch den Rahmen sprengen.

Ein LLT für p=13 würde dann jedenfalls so aussehen:
Code: [AUSKLAPPEN]

2^13 -1= 8191
s(1) = 4
s(2) = (4² - 2) mod 8191 = 14
s(3) = (14² - 2) mod 8191 = 194
s(4) = (194² - 2) mod 8191 = 4870
s(5) = (4870² - 2) mod 8191 = 3953
s(6) = (3953² - 2) mod 8191 = 5970
s(7) = (5970² - 2) mod 8191 = 1857
s(8) = (1857² - 2) mod 8191 = 1294
s(9) = (1294² - 2) mod 8191 = 3470
s(10) = (3470² - 2) mod 8191 = 128
s(11) = (128² - 2) mod 8191 = 0

Wenn 0 rauskommt, handelt es sich um eine M-Pz.

nach diesem Prinzip funktioniert auch die GIMPS (great internet mersenne primes search), mit der 2^25964951 -1 gefunden wurde, die derzeit größte Pz.

BB kann es jedenfalls Standardmäßig nur bis p=13. Darüber braucht man spezielle Rechenfunktionen auf Stringbasis, welche z.B. Rallimen schonmal irgendwo beigesteuert hat.

Für folgene p liegt die Mersenne-Primzahl noch im von BB bearbeitbaren Bereich:
2,3,5,7,13

Code: [AUSKLAPPEN]

;** Lucas-Lehmer-Test zum testen von Mersenne-Primzahlen
;** 2^p -1
;** 31.10.2005 by Triton
;Probleme: zu kleiner zahlenbereich - schon bei p=17 wird 2^31 gesprengt
;** http://www.silizium-net.de
AppTitle "Mersenne-Primzahlen"
Graphics 640,480,16,2

p=13
Print "2^"+p+" -1"
a=llt(p)
If a = 1 Then Print "-> "+Str(zweihochx(p)-1)+" ist eine M-Primzahl"
If a = 0 Then Print "-> "+Str(zweihochx(p)-1)+" ist keine M-Primzahl"
WaitKey
End

;---
Function llt(p)
pz=zweihochx(p)-1
s=4
For oft1 = 2 To p-1
s=(s*s-2) Mod pz
DebugLog s
Print oft1+" - "+s+" - "+Str(s*s-2)
Next
If s=0 Then Return 1

End Function

;---
Function zweihochx(x)
b=2
For oft2=1 To x-1
b=b+b
Next
Return b
End Function

Coding: silizium-net.de | Portfolio: Triton.ch.vu