Eulersche Pseudoprimzahl

Eine ungerade natürliche Zahl n wird eulersche Pseudoprimzahl genannt, wenn sie eine zusammengesetzte Zahl ist, die sich in Bezug auf eine zu ihr teilerfremde Basis a wie eine Primzahl verhält: wenn nämlich die Kongruenz

$a^\frac{n-1}{2} \equiv \pm 1 \mod n$

erfüllt ist.

Anders ausgedrückt muss n die Differenz $a^\frac{n-1}{2}-1$ oder die Summe $a^\frac{n-1}{2}+1$ teilen.

Eine Folgerung aus dem kleinen fermatschen Satz

Eine eulersche Pseudoprimzahl ist eine Pseudoprimzahl in Bezug auf eine Folgerung aus dem kleinen Fermatschen Satz:

ist p eine ungerade Primzahl, so teilt sie a^{p − 1} − 1, also auch einen der beiden Faktoren $(a^\frac{p-1}{2}+1)(a^\frac{p-1}{2}-1)$ (dritte Binomische Formel). Beispielsweise ist 7 ein Teiler von 3⁶-1 = 728 = 26·28 und einer der Faktoren ist durch 7 teilbar. Dieses Kriterium lässt sich für Primzahltests verwenden. Wie üblich nennt man die zusammengesetzten Zahlen, die das Kriterium erfüllen, Pseudoprimzahlen (in Bezug auf die betrachtete Eigenschaft).

Jede eulersche Pseudoprimzahl ist eine fermatsche Pseudoprimzahl (man quadriere beide Seiten der Kongruenz). Sie sind nach Leonhard Euler benannt.

Definition

Es gibt zwei Varianten, den Begriff eulersche Pseudoprimzahl zu definieren. Beide Fälle setzen voraus, dass die Basis a teilerfremd zu n ist.

Eulersche Pseudoprimzahl

Eine ungerade zusammengesetzte natürliche Zahl n heißt eulersche Pseudoprimzahl zur Basis a, wenn

$a^{\frac{n-1}{2}} \equiv \pm 1 \mod n$

gilt.^[1]

Euler-Jacobi-Pseudoprimzahl

Eine ungerade zusammengesetzte natürliche Zahl n heißt Euler-Jacobi-Pseudoprimzahl zur Basis a, wenn

$a^{(n-1)/2} \equiv \left(\frac an\right)\mod n$

gilt. Dabei bezeichnet $\left(\frac an\right)$ das Jacobi-Symbol.^[2]
Für prime n wird diese Eigenschaft eulersches Kriterium (für das Legendre-Symbol) genannt; es gilt nämlich für alle Primzahlen p > 2:

$a^{(p-1)/2} \equiv \left(\frac ap\right)\mod p$ .

Vergleich

Offenbar impliziert die zweite Variante die erste (da für teilerfremde a und n das Jacobi-Symbol die Werte +1 und -1 annimmt). Die Beispiele n = 341, a = 2 oder n = 21, a = 8 zeigen, dass die Umkehrung falsch ist. Die zweite Definition ist also echt stärker. Das Vorgehen der zweiten Definition ist die Basis des Solovay-Strassen-Tests.

Eine fermatsche Pseudoprimzahl, die keine eulersche Pseudoprimzahl ist

Die Zahl n = 15 liefert mit der Basis a = 11 ein Beispiel für eine fermatsche Pseudoprimzahl, die keine eulersche Pseudoprimzahl ist:

Es gilt:

$11^{14} \equiv 1 \mod 15$ ,

aber

$11^7 \equiv 11 \mod 15$ ;

Man beachte:

$11^2 = 121 \equiv 1 \mod 15$ .

Absolute eulersche Pseudoprimzahlen

Zahlen, die zu allen teilerfremden Basen eine eulersche Pseudoprimzahl darstellen, nennt man absolute eulersche Pseudoprimzahlen.

Literatur

• Neil Koblitz: A Course in Number Theory and Cryptography. 2nd edition. Springer, New York NY u. a. 1994, ISBN 3-540-96576-9 (Graduate Texts in Mathematics 114).

sowie die in Pseudoprimzahl angegebene Literatur.

Siehe auch

• Starke Pseudoprimzahl
• Super-Eulersche Pseudoprimzahl

Einzelnachweise

1. ↑ Eric W. Weisstein: "Euler Pseudoprime." (MathWorld)
2. ↑ Eric W. Weisstein: "Euler-Jacobi Pseudoprime." (MathWorld)