imported>RolandIllig: /* Beispielimplementierung in Python */ idiomatisches Python 3; insbesondere die Leerzeichen rund um die Operatoren waren irreführend

2023-12-20T23:25:01Z

Beispielimplementierung in Python: idiomatisches Python 3; insbesondere die Leerzeichen rund um die Operatoren waren irreführend

Neue Seite

[[Datei:LucasTheorieDesFonctions1878.png|miniatur|500px|Ausschnitt von Seite 316 der Arbeit ''Théorie des Fonctions Numériques Simplement Périodiques'' von [[Édouard Lucas]] (1878)]]
Der '''Lucas-Lehmer-Test''' ist ein [[Primzahltest]] für [[Mersenne-Zahl]]en, das heißt für Zahlen der Form <math>M_n = 2^n - 1</math>. Der Test wird im [[Great Internet Mersenne Prime Search|GIMPS-Projekt]] (engl.: ''Great Internet Mersenne Prime Search'') – der Suche nach bisher nicht bekannten Mersenne-Primzahlen – angewandt.

Dieser Test beruht auf Eigenschaften der [[Lucas-Folge]]n und nicht wie der [[Lucas-Test (Mathematik)|Lucas-Test]] auf dem [[Kleiner Fermatscher Satz|kleinen Fermatschen Satz]].

== Funktionsweise ==
Der Lucas-Lehmer-Test funktioniert wie folgt:
: Sei <math>p</math> ungerade und prim. Die Folge <math>S(k)</math> sei definiert durch <math>S(1)=4, S(k+1)=S(k)^2-2</math>.
: Dann gilt: <math>M_p=2^p-1</math> ist genau dann eine Primzahl, wenn <math>S(p-1)</math> durch <math>M_p</math> teilbar ist.<ref>Zum Beweis siehe Ribenboim: ''Die Welt der Primzahlen'', S. 78/79.</ref>
Dieser Satz wurde 1930 von [[Derrick Henry Lehmer]] gefunden und geht auf [[Édouard Lucas]] zurück (siehe Abbildung).
Mit Hilfe der [[Modulo]]-Funktion mod lässt sich der Satz so formulieren:
: Seien <math>S(1)=4</math> und <math>S(k+1)\equiv S(k)^2-2\ mod\ M_p</math>. Dann gilt: <math>M_p</math> ist genau dann eine Primzahl, wenn <math>S(p-1)=0</math>.

Die Modulo-Funktion bzgl. einer Mersenne-Zahl lässt sich im [[Dualsystem]] (Binärsystem) besonders einfach berechnen, da die Mersenne-Zahl darin nur aus lauter Einsen bestehen.

== Beispiele ==
Beispiel 1: Wir prüfen mit diesem Verfahren, ob <math>M_5=2^5-1=31</math> eine Primzahl ist:
S(1) = 4
S(2) = ( 4² - 2) mod 31 = 14 mod 31 = 14
S(3) = (14² - 2) mod 31 = 194 mod 31 = 8
S(4) = ( 8² - 2) mod 31 = 62 mod 31 = 0
Da <math>S(4)=0</math> ist, ist <math>M_5=31</math> eine Primzahl.

Beispiel 2: Wir prüfen, ob <math>M_{11}=2^{11}-1=2047</math> eine Primzahl ist:
S( 1) = 4
S( 2) = ( 4² - 2) mod 2047 = 14 mod 2047 = 14
S( 3) = ( 14² - 2) mod 2047 = 194 mod 2047 = 194
S( 4) = ( 194² - 2) mod 2047 = 37634 mod 2047 = 788
S( 5) = ( 788² - 2) mod 2047 = 620942 mod 2047 = 701
S( 6) = ( 701² - 2) mod 2047 = 491399 mod 2047 = 119
S( 7) = ( 119² - 2) mod 2047 = 14159 mod 2047 = 1877
S( 8) = (1877² - 2) mod 2047 = 3523127 mod 2047 = 240
S( 9) = ( 240² - 2) mod 2047 = 57598 mod 2047 = 282
S(10) = ( 282² - 2) mod 2047 = 79522 mod 2047 = 1736
Da <math>S(10)>0</math> ist, ist <math>M_{11}=2047</math> keine Primzahl (es gilt <math>2047 = 23\cdot 89</math>).

Beispiel 3: Wir prüfen, ob <math>M_{19}=2^{19}-1 = 524287</math> eine Primzahl ist:
S( 1) = 4
S( 2) = ( 4² - 2) mod 524287 = 14
S( 3) = ( 14² - 2) mod 524287 = 194
S( 4) = ( 194² - 2) mod 524287 = 37634
S( 5) = ( 37634² - 2) mod 524287 = 218767
S( 6) = ( 218767² - 2) mod 524287 = 510066
S( 7) = ( 510066² - 2) mod 524287 = 386344
S( 8) = ( 386344² - 2) mod 524287 = 323156
S( 9) = ( 323156² - 2) mod 524287 = 218526
S(10) = ( 218526² - 2) mod 524287 = 504140
S(11) = ( 504140² - 2) mod 524287 = 103469
S(12) = ( 103469² - 2) mod 524287 = 417706
S(13) = ( 417706² - 2) mod 524287 = 307417
S(14) = ( 307417² - 2) mod 524287 = 382989
S(15) = ( 382989² - 2) mod 524287 = 275842
S(16) = ( 275842² - 2) mod 524287 = 85226
S(17) = ( 85226² - 2) mod 524287 = 523263
S(18) = ( 523263² - 2) mod 524287 = 0
Da <math>S_{18}=0</math> ist, ist <math>M_{19} = 524287</math> eine Primzahl (dies ist schon seit 1603 bekannt).

== Beispielimplementierung in Python ==
Das folgende Programm implementiert den Lucas-Lehmer-Test in der Programmiersprache [[Python (Programmiersprache)|Python]]. In Python ist es möglich, mit beliebig großen ganzen Zahlen zu rechnen, die nur durch den verfügbaren Speicher begrenzt sind. Die hier vorgestellte Implementierung berücksichtigt nicht, dass der Lucas-Lehmer-Test idealerweise bereits abbricht, wenn <math>p</math> gerade oder nicht-prim ist, dies wird dem Nutzer überlassen. So würde das Programm bei Eingabe von <math>p = 2</math> die falsche Aussage liefern, dass die Zahl 3 keine Mersenne-Primzahl ist.
[[Datei:MersennePrimeStamp.gif|miniatur|Briefstempel zur Entdeckung der Mersenne-Primzahl 2<sup>11213</sup>-1]]
Auf einem [[Intel Pentium 4]] aus dem Jahr 2005 benötigt die Rechnung für <math>p = 11213</math> mit diesem Programm nur 41 Sekunden. Die Rechnung im Jahr 1963, mit der nachgewiesen wurde, dass <math>M_{11213}</math> prim ist, dauerte dagegen mit einem damaligen [[Supercomputer]] Illiac II<ref>''[[:en:ILLIAC II|ILLIAC II]]'' in der englischsprachigen Wikipedia</ref> noch 2¼ Stunden.<ref>Donald B. Gillies: [http://www.jstor.org/pss/2003409 ''Three new Mersenne primes and a statistical theory'']</ref>

<syntaxhighlight lang="python">
def ist_prim(p):
m = 2 ** p - 1
s = 4
for i in range (2, p):
s = (s * s - 2) % m
return s == 0

p = int(input('Exponent p von 2^p-1 '))
eine_oder_keine = 'eine' if ist_prim(p) else 'keine'
print(f'2^{p} - 1 ist {eine_oder_keine} Mersenne-Primzahl')
</syntaxhighlight>

== Literatur ==
* [[Paulo Ribenboim]]: ''Die Welt der Primzahlen. Geheimnisse und Rekorde.'' Springer Verlag, Berlin u. a. 2006, ISBN 3-540-34283-4 (''Springer-Lehrbuch'').
* [[Édouard Lucas]]: ''Théorie des Fonctions Numériques Simplement Périodiques.'' In: ''American Journal of Mathematics.'' 1, No. 4, 1878, S. 289–321, {{ISSN|0002-9327}} (dritter Teil der Abhandlung).
* [[Derrick Henry Lehmer]]: ''An extended theory of Lucas’ functions.'' In: ''The Annals of Mathematics.'' 31, No. 3, 1930, S. 419–448, {{ISSN|0003-486X}}.<br /> ([http://bancroft.berkeley.edu/Exhibits/Math/dhla.html erste Seite seiner Doktorarbeit von 1930 in einer Ausstellung in Berkeley sowie weitere Photos]).

== Einzelnachweise ==
<references />

[[Kategorie:Primzahl]]

Lucas-Lehmer-Test - Versionsgeschichte

imported>RolandIllig: /* Beispielimplementierung in Python */ idiomatisches Python 3; insbesondere die Leerzeichen rund um die Operatoren waren irreführend