Pepin-Test

Unter dem Pepin-Test versteht man einen Primzahltest. Der Pepin-Test überprüft Fermatsche Zahlen, das sind natürliche Zahlen der Form

$F_k:=2^{2^k}+1,$

darauf, ob sie eine Primzahl sind oder nicht. Grundlage für den Pepin-Test sind Arbeiten, die auf Édouard Lucas zurückgehen.

Der Pepin-Test lautet: Sei $k\geq 1$.

$F_k=2^{2^k}+1$ ist genau dann eine Primzahl, wenn gilt $3^{(F_k -1)/2} \equiv -1 \ \textrm{mod} \ F_k.$

Zur schnelleren und einfacheren Berechnung verwendet man den modulo-Befehl schon in den Zwischenschritten, dies ändert nichts am Ergebnis. Zum Potenzieren der 3 wird im Allgemeinen das Verfahren des schnellen Potenzierens verwendet.

Als Beispiel soll hier der Beweis dafür, dass F₃ = 2⁸ + 1 = 257 eine Primzahl ist, mithilfe des Pepin-Tests geführt werden. Wir berechnen $3^{128} \ \textrm{mod} \ 257$ schrittweise:

$3^8=6561\equiv -121 \ \textrm{mod} \ 257$

$3^{16}\equiv (-121)^2 \equiv -8 \ \textrm{mod} \ 257$

$3^{32}\equiv (-8)^2 = 64 \ \textrm{mod} \ 257$

$3^{64}\equiv 64^2 \equiv -16 \ \textrm{mod} \ 257$

$3^{128}\equiv (-16)^2 = 256\equiv -1 \ \textrm{mod} \ 257$