Der Lucas-Test ist eine Weiterentwicklung des 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-Zahlen verwechselt werden.

Fermatscher Primzahltest

Bearbeiten

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 also niemals die Aussage, dass eine Zahl prim ist, sondern kann nur das Prim-Sein ausschließen. Für die Carmichael-Zahlen liefert der Fermat-Test keine Aussage.

Lucas-Test

Bearbeiten

Im Jahr 1876 gelang Édouard Lucas folgende Umkehrung des 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

Bearbeiten

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

Bearbeiten

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 auf Fermat-Zahlen wird mit Pépin-Test bezeichnet.

Flexibler Lucas-Test

Bearbeiten

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

Bearbeiten

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

q a an-1 ≡ 1 (mod n) a(n-1)/q ≢ 1 (mod n)
2 7 7910 ≡ 1 (mod 911) 7910/2 ≡ -1 (mod 911)
5 3 3910 ≡ 1 (mod 911) 3910/5 ≡ 482 (mod 911)
7 2 2910 ≡ 1 (mod 911) 2910/7 ≡ 568 (mod 911)
13 2 2910 ≡ 1 (mod 911) 2910/13 ≡ 577 (mod 911)

Pratt Primzahltest

Bearbeiten

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

Fermat-Paar

Bearbeiten

  ist ein Fermat-Paar, falls  

Pratt-Sequenz

Bearbeiten

  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

Bearbeiten

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

Bearbeiten

Einzelnachweise

Bearbeiten
  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).