Benutzer:Tanik/Lucas-Lehmer-Test für Mersennezahlen



Lucas-Lehmer-Test für Mersennezahlen



Im Lucas-Lehmer-Test für Mersennezahlen besteht die Schwierigkeit darin, die Primfaktoren von und entsprechende Lucas-Folgen zu finden. Die Mersennezahlen haben die Eigenschaft, dass in diesem Fall eine Potenz von 2 ist und hat nur einen Primfaktor. Deshalb können wir Lucas-Lehmer-Test für Mersennezahlen so formulieren:


Wenn eine Lucas-Folge mit


bei

existiert, dann ist prim.



und haben höchstens als gemeisamen Teiler, sprich .


Die Bedingungen und können zusammengefasst werden.

Es gilt womit sein muss. Durch allgemeine Bedingung an Lucas-Folgen für Primzahltests und Lemma auch klar, dass wenn den Faktor enthält, sein muss. Es gegügt demnach zu überprüfen.


Es sei

Die Berechnung dadurch die Form Begonnen wird die Rekursion mit und die Frage bezüglich der Primalität von lässt sich wie folgt formulieren: wann ist


Die Werte ergeben eine passende Lucas-Folge, das führt zu

Dadurch sieht die Rekursion wie folgt aus: mit dem Startwert


Es sei m ungerade, dann ist genau dann prim, wenn , wobei und .





Verbesserter Lucas-Lehmer-Test für Mersennezahlen



Sei für eine ungerade Primzahl. Die Folge sei rekursiv definiert durch und . Dann ist genau dann prim, falls die Zahl teilt.



Man zeige, dass prim ist.


Wir berechnen alle aus:


,

,

,

.


Daraus nach verbessertem Lucas-Lehmer-Test für Mersennezahlen folgt, dass die Zahl prim ist.


Man zeige, dass nicht prim ist.


Wir berechnen alle aus:


,


,


,


,


.


D.h. und nach verbessertem Lucas-Lehmer-Test für Mersennezahlen folgt, dass die Zahl nicht prim ist. Und tatsächlich .


Literatur

  • Müller-Stach,S./Piontkowski, J.: Elementare und algebraische Zahlentheorie. 1. Auflage Wiesbaden : Vieweg, 2006, ISBN 978-3-8348-0211-8
  • Paulo Ribenboim, Die Welt der Primzahlen: Geheimnisse und Rekorde, Springer-Verlag Berlin Heidelberg, 2006 ISBN 978-3-540-34284-7
  • Riesel,H.: Prime Numbers and Computer Methods for Factorization, Birkhäuser, ISBN 0-8176-3291-3
  • Burton, D.M./Dalkowski, H.: Handbuch der elementaren Zahlentheorie. Neldermann Verlag, 2005, ISBN 3-88538-112-5