Quelltext der Seite Lucas-Test (Mathematik)

{{Dieser Artikel|erläutert den Primzahltest für natürliche Zahlen ''n'', für die die Faktorisierung von ''n−1'' bekannt ist. Zum Primzahltest für Mersenne-Zahlen siehe [[Lucas-Lehmer-Test]].}}
Der '''Lucas-Test''' ist eine Weiterentwicklung des [[Fermatscher Primzahltest|Fermatschen Primzahltests]] durch den Mathematiker [[Édouard Lucas]]. Der Test wurde in den 1950er Jahren von [[Derrick Henry Lehmer]] und später nochmals von [[John Brillhart]] und [[John L. Selfridge]] verbessert. Er sollte nicht mit dem [[Lucas-Lehmer-Test]] für [[Mersenne-Primzahl|Mersenne-Zahlen]] verwechselt werden.

== Fermatscher Primzahltest ==
Gegeben sei eine [[natürliche Zahl]] <math>n > 1</math>, für die man prüfen möchte, ob sie prim ist. Nach dem [[Fermatscher Primzahltest|fermatschen Primzahltest]] ist <math>n</math> keine Primzahl, wenn folgende Bedingung für eine zu <math>n</math> [[Teilerfremdheit|teilerfremde]] Zahl <math>a</math> mit <math>1<a<n</math> zutrifft:
:<math>a^{n-1} \not\equiv 1 \pmod n</math>

Der Fermat-Test liefert also niemals die Aussage, dass eine Zahl prim ist, sondern kann nur das Prim-Sein ausschließen. Für die [[Carmichael-Zahl]]en liefert der Fermat-Test keine Aussage.

== Lucas-Test ==
Im Jahr 1876 gelang Édouard Lucas folgende Umkehrung des [[Kleiner fermatscher Satz|kleinen fermatschen Satzes]]:

'''(Vorläufer des Lucas-Tests)''' Eine natürliche Zahl <math>n</math> ist genau dann eine Primzahl, wenn es ein <math>a</math> mit <math>1<a<n</math> gibt, für das
:<math>a^{n-1} \equiv 1 \pmod n</math>
sowie
:<math>a^m \not\equiv 1 \pmod n</math>
für alle natürlichen Zahlen <math>m<n-1</math> gilt.

Dieses Ergebnis lässt sich nur schwer anwenden, da so viele <math>m</math> geprüft werden müssen.
Im Jahr 1891 verbesserte Lucas den Satz und erhielt den nach ihm benannten Primzahltest:

'''(Lucas-Test)''' Eine natürliche Zahl <math>n</math> ist genau dann eine Primzahl, wenn es ein <math>a</math> mit <math>1<a<n</math> gibt, für das
:<math>a^{n-1} \equiv 1 \pmod n</math>
sowie
:<math>a^m \not\equiv 1 \pmod n</math>
für alle echten [[Teilbarkeit|Teiler]] <math>m<n-1</math> von <math>n-1</math> gilt.<ref>Beweise hierzu: siehe Ribenboim, ''Die Welt der Primzahlen'', Seite 40.</ref>

Da hier nur noch die ''Teiler'' von <math>n-1</math> getestet werden müssen, sind erheblich weniger Rechenschritte nötig. Ein Nachteil ist jedoch, dass man die [[Primfaktorzerlegung]] von <math>n-1</math> kennen muss. <math>n-1</math> muss also [[Faktorisierungsproblem|faktorisiert]] werden. Für Zahlen mit einem besonderen Aufbau ist diese Methode aber sehr effizient, so zum Beispiel bei Zahlen der Form <math>2^k+1</math>.

Ist die Bedingung des Lucas-Tests für eine Basis <math>a</math> nicht erfüllt, so folgt nicht, dass die Zahl <math>n</math> zusammengesetzt ist. Dafür müsste man nämlich alle Basen <math>1<a<n</math> prüfen.

'''Beispiel:'''

Für die Zahl <math>n=59</math> gilt <math>2^{58}\equiv 1 \bmod 59</math>. Die echten Teiler von <math>n - 1 = 58</math> sind <math>1, 2</math> und <math>29</math>.
Weiter gilt <math>2^1 \equiv 2 \bmod 59, 2^2\equiv 4 \bmod 59</math> und <math>2^{29}\equiv -1 \bmod 59</math>. Es folgt, dass <math>59</math> eine Primzahl ist.

== Erweiterungen von Lehmer, Brillhart und Selfridge ==
[[Derrick Henry Lehmer]] fand 1953 den ''verbesserten Lucas-Test''. Im Jahr 1967 wurde eine weitere Version (''flexibler Lucas-Test'') von [[John Brillhart]] und [[John L. Selfridge]] entdeckt.

=== Verbesserter Lucas-Test ===
Der ''verbesserte Lucas-Test'' beruht auf folgender Eigenschaft:<br>
<math>n</math> ist genau dann eine Primzahl, wenn es eine natürliche Zahl <math>a</math> mit <math>1<a<n</math> gibt, für die
:<math>a^{n-1}\equiv 1 \pmod n</math>
sowie
:<math>a^{\frac{n-1}{q_i}} \not\equiv 1 \pmod n</math>
für alle Primfaktoren <math>q_i</math> von <math>n-1</math> gilt.

Die Anwendung dieses Tests auf [[Fermat-Zahl]]en wird mit [[Pépin-Test]] bezeichnet.

=== Flexibler Lucas-Test ===
Der ''flexible Lucas-Test'' beruht auf folgender Eigenschaft:<br>
Für die natürliche Zahl <math>n</math> sei die Primfaktorzerlegung von <math>n-1</math> gegeben durch
:<math>n-1=q_1^{e_1} \cdot \ldots \cdot q_r^{e_r}</math>.
Dann gilt: <math>n</math> ist genau dann eine Primzahl, wenn es zu jedem Primfaktor <math>q_i</math> eine natürliche Zahl <math>a_i</math> mit <math>1<a_i<n</math> gibt, für die
:<math>a_i^{n-1} \equiv 1 \pmod n</math>
sowie
:<math>a_i^{\frac{n-1}{q_i}} \not\equiv 1 \pmod n</math>
gilt.<ref>Zum Beweis dieses und des vorigen Satzes siehe Ribenboim, ''Die Welt der Primzahlen'', Seite 42.</ref>

==== Beispiel ====

Wir betrachten die Primzahl <math>n=911</math>. Die Vorgängerzahl <math>n-1=910</math> hat die Primteiler <math>q = 2, 5, 7</math> und <math>13</math>. Die folgende Tabelle zeigt dazu passende <math>a</math> und wie die Bedingungen erfüllt werden:

{| class = "wikitable"
!  q !! a !! a<sup>n-1</sup> ≡ 1 (mod n) !! a<sup>(n-1)/q</sup> ≢ 1 (mod n)
|-
|  2 || 7 || 7<sup>910</sup> ≡ 1 (mod 911) || 7<sup>910/2</sup> ≡ -1 (mod 911)
|-
|  5 || 3 || 3<sup>910</sup> ≡ 1 (mod 911) || 3<sup>910/5</sup> ≡ 482 (mod 911)
|-
|  7 || 2 || 2<sup>910</sup> ≡ 1 (mod 911) || 2<sup>910/7</sup> ≡ 568 (mod 911)
|-
| 13 || 2 || 2<sup>910</sup> ≡ 1 (mod 911) || 2<sup>910/13</sup> ≡ 577 (mod 911)
|}

== Pratt Primzahltest ==
Der Pratt-Test ist ein iterierter Lucas-Test.<ref>{{Internetquelle |autor=Daniela Steidl |url=https://wwwbroy.in.tum.de/lehre/vorlesungen/perlen/SS08/Unterlagen/Pratt.pdf |titel=Primzahlzertifikat von Pratt |werk= |hrsg= |datum=2008-04-17 |abruf=2020-05-07 |sprache=de}}</ref><ref>{{Internetquelle |autor=apl. Prof. Dr. Klaus Reinhardt |url=https://users.informatik.uni-halle.de/~ahyjb/krypto/Pratt/Pratt_Applet_d.html |titel=Pratt Primzahlentest |werk= |hrsg= |datum= |abruf=2020-05-07 |sprache=de,en}}</ref> Für alle Primfaktoren von <math>n-1</math> wird wiederum geprüft, ob diese Primzahlen sind.

=== Fermat-Paar ===
<math>(a,b)</math> ist ein Fermat-Paar, falls <math>(a,b)=(1,2) \lor (a\geq 2 \land a^{n-1} \not\equiv 1 \mod n)</math>

=== Pratt-Sequenz ===
<math>(a_1,b_1) \dots (a_k,b_k)</math> ist eine Pratt-Sequenz, wenn für jedes Fermat-Paar <math>(a,b)</math> aus der Sequenz gilt, dass für jeden Primfaktor <math>p</math> von <math>b</math> ein Fermat-Paar <math>(a', p)</math> in der Prattsequenz enthalten ist und es gilt: <math>a^{\frac{n-1}{p}} \not\equiv 1</math>


Für jede Primzahl gibt es eine Pratt-Sequenz in der Länge der Darstellung der Primzahl, weshalb <math> Prime \in NP </math>.

=== Beispiel ===
Für <math>797</math> ist folgendes eine Mögliche Pratt-Sequenz

<math>(5,797),(1,2),(6,199),(5,3),(3,11)</math>

zu überprüfen ist nun noch, ob <math>a^{b-1}\equiv 1</math> und danach, ob für die Primteiler <math>p</math> von <math> b-1 </math> gilt, <math> a^{\frac{b-1}{2}} \not\equiv </math>


<math>(5,797)</math>

<math>5^{797-1} \mod 797 \equiv 5^{796} \mod 797 \equiv  1</math>

<math>5^{\frac{796}{2}} \mod 797 \equiv 5^{398} \mod 797 \equiv 796 \not\equiv 1</math>

<math>5^{\frac{796}{199}} \mod 797 \equiv 5^{4} \mod 797 \equiv 625 \not\equiv 1</math>


<math>(6,199)</math>

<math>6^{199-1} \mod 199 \equiv 6^{198} \mod 199 \equiv 1</math>

<math>6^{\frac{198}{2}} \mod 199 \equiv 6^{99} \mod 199 \equiv 198 \not\equiv 1</math>

<math>6^{\frac{198}{3}} \mod 199 \equiv 6^{66} \mod 199 \equiv 192 \not\equiv 1</math>

<math>6^{\frac{198}{11}} \mod 199 \equiv 6^{18} \mod 199 \equiv 63 \not\equiv 1</math>


<math>(5,3)</math>

<math>5^{3-1} \mod 3 \equiv 5^{2} \mod 3 \equiv 1</math>

<math>5^{\frac{2}{2}} \mod 3 \equiv 5^{1} \mod 3 \equiv 2 \not\equiv 1</math>


<math>(2,5)</math>

<math>2^{5-1} \mod 5 \equiv 2^{4} \mod 5 \equiv 1</math>

<math>2^{\frac{2}{2}} \mod 5 \equiv 2^{1} \mod 5 \equiv 2 \not\equiv 1</math>

== Literatur ==
* [[Paulo Ribenboim]]: ''Die Welt der Primzahlen. Geheimnisse und Rekorde.'' Springer, Berlin u. a. 2006, ISBN 3-540-34283-4 (''Springer-Lehrbuch'').
* [[John Brillhart]], [[Derrick Henry Lehmer|D. H. Lehmer]], [[John L. Selfridge|J. L. Selfridge]]: ''New Primality Criteria and factorizations of <math>2^n \pm 1</math>.'' In: ''Mathematics of Computation.'' 29, 1975, {{ISSN|0025-5718}}, S. 620–647, [https://www.ams.org/journals/mcom/1975-29-130/S0025-5718-1975-0384673-1/S0025-5718-1975-0384673-1.pdf online (PDF; 2,14 MB)].

== Einzelnachweise ==
<references/>

[[Kategorie:Primzahl]]