Benutzer:Abrankov/Vorlesung/Lucas-Test (A.Brankova und T.Nikolaenkova)

Aus Wikiversity

„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


Édouard Lucas



Satz (Lucas Test)  

Eine natürliche Zahl ist genau dann eine Primzahl, wenn es eine

natürliche Zahl gibt mit

für alle Primteiler von .

Beweis  

Benutzer:Abrankov/Lucas Test/Fakt/Beweis



Beispiel  

Wir wollen zeigen, dass prim ist. Wegen folgt dies aus

,
,
.


Eine direkte Verallgemeinerung des Lucas Test ist der Pocklington Test:



Satz (Pocklington)  

Sei eine natürliche Zahl, so dass eine Faktorisierung der Form besitzt, wobei alle Primteiler von bekannt sind. Weiterhin gebe es eine natürliche Zahl mit
für alle Primteiler von . Ist dann , so ist eine Primzahl.

Beweis  


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:



Satz (Pepin Test)  

Die Zahl

, ist genau dann eine Primzahl, falls

Beweis  

Benutzer:Abrankov/Pepin Test/Beweis



Beispiel  

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:

  1. Man muss die Primteiler von kennen. Dies ist ein Faktorisierungsproblem und damit im Allgemeinen schwierig.
  2. 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.



Satz (Miller-Rabin Test)

Sei ungerade und ungerade. ist genau dann eine Primzahl, wenn für jede zu teilerfremde Zahl gilt
Ist keine Primzahl, so erfüllt höchstens ein Viertel alle Zahlen eine der Bedingungen.


Beispiel  

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



Definition (Lucas-Folgen)  

Gegeben sei die Gleichung mit und , die Lösungen seien die reellen Zahlen und . und werden durch

definiert und Lucas-Folgen genannt.


Bemerkung  

Die Gleichung hat Diskriminante und damit die Lösungen

Man beachte, dass


Bemerkung (Eigenschaften der Folgeglieder)  

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



Definition (Quadratischer Zahlenkörper)  

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.



Satz  

Wenn und eine ungerade Primzahl, dann

oder

Beweis  

Benutzer:Tanik/Lucas-Test/Fakt/Beweis


Falls in eine Einheit ist, dann folgt aus dem Satz, dass

oder



Lemma  

Die Bedingung in , ist identisch mit der Bedingung in .

Beweis  


Aus Identitäten ergeben sich für und folgende Berechnungen(beachte :

Bemerkung  

  1. soll wegen Division nicht sein
  2. daraus folgt, dass sein muss
  3. 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

weil alle Terme abseits des ersten stets den Faktor enthalten.

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.



Lemma  

Sei . Es existiert ein , sodaß die Menge und hat die Form .

Beweis  



Satz (Lucas-Lehmer-Test)  

Sei mit paarweise verschiedenen Primzahlen. Sei eine Lucas-Folge mit und


Ist nun ,

so ist prim.

Beweis  






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:


Bemerkung (Lucas-Lehmer-Test für Mersennezahlen)  

Wenn eine Lucas-Folge mit


bei

existiert, dann ist prim.



Lemma  

und haben höchstens als gemeisamen Teiler, sprich .

Beweis  


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 .

Bemerkung (Lucas-Lehmer-Test für Mersennezahlen alternativ)  

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





Verbesserter Lucas-Lehmer-Test für Mersennezahlen



Satz (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.

Beweis  



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.



Beispiel  

Man zeige, dass prim ist.


Wir berechnen alle aus:


,

,

,

.


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


Beispiel  

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