Pépin-Test

Der Pépin-Test ist ein Primzahltest für Fermat-Zahlen. Er prüft, ob natürliche Zahlen der Form

${\displaystyle F_{k}:=2^{2^{k}}+1}$

prim sind oder nicht. Grundlage für den Pépin-Test sind Arbeiten von Théophile Pépin (1826–1904), François Proth (1852–1879) und Édouard Lucas.

Funktionsweise

Der Test beruht auf folgendem Satz:

F_k ist für k ≥ 1 genau dann eine Primzahl, wenn die Kongruenz

${\displaystyle 3^{(F_{k}-1)/2}\equiv -1\mod F_{k}}$

erfüllt ist.[1]

Da F₀ = 3 ist, gilt der Satz nicht für k = 0. Für k = 1 ist F_k = 5 und es gilt 3^2 = 9 ≡ −1 mod 5. Zur Berechnung für größere k verwendet man den Modulo-Befehl schon in den Zwischenschritten, wie im untenstehenden Beispiel illustriert wird.

Beweis des Satzes

„${\displaystyle \Rightarrow }$“: Ist für ein k ≥ 1 die Fermat-Zahl F_k prim, so gilt nach dem Eulerschen Kriterium für das Legendre-Symbol die Kongruenz

${\displaystyle 3^{(F_{k}-1)/2}\equiv \left({\frac {3}{F_{k}}}\right)\mod F_{k}}$ .

Aufgrund des quadratischen Reziprozitätsgesetzes gilt

${\displaystyle \left({\frac {3}{F_{k}}}\right)=\left({\frac {F_{k}}{3}}\right)=\left({\frac {2}{3}}\right)=-1}$ .

Hierbei werden die Kongruenzen F_k ≡ 1 mod 4 und F_k ≡ 2 mod 3 (mit Induktion zu zeigen) benutzt. Damit ist der Beweis in einer Richtung erbracht.

„${\displaystyle \Leftarrow }$“: Nehmen wir umgekehrt an, dass

${\displaystyle 3^{(F_{k}-1)/2}\equiv -1\mod F_{k}}$

gilt, so folgt durch Quadrieren

${\displaystyle 3^{F_{k}-1}\equiv 1\mod F_{k}}$ .

Nach dem verbesserten Lucas-Test folgt, dass F_k prim ist.

Die Anwendung des verbesserten Lucas-Tests ist in diesem Fall besonders einfach, da F_k – 1 nur einen Primteiler, nämlich die 2, hat.

Beispiel

Als Beispiel zeigen wir mit Hilfe des Pépin-Tests, dass F₃ = 2^8 + 1 = 257 eine Primzahl ist. Wir berechnen 3^128 mod 257 schrittweise und erhalten 3^128 ≡ −1 mod 257:

3^8 = 6561 ≡ –121 mod 257,
→ 3^16 ≡ (–121)^2 ≡ –8 mod 257,
→ 3^32 ≡ (–8)^2 ≡ 64 mod 257,
→ 3^64 ≡ 64^2 ≡ –16 mod 257,
→ 3^128 ≡ (–16)^2 = 256 ≡ –1 mod 257.

Literatur

• Paulo Ribenboim: Die Welt der Primzahlen. Geheimnisse und Rekorde. Springer, Berlin u. a. 2006, ISBN 3-540-34283-4, S. 71–72.
• Théophile Pépin: Sur la formule ${\displaystyle 2^{2^{n}}+1}$. In: Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences. Bd. 85, 1877, ISSN 0001-4036, S. 329–333

Einzelnachweise

1. Historische Anmerkungen sind enthalten in John H. Jaroma: Equivalence of Pepin’s and the Lucas-Lehmer Tests. In: European Journal of Pure & Applied Mathematics. Bd. 2, Nr. 3, 2009, ISSN 1307-5543, S. 352–360. Statt der Basis 3 kann man auch andere Basen verwenden, z. B. 5 und 10.