Benutzer:Abrankov/Vorlesung/Lucas-Test (A.Brankova und T.Nikolaenkova)
„Es wird wohl noch mindestens eine Million Jahre vergehen, bevor wir die Primzahlen verstehen“ Paul Erdös
Eine wesentliche Rolle in der Zahlentherie spielt der Begriff der Primzahl. Diese Arbeit beschäftigt sich mit der Bestimmung der Primalität einer Zahl mit Hilfe von Lucas-Test.
- Lucas-Test
- Primzahltests auf Grundlage von Kongruenzen
natürliche Zahl gibt mit
Wir wollen zeigen, dass prim ist. Wegen folgt dies aus
- ,
- ,
- .
Eine direkte Verallgemeinerung des Lucas Test ist der Pocklington Test:
Die anderen berühmten Primzahlen sind die Fermatschen Primzahlen, obwohl man davon nur 5 Stück kennt und vermutet, dass es keine weiteren gibt. Auch für diese Zahlen gibt es einen speziellen Test, den Pepin Test. Er beruht auf dem Lucas Test, der immer anwendbar ist, wenn man die Primteiler von kennt. Für die Fermatschen Primzahlen reicht es aus, im Lucas Test die Zahl zu überprüfen:
, ist genau dann eine Primzahl, falls
Da doppelt exponentiell in wächst, kann man den Test per Hand nur für sehr kleine durchführen. Wir betrachten hier . Diese Zahl ist prim, weil
Bei der Anwendung des Lucas Tests auf eine beliebige Zahl gibt es zwei Probleme:
- Man muss die Primteiler von kennen. Dies ist ein Faktorisierungsproblem und damit im Allgemeinen schwierig.
- Man muss alle Werte für überprüfen. Dies bedeutet einen sehr hohen Rechenaufwand. (Die Anzahl könnte man verkleinern, wenn man berücksichtigt, dass es Primitivwurzeln modulo für prim gibt. Man bleibt aber in der gleichen Größenordnung für den Rechenaufwand.)
Um das erste Problem in den Griff zu bekommen, könnte man hoffen, dass ein bereits prim ist, falls ist für alle zu teilerfremden im Bereich von bis . Das ist aber leider nicht richtig.
Wir möchten überprüfen, ob 89 mit Miller-Rabin Test eine Primzahl ist. Es gilt , also . Wir testen für zwei zufällige Zahlen und erhalten wir:
Die zwei Testzahlen erfüllen die Testbedingung.
- Primzahltests auf Grundlage von Lucas-Folgen
- Lucas-Folgen
Gegeben sei die Gleichung mit und , die Lösungen seien die reellen Zahlen und . und werden durch
definiert und Lucas-Folgen genannt.
Die Gleichung hat Diskriminante und damit die Lösungen
Man beachte, dass
Die Folgenglieder für kann man leicht ablesen:
Die Lucas-Folgen erfüllen die Rekursion
bzw.
Das heisst, dass jeder Term hängt linear von den zwei vorherigen ab.
Diese Rekursionen kann man durch Nachrechnen überprüfen.
Die Richtigkeit der zweiten Rekursion kann analog gezeigt werden.
Die Lucas-Folgen haben noch weitere Eigenschaften. Man geht davon aus, dass ist, dann gilt:
Daraus für folgt:
und für :
Damit wurde gezeigt, dass alle Folgeglieder aus sind.
- Teilbarkeitseigenschaften der Folgeglieder
Für ein quadratfreies heisst die Menge
quadratischer Zahlenkörper.
Für ein ist dann .
Sei mit und quadratfrei. Ist , so sind die Lösungen der Gleichung irrationale Zahlen aus dem quadratischen Zahlenkörper .
Jeztz kann man ein Pendant zum Kleinen Fermatschen Satz in formulieren.
Falls in eine Einheit ist, dann folgt aus dem Satz, dass
Aus Identitäten ergeben sich für und folgende Berechnungen(beachte :
- soll wegen Division nicht sein
- daraus folgt, dass sein muss
- Zusammen mit muss die Bedingung erfüllt sein.
- Verhalten Potenzen von bzw. bezüglich der Teilbarkeit durch
Falls ist für ein bestimmtes und deshalb gilt
Man kann unter der Bedingung, dass in eine Einheit ist, durch Division durch das Folgende erhalten:
{{math|term= a^{p^n} \equiv a^{p^{n-1} } \Rightarrow a^{{p^n}-{p^{n-1}}} \equiv 1 \Rightarrow a^{p^{n-1}(p-1)} \equiv 1 (mod \,\,p^n)\,|SZ=}}
Analog erhält man
.
Mit diesen Identitäten können die folgenden Folgeglieder berechnet werden:
.
Das lässt sich wie folgt zusammenfassen:
.
Die Beschränkung , folgt aus dem Lemma und Bemerkung oben.
Der Lucas-Lehmer-Test ist ein Verfahren, um Mersenne-Primzahlen zu überprüfen. Entwickelt wurde der Test von Eduardo Luca und Derrick Henry Lehmer, der die Arbeiten von Luca fortsetzte. Als mathematische Grundlagen dienen Lucas-Folgen. Häufigste Verwendung findet der Test beim Suchen von sehr großen Primzahlen. Er ist seit Jahren die effizienteste Methode, um die größten zurzeit bekannten Primzahlen zu entdecken, und wird als Standardtestverfahren beim GIMPS-Projekt (Great Internet Mersenne Prime Search) eingesetzt. Zuerst werden wir der Lucas-Lehmer-Test für beliebige Zahl n zeigen und dann für Mersenne-Primzahlen.
Ist nun ,
- Lucas-Lehmer-Test für Mersennezahlen
Im Lucas-Lehmer-Test für Mersennezahlen die Schwierigkeit besteht darin, die Primfaktoren von und
entsprechende Lucas-Folgen zu finden. Die Mersennezahlen haben die Eigenschaft,
dass in diesem Fall eine Potenz von ist und hat nur einen Primfaktor. Deshalb
können wir Lucas-Lehmer-Test für Mersennezahlen so formulieren:
Wenn eine Lucas-Folge mit
bei
- 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
Das Verfahren eignet sich durch seinen iterativen Charakter in der Praxis sehr gut. Sämtliche grossen Mersenne-Primzahlen wurden auf diese Weise gefunden. Lucas selbst hat im Jahre 1876 die Primalität von nachgewiesen und hat gezeigt, dass zerlegbar ist. Schliesslich gelang es Lehmer 1927 zu zeigen, dass zerlegbar ist und korrigierte damit Mersennes Aussage.
Der Lucas-Lehemer Primzahltest für Mersenne-Zahlen erfordert eine immense Rechenleistung, wenn sehr groß ist. Darüber hinaus kommen sehr spezielle Programme zum Einsatz. Eine große Rolle spielt die Multiplikation mit schneller Fourier-Transformation, die 1971 von Schöhage und Strassen entwickelt wurde. Als maßgeblich haben sich die Programme von Crandall und Woltman herausgestellt.
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
- [B] Brenner H.: Zahlentheorie (Osnabrück 2008) http://de.wikiversity.org/wiki/Zahlentheorie_(Osnabr%C3%BCck_2008)(13.03.09)
- Burton, D.M./Dalkowski, H.: Handbuch der elementaren Zahlentheorie.Neldermann Verlag, 2005, ISBN 3-88538-112-5
- Müller-Stach,S./Piontkowski, J.: Elementare und algebraische Zahlentheorie.1. Auflage Wiesbaden : Vieweg, 2006, ISBN 978-3-8348-0211-8
- Ribenboim, P.: 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