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

Édouard Lucas

Satz (Lucas Test)

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

natürliche Zahl $0<a<n$ gibt mit

$a^{n-1}\equiv 1modn,\text{ aber }{a}^{\frac{n-1}{q}}\equiv ̸1modn$

für alle Primteiler $q$ von $n-1$.

Beweis

Benutzer:Abrankov/Lucas Test/Fakt/Beweis

$◻$

Beispiel

Wir wollen zeigen, dass $n=61$ prim ist. Wegen $n-1=60=2^2\cdot 3\cdot 5$ folgt dies aus

$2^{\frac{60}{2}}=2^{30}=(2^6{)}^5=64^5\equiv 3^5\equiv 60\equiv ̸1mod61$,

$2^{\frac{60}{3}}=2^{20}=(2^6{)}^3\cdot 2^2={64}^3\cdot 2^2\equiv 3^3\cdot 4\equiv 47\equiv ̸1mod61$,

$2^{\frac{60}{5}}=2^{12}=(2^6{)}^2=64^2\equiv 3^2\equiv 9\equiv ̸1mod61$.

Eine direkte Verallgemeinerung des Lucas Test ist der Pocklington Test:

Satz (Pocklington)

Sei $n$ eine natürliche Zahl, so dass $n-1$ eine Faktorisierung der Form $n-1=RF$ besitzt, wobei alle Primteiler von $F$ bekannt sind. Weiterhin gebe es eine natürliche Zahl $0<a<n$ mit

1. $a^{n-1}\equiv 1modn$
2. $ggT(a^{\frac{n-1}{q}}-1,n)=1$

für alle Primteiler $q$ von $F$. Ist dann $F\ge \sqrt{n}$, so ist $n$ eine Primzahl.

Beweis

Benutzer:Abrankov/Pocklington Test/Fakt/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 $n-1$ kennt. Für die Fermatschen Primzahlen reicht es aus, im Lucas Test die Zahl $a=3$ zu überprüfen:

Satz (Pepin Test)

Die Zahl

$F_r=2^{2^r}+\mathrm{1,}r\ge 1$, ist genau dann eine Primzahl, falls

$3^{\frac{F_r-1}{2}}\equiv -1mod{F}_k.$

Beweis

Benutzer:Abrankov/Pepin Test/Beweis

$◻$

Beispiel

Da $F_r$ doppelt exponentiell in $r$ wächst, kann man den Test per Hand nur für sehr kleine $r$ durchführen. Wir betrachten hier $F_2=2^{2^2}+1=2^4+1=17$. Diese Zahl ist prim, weil

$3^{\frac{F_2-1}{2}}=3^{2^3}=3^8=(3^4{)}^2\equiv 13^2\equiv -1mod17.$

Bei der Anwendung des Lucas Tests auf eine beliebige Zahl $n\in \mathbb{N}$ gibt es zwei Probleme:

1. Man muss die Primteiler von $n-1$ kennen. Dies ist ein Faktorisierungsproblem und damit im Allgemeinen schwierig.
2. Man muss alle $n-1$ Werte für $a$ überprüfen. Dies bedeutet einen sehr hohen Rechenaufwand. (Die Anzahl könnte man verkleinern, wenn man berücksichtigt, dass es $\phi (n-1)$ Primitivwurzeln modulo $n$ für $n$ 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 $n\in \mathbb{N}$ bereits prim ist, falls $a^{n-1}\equiv 1modn$ ist für alle zu $n$ teilerfremden $a$ im Bereich von $1$ bis $n-1$. Das ist aber leider nicht richtig.

Satz (Miller-Rabin Test)

Sei $n\ge 3$ ungerade und $n-1=2^{t}m\text{ für }m$ ungerade. $n$ ist genau dann eine Primzahl, wenn für jede zu $n$ teilerfremde Zahl $0<a<n$ gilt

$a^m\equiv 1modn\text{ oder }{2}^{s}m\equiv -1modn\text{ für }\text{ ein }s\in \{0,1,\dots ,t-1\}.$

Ist $n$ keine Primzahl, so erfüllt höchstens ein Viertel alle Zahlen $a$ eine der Bedingungen.

Beispiel

Wir möchten überprüfen, ob 89 mit Miller-Rabin Test eine Primzahl ist. Es gilt $n-1=88=2^3\cdot 11$, also $t=3$. Wir testen für zwei zufällige Zahlen $a=3$ und $a=5$ erhalten wir:

$3^{11}\equiv 37modn$

$3^{2.11}\equiv 37^2\equiv 34modn$

$3^{4.11}\equiv 37^2\equiv -1modn$

$5^{11}\equiv 55modn$

$5^{2.11}\equiv 55^2\equiv -1modn$

Die zwei Testzahlen erfüllen die Testbedingung.

Primzahltests auf Grundlage von Lucas-Folgen

Lucas-Folgen

Definition (Lucas-Folgen)

Gegeben sei die Gleichung $X^2-PX+Q=0$ mit $P,Q\in \mathbb{Z}$ und $P≠0,Q≠0$, die Lösungen seien die reellen Zahlen $a$ und $b,a≠b$. $U_n$ und $V_n$ werden durch

$U_n=\frac{a^n+b^n}{a-b},n\ge 0$

$V_n=\frac{a^n+b^n}{a+b},n\ge 0$

definiert und Lucas-Folgen genannt.

Bemerkung  

Die Gleichung $X^2-PX+Q=0$ hat Diskriminante $D=P^2-4Q≠0$ und damit die Lösungen

$a=\frac{P+\sqrt{D}}{2}\text{ und }b=\frac{P+\sqrt{D}}{2}.$

Man beachte, dass $D\equiv 0(mod4)oderD\equiv 1(mod4).$

Bemerkung (Eigenschaften der Folgeglieder)  

Die Folgenglieder für $n=0\text{und}n=1$ kann man leicht ablesen:

$U_0=0,U_1=1$

$V_0=2,V_1=a+b=P$

Die Lucas-Folgen erfüllen die Rekursion

$U_{n+2}=P{U}_{n+1}-Q{U}_n$

bzw.

$V_{n+2}=P{V}_{n+1}-Q{V}_n,\text{wobei}n\ge 0,$

Das heisst, dass jeder Term hängt linear von den zwei vorherigen ab.

Diese Rekursionen kann man durch Nachrechnen überprüfen.

$\begin{array}{cc}P{U}_{n+1}-Q{U}_n& =(a+b)\frac{a^{n+1}-b^{n+1}}{a-b}-ab\frac{a^n-b^n}{a-b}\\ & =\frac{a^{n+2}-a{b}^{n+1}+b{a}^{n+1}-b^{n+2}-a^{n+1}b+a{b}^{n+1}}{a-b}\\ & =\frac{a^{n+2}-b^{n+2}}{a-b}\\ & =U_{n+2}.\end{array}$

Die Richtigkeit der zweiten Rekursion kann analog gezeigt werden.

Die Lucas-Folgen haben noch weitere Eigenschaften. Man geht davon aus, dass $m\ge ̸n$ ist, dann gilt:

$\begin{array}{cc}{U}_{m+n}& =\frac{a^{m+n}-b^{m+n}}{a-b}\\ & =\frac{(a^m-b^m)(a^n+b^n)}{a-b}-\frac{a^n{b}^n(a^{m-n}-b^{m-n})}{a-b}\\ & =U_m{V}_n-Q^n{U}_{m-n};\end{array}$

$\begin{array}{cc}{V}_{m+n}& =a^{m+n}+b^{m+n}\\ & =(a^m+b^m)(a^n+b^n)-a^n{b}^n(a^{m-n}+b^{m-n})\\ & =V_m{V}_n-Q^n{V}_{m-n}.\end{array}$

Daraus für $m=n$ folgt:

$U_{2n}=U_n{V}_n-Q^n{U}_0=U_n{V}_n$

$V_{2n}=V_n{U}_n-Q^n{V}_0={V_n}^2-2Q^n$

und für $m=n+1$:

$U_{2n+1}=U_{n+1}{V}_n-Q^n{U}_1=U_{n+1}{V}_n-Q^n$

$V_{2n+1}=V_{n+1}{V}_n-Q^n{V}_1=V_{n+1}{V}_n-Q^{n}P.$

Damit wurde gezeigt, dass alle Folgeglieder aus $\mathbb{Z}$ sind.

Teilbarkeitseigenschaften der Folgeglieder $U_n$

Definition (Quadratischer Zahlenkörper)

Für ein quadratfreies $D$ heisst die Menge

$Q(\sqrt{D})=a+b\sqrt{D}\text{mit}a,b\in \mathbb{Q}-$ quadratischer Zahlenkörper.

Für ein $a=a_1+a_2\sqrt{D}$ ist dann $\bar{a}=a_1-a_2\sqrt{D}$.

Sei $P^2-4Q=c^{2}D$ mit $c,D\in \mathbb{N}$ und $D$ quadratfrei. Ist $D>1$, so sind die Lösungen $a,b$ der Gleichung $X^2-PX+Q=0$ irrationale Zahlen aus dem quadratischen Zahlenkörper $Q(\sqrt{D})$.

Jeztz kann man ein Pendant zum Kleinen Fermatschen Satz in $Q\sqrt{D}$ formulieren.

Satz

Wenn $a\in A_D$ und $p$ eine ungerade Primzahl, dann

$a^p\equiv a(modp),\text{falls}\left(\frac{D}{p}\right)=+1$

oder

$a^p\equiv \bar{a}(modp),\text{falls}\left(\frac{D}{p}\right)=-1.$

Beweis

Benutzer:Tanik/Lucas-Test/Fakt/Beweis

$◻$

Falls $a(modp)$ in $A_d$ eine Einheit ist, dann folgt aus dem Satz, dass

$a^{p-1}\equiv 1(modp),\text{falls}\left(\frac{D}{p}\right)=1$

oder

$a^{p+1}\equiv a\bar{a}(modp),\text{falls}\left(\frac{D}{p}\right)=-1.$

Lemma

Die Bedingung $ggT(a,p)=1$ in $A_D$, ist identisch mit der Bedingung $ggT(Q,p)=1$ in $N$.

Beweis

Benutzer:Tanik/Lucas-Test/ggt-Lemma/Fakt/Beweis

$◻$

Aus Identitäten ergeben sich für $U_{p-1}$ und $U_{p+1}$ folgende Berechnungen(beachte $b=\bar{a}$:

$U_{p-1}=\frac{a^{p-1}-{\bar{a}}^{p-1}}{a-\bar{a}}\equiv a\bar{a}-\bar{a}a\equiv 0(modp),\text{falls}\left(\frac{D}{p}\right)=1,$

$U_{p+1}=\frac{a^{p+1}-{\bar{a}}^{p+1}}{a-\bar{a}}\equiv \frac{1-1}{a-\bar{a}a}\equiv 0(modp),\text{falls}\left(\frac{D}{p}\right)=-1.$

Bemerkung  

1. $a-\bar{a}$ soll wegen Division nicht $0$ sein
2. $(a-\bar{a}{)}^2=c^{2}D$ daraus folgt, dass $ggt(c,p)=1$ sein muss
3. Zusammen mit $ggT(Q,p)=1$ muss die Bedingung $ggT(cQ,p)=1$ erfüllt sein.

Verhalten Potenzen von $a$ bzw. $U_n$ bezüglich der Teilbarkeit durch $p^n$

Falls $\left(\frac{D}{p}\right)=1$ ist $a^p=a+kp$ für ein bestimmtes $k\in \mathbb{N}$ und deshalb gilt

$a^{p^n}=(a^p{)}^{p^{n-1}}=(a+kp{)}^{p^{n-1}}\equiv a^{p^{n-1}}(mod{p}^n),$

weil alle Terme abseits des ersten $a^{p^{n-1}}$ stets den Faktor $p^n$ enthalten.

Man kann unter der Bedingung, dass $a(modp)$ in $A_D$ eine Einheit ist, durch Division durch $a^{p^{n-1}}$ 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

$a^{p^n}\equiv {\bar{a}}^{p^{n-1}}\Rightarrow a^{p^n}{a}^{p^{n-1}}\equiv (\bar{a}a{)}^{p^{n-1}}\equiv a^{p^{n-1}(p-1)}\equiv (a\bar{a}{)}^{p^{n+1}}(mod{p}^n)$.

Mit diesen Identitäten können die folgenden Folgeglieder $U_i$ berechnet werden:

$U_{p^{n-1}(p-1)}\equiv 0(mod{p}^n)\text{ für }\left(\frac{D}{p}\right)=1$

$U_{p^{n-1}(p+1)}\equiv 0(mod{p}^n)\text{ für }\left(\frac{D}{p}\right)=-1$.

Das lässt sich wie folgt zusammenfassen:

$U_{p^{n-1}(p-\left(\frac{D}{p}\right))}\equiv 0(mod{p}^n)\text{ für }ggT(2QcD,p)=1$.

Die Beschränkung $ggT(2QcD,p)=1$, 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 $ggT(Q,n)=1$. Es existiert ein $d\ge 1$, sodaß die Menge $G=\{t\mid U_t\equiv 0modn\}$ und $G$ hat die Form $G=d\cdot \mathbb{N}$.

Beweis

Benutzer:Abrankov/Lucas-Lehmer-Test/Lemma/Fakt/Beweis

$◻$

Satz (Lucas-Lehmer-Test)

Sei $n+1=\prod _{j=1}^r{q_j}^{{\beta }_j}$ mit $q_j$ paarweise verschiedenen Primzahlen. Sei $U_i$ eine Lucas-Folge mit $\mathrm{ggT}(2QcD,n)=1$ und

$\mathrm{ggT}(U_{\frac{n-1}{q_j}},n)=1\text{ für alle }j=1,2,\mathrm{...},r.$

Ist nun $U_{n+1}\equiv 0modn$,

so ist $n$ prim.

Beweis

Benutzer:Abrankov/Lucas-Lehmer-Test/Beweis

$◻$

Lucas-Lehmer-Test für Mersennezahlen

Im Lucas-Lehmer-Test für Mersennezahlen die Schwierigkeit besteht darin, die Primfaktoren von $n+1$ und

entsprechende Lucas-Folgen zu finden. Die Mersennezahlen $M_m=2^m-1,m⪈1$ haben die Eigenschaft,

dass $n+1$ 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:

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

Wenn eine Lucas-Folge $U_n$ mit

$U_{n+1}\equiv 0(modn)$

bei

$U_{\frac{n+1}{2}}\equiv 0(modn)$

existiert, dann ist $n=M_m=2^m-1$ prim.

Lemma

$U_k$ und $V_k$ haben höchstens $2Q^k$ als gemeisamen Teiler, sprich $ggT(U_k,V_k)$.

Beweis

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

$◻$

Die Bedingungen $U_{n+1}\equiv 0(modn)$ und $U_{\frac{n+1}{2}}\equiv 0(modn)$ können zusammengefasst werden.

Es gilt $U_{n+1}=\frac{U_{n+1}}{2}\frac{V_{n+1}}{2}$, womit $\frac{V_{n+1}}{2}\equiv 0(modn)$ sein muss. Durch allgemeine Bedingung $ggT(2QcD,p)=1$, an Lucas-Folgen für

Primzahltests und Lemma auch klar, dass wenn $\frac{V_{n+1}}{2}$ den Faktor $n$ enthält,

$\frac{V_{n+1}}{2}\equiv ̸0(modn)$ sein muss. Es gegügt demnach $\frac{V_{n+1}}{2}=V_{2^{m-1}}\equiv 0(modn)$ zu überprüfen.

Es sei $V_{2^k}:=v_k$.

Die Berechnung $V_{2^k}=V_{2^{k-1}}^2-2Q^{2^{k-1}}$ dadurch die Form $v_k=v_{k-1}^2-2Q^{2^{k-1}}$.Begonnen wird die Rekursion mit $v_0=V_1=P$ und die Frage bezüglich der Primalität von

$M_m$ lässt sich wie folgt formulieren: wann ist $v_{m-1}\equiv 0(mod{M}_m)$?

Die Werte $a=1+\sqrt{3},b=1-\sqrt{3}$ ergeben eine passende Lucas-Folge, das führt zu

$P=2,Q=-2,P^2-4Q=12,D=3,C=2$.

Dadurch sieht die Rekursion wie folgt aus: $v_k=v_{k-1}^2-22^{2^{k-1}}$ mit dem Startwert $v_1=v_0^2+4=8$.

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

Es sei m ungerade, dann ist $M_m=2^m-1$ genau dann prim, wenn $v_{m-1}\equiv 0(mod{M}_m)$, wobei $v_1=8$ und $v_k=v_{k-1}^2-22^{2^{k-1}}$.

Verbesserter Lucas-Lehmer-Test für Mersennezahlen

Satz (Verbesserter Lucas-Lehmer-Test für Mersennezahlen)

Sei $n=2^p-1$ für eine ungerade Primzahl. Die Folge $v_k$ sei rekursiv definiert durch $v_1=4$ und $v_k=v_{k-1}^2-2$. Dann ist $n$ genau dann prim, falls $n$ die Zahl $v_{p-1}$ teilt.

Beweis

Benutzer:Tanik/Lucas-Lehmer-Test für Mersennezahlen//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 $M_{127}$ nachgewiesen und hat gezeigt, dass $M_{67}$ zerlegbar ist. Schliesslich gelang es Lehmer 1927 zu zeigen, dass $M_{257}$ zerlegbar ist und korrigierte damit Mersennes Aussage.

Der Lucas-Lehemer Primzahltest für Mersenne-Zahlen erfordert eine immense Rechenleistung, wenn$p$ 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 $n=2^5-1=31$ prim ist.

Wir berechnen alle $v_k,k=1,2,3,4$ aus:

$v_1=4$,

$v_2=4^2-2=14$,

$v_3=14^2-2=194\equiv 8(mod31)$,

$v_4=8^2-2=62\equiv 0(mod31)$.

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

Beispiel

Man zeige, dass $n=2^{1}1-1=2047$ nicht prim ist.

Wir berechnen alle $v_k,k=1,\dots ,10$ aus:

$v_1=4,v_2=4^2-2=14$,

$v_3=14^2-2=194\equiv 8,v_4=194^2-2\equiv 788(mod2047)$,

$v_5=788^2-2\equiv 701(mod2047),v_6=701^2-2\equiv 119(mod2047)$,

$v_7=119^2-2\equiv 1877(mod2047),v_8=1877^2-2\equiv 240(mod2047)$,

$v_9=240^2-2\equiv 282(mod2047),v_{1}0=282^2-2\equiv 1736(mod2047)$.

D.h. $n\nmid v_{10}$ und nach verbessertem Lucas-Lehmer-Test für Mersennezahlen folgt, dass die Zahl$2047$ nicht prim ist. Und tatsächlich $2047=23\cdot 89$.

Literatur

• [B] Brenner H.: Kurs: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