Pépin-Test
# Pépin-Test

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

    $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

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

erfüllt ist.

Da $F_0$ = 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

„$\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

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

Aufgrund des quadratischen Reziprozitätsgesetzes gilt

    $\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.

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

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

gilt, so folgt durch Quadrieren

    $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_3$ = $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.

