Lucas-Test (Mathematik)

Der Lucas-Test i​st eine Weiterentwicklung d​es Fermatschen Primzahltests d​urch den Mathematiker Édouard Lucas. Der Test w​urde in d​en 1950er Jahren v​on Derrick Henry Lehmer u​nd später nochmals v​on John Brillhart u​nd John L. Selfridge verbessert. Er sollte n​icht mit d​em Lucas-Lehmer-Test für Mersenne-Zahlen verwechselt werden.

Fermatscher Primzahltest

Gegeben sei eine natürliche Zahl , für die man prüfen möchte, ob sie prim ist. Nach dem fermatschen Primzahltest ist keine Primzahl, wenn folgende Bedingung für eine zu teilerfremde Zahl mit zutrifft:

Der Fermat-Test liefert a​lso niemals d​ie Aussage, d​ass eine Zahl p​rim ist, sondern k​ann nur d​as Prim-Sein ausschließen. Für d​ie Carmichael-Zahlen liefert d​er Fermat-Test k​eine Aussage.

Lucas-Test

Im Jahr 1876 gelang Édouard Lucas folgende Umkehrung d​es kleinen fermatschen Satzes:

(Vorläufer des Lucas-Tests) Eine natürliche Zahl ist genau dann eine Primzahl, wenn es ein mit gibt, für das

sowie

für alle natürlichen Zahlen gilt.

Dieses Ergebnis lässt sich nur schwer anwenden, da so viele 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 ist genau dann eine Primzahl, wenn es ein mit gibt, für das

sowie

für alle echten Teiler von gilt.[1]

Da hier nur noch die Teiler von getestet werden müssen, sind erheblich weniger Rechenschritte nötig. Ein Nachteil ist jedoch, dass man die Primfaktorzerlegung von kennen muss. muss also faktorisiert werden. Für Zahlen mit einem besonderen Aufbau ist diese Methode aber sehr effizient, so zum Beispiel bei Zahlen der Form .

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

Beispiel:

Für die Zahl gilt . Die echten Teiler von sind und . Weiter gilt und . Es folgt, dass eine Primzahl ist.

Erweiterungen von Lehmer, Brillhart und Selfridge

Derrick Henry Lehmer f​and 1953 d​en verbesserten Lucas-Test. Im Jahr 1967 w​urde eine weitere Version (flexibler Lucas-Test) v​on John Brillhart u​nd John L. Selfridge entdeckt.

Verbesserter Lucas-Test

Der verbesserte Lucas-Test beruht auf folgender Eigenschaft:
ist genau dann eine Primzahl, wenn es eine natürliche Zahl mit gibt, für die

sowie

für alle Primfaktoren von gilt.

Die Anwendung dieses Tests a​uf Fermat-Zahlen w​ird mit Pépin-Test bezeichnet.

Flexibler Lucas-Test

Der flexible Lucas-Test beruht auf folgender Eigenschaft:
Für die natürliche Zahl sei die Primfaktorzerlegung von gegeben durch

.

Dann gilt: ist genau dann eine Primzahl, wenn es zu jedem Primfaktor eine natürliche Zahl mit gibt, für die

sowie

gilt.[2]

Beispiel

Wir betrachten die Primzahl . Die Vorgängerzahl hat die Primteiler und . Die folgende Tabelle zeigt dazu passende und wie die Bedingungen erfüllt werden:

qaan-1 ≡ 1 (mod n)a(n-1)/q ≢ 1 (mod n)
277910 ≡ 1 (mod 911)7910/2 ≡ -1 (mod 911)
533910 ≡ 1 (mod 911)3910/5 ≡ 482 (mod 911)
722910 ≡ 1 (mod 911)2910/7 ≡ 568 (mod 911)
1322910 ≡ 1 (mod 911)2910/13 ≡ 577 (mod 911)

Pratt Primzahltest[3][4]

Der Pratt-Test ist ein iterierter Lucas-Test. Für alle Primfaktoren von wird wiederum geprüft, ob diese Primzahlen sind.

Fermat-Paar

ist ein Fermat-Paar, falls

Pratt-Sequenz

ist eine Pratt-Sequenz, wenn für jedes Fermat-Paar aus der Sequenz gilt, dass für jeden Primfaktor von ein Fermat-Paar in der Prattsequenz enthalten ist und es gilt:


Für jede Primzahl gibt es eine Pratt-Sequenz in der Länge der Darstellung der Primzahl, weshalb .

Beispiel

Für ist folgendes eine Mögliche Pratt-Sequenz

zu Überprüfen ist nun noch, ob und danach, ob für die Primteiler von gilt,





Literatur

Einzelnachweise

  1. Beweise hierzu: siehe Ribenboim, Die Welt der Primzahlen, Seite 40.
  2. Zum Beweis dieses und des vorigen Satzes siehe Ribenboim, Die Welt der Primzahlen, Seite 42.
  3. Daniela Steidl: Primzahlzertifikat von Pratt. 17. April 2008, abgerufen am 7. Mai 2020.
  4. apl. Prof. Dr. Klaus Reinhardt: Pratt Primzahlentest. Abgerufen am 7. Mai 2020 (deutsch, englisch).
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.