Lucas-Test (Mathematik)

Lucas-Test (Mathematik)

Der Lucas-Test ist eine Weiterentwicklung des Fermatschen Primzahltests durch den Mathematiker Édouard Lucas. Der Test wurde in den 50er Jahren von Derrick 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.

Inhaltsverzeichnis

Fermatscher Primzahltest

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

a^{n-1} \not\equiv 1 \pmod n

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

Im Jahr 1876 gewann Édouard Lucas folgende Umkehrung des kleinen fermatschen Satzes:

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

a^{n-1} \equiv 1 \pmod n

sowie

a^m \not\equiv 1 \pmod n

für alle natürlichen Zahlen m < n - 1 gilt.

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

a^{n-1} \equiv 1 \pmod n

sowie

a^m \not\equiv 1 \pmod n

für alle echten Teiler m < n - 1 von n - 1 gilt.[1]

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

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

Beispiel:

Für die Zahl n = 59 gilt 258 ≡ 1 mod 59. Die echten Teiler von n - 1 = 58 sind 1, 2 und 29. Weiter gilt 21 ≡ 2 mod 59, 22 ≡ 4 mod 59 und 229 ≡ -1 mod 59. Es folgt, dass 59 eine Primzahl ist.

Erweiterungen von Lehmer, Brillhart und Selfridge

Derrick 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:
n ist genau dann eine Primzahl, wenn es eine natürliche Zahl a mit 1 < a < n gibt, für die

a^{n-1}\equiv 1 \pmod n

sowie

a^{\frac{n-1}{q_i}} \not\equiv 1 \pmod n

für alle Primfaktoren qi von n - 1 gilt.

Die Anwendung dieses Tests auf Fermat-Zahlen wird mit Pépin-Test bezeichnet.

Flexibler Lucas-Test

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

n-1=q_1^{e_1} \cdot \ldots \cdot q_r^{e_r}.

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

a_i^{n-1} \equiv 1 \pmod n

sowie

a_i^{\frac{n-1}{q_i}} \not\equiv 1 \pmod n

gilt.[2]

Beispiel

Wir betrachten die Primzahl n=911. Die Vorgängerzahl n-1=910 hat die Primteiler q = 2, 5, 7 und 13. Die folgende Tabelle zeigt dazu passende a 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)

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.

Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Lucas-Test — bezeichnet: Lucas Test (Mathematik), ein Primzahlentest in der Mathematik Lucas Probe, eine Probe zur Unterscheidung verschiedener Alkohole in der Chemie Diese Seite ist eine Begriffsklärung zur Unterscheidung mehrerer mi …   Deutsch Wikipedia

  • Lucas-Lehmer Test — Eine Mersenne Zahl ist eine Zahl der Form 2n − 1. Im Speziellen bezeichnet man mit Mn = 2n − 1 die n te Mersenne Zahl. Die Primzahlen unter den Mersenne Zahlen werden Mersenne Primzahlen genannt. Die ersten acht Mersenne Primzahlen Mp sind 3, 7,… …   Deutsch Wikipedia

  • Edouard Lucas — François Édouard Anatole Lucas (* 4. April 1842 in Amiens; † 3. Oktober 1891 in Paris) war ein französischer Mathematiker. Édouard Lucas Lucas studierte an der École normale superieure, arbeitete am Pariser Observatorium, war Mathematiklehrer am… …   Deutsch Wikipedia

  • Lucas-Folgen — Unter der Lucas Folge versteht man zwei unterschiedliche Dinge: Einerseits die Folge 2, 1, 3, 4, 7, 11, 18, 29, ... bei der jedes Folgenglied (ab dem dritten) die Summe der beiden vorhergehenden ist. Andererseits die beiden allgemeinen Lucas… …   Deutsch Wikipedia

  • Lucas-Zahlen — Unter der Lucas Folge versteht man zwei unterschiedliche Dinge: Einerseits die Folge 2, 1, 3, 4, 7, 11, 18, 29, ... bei der jedes Folgenglied (ab dem dritten) die Summe der beiden vorhergehenden ist. Andererseits die beiden allgemeinen Lucas… …   Deutsch Wikipedia

  • GIMPS — Eine Mersenne Zahl ist eine Zahl der Form 2n − 1. Im Speziellen bezeichnet man mit Mn = 2n − 1 die n te Mersenne Zahl. Die Primzahlen unter den Mersenne Zahlen werden Mersenne Primzahlen genannt. Die ersten acht Mersenne Primzahlen Mp sind 3, 7,… …   Deutsch Wikipedia

  • Mersenne-Primzahlen — Eine Mersenne Zahl ist eine Zahl der Form 2n − 1. Im Speziellen bezeichnet man mit Mn = 2n − 1 die n te Mersenne Zahl. Die Primzahlen unter den Mersenne Zahlen werden Mersenne Primzahlen genannt. Die ersten acht Mersenne Primzahlen Mp sind 3, 7,… …   Deutsch Wikipedia

  • Mersenne-Zahl — Eine Mersenne Zahl ist eine Zahl der Form 2n − 1. Im Speziellen bezeichnet man mit Mn = 2n − 1 die n te Mersenne Zahl. Die Primzahlen unter den Mersenne Zahlen werden Mersenne Primzahlen genannt. Die ersten acht Mersenne Primzahlen Mp sind 3, 7,… …   Deutsch Wikipedia

  • Mersennesche Zahl — Eine Mersenne Zahl ist eine Zahl der Form 2n − 1. Im Speziellen bezeichnet man mit Mn = 2n − 1 die n te Mersenne Zahl. Die Primzahlen unter den Mersenne Zahlen werden Mersenne Primzahlen genannt. Die ersten acht Mersenne Primzahlen Mp sind 3, 7,… …   Deutsch Wikipedia

  • Mersennsche Primzahl — Eine Mersenne Zahl ist eine Zahl der Form 2n − 1. Im Speziellen bezeichnet man mit Mn = 2n − 1 die n te Mersenne Zahl. Die Primzahlen unter den Mersenne Zahlen werden Mersenne Primzahlen genannt. Die ersten acht Mersenne Primzahlen Mp sind 3, 7,… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”