Pseudoprimzahlen: Eulersche Pseudoprimzahlen

Pseudoprimzahlen

Für jede ungerade Primzahl $p$ gilt mit jeder teilerfremden Basis $a$ die Kongruenz

$a^{\frac {n-1}{2}}\equiv \left({\frac {a}{n}}\right)=\pm 1{\pmod {n}}$.

Dabei bezeichnet $\left({\frac {a}{n}}\right)$ das Jacobi-Symbol.

Eulersche Pseudoprimzahl

Eine zusammengesetzte Zahl n ist eine eulersche Pseudoprimzahl, wenn es mindestens eine natürliche Zahl $a$ im Bereich $1<a<n-1$ als Basis gibt, mit der entweder

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

(1a)

oder

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

(1b)

ist.

Eine solche Zahl nennt man eulersche Pseudoprimzahl zur Basis a, kurz: EPsP(a).

Eulersche Pseudoprimzahlen sind auch Fermatsche Pseudoprimzahlen

Es lässt sich ziemlich einfach, nämlich durch Quadrieren, zeigen, dass jede eulersche Pseudoprimzahl auch eine fermatsche Pseudoprimzahl ist. Es sei n eine eulersche Pseudoprimzahl zur Basis a. Es gilt also:

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

Folglich ist:

$a^{n-1}=\left(a^{\frac {n-1}{2}}\right)^{2}\equiv (\pm 1)^{2}=1{\pmod {n}},$

und deshalb ist n auch eine fermatsche Pseudoprimzahl zur Basis a.

Daraus dass eine eulersche Pseudoprimzahl eine fermatsche Pseudoprimzahl ist, lässt sich nicht der Umkehrschluss ziehen, dass jede fermatsche Pseudoprimzahl auch eine eulersche Pseudoprimzahl ist. Das lässt sich anhand der fermatschen Pseudoprimzahl 15 zeigen:

$11^{7}\equiv 11{\pmod {15}}$.

Die Zahl 15 ist also keine eulersche Pseudoprimzahl zur Basis 11. Aber

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

demzufolge ist 15 eine fermatsche Pseudoprimzahl zur Basis 11.

Euler-Jacobi-Pseudoprimzahl

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

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

(2)

ist.

Euler-Jacobi-Pseudoprimzahlen werden oft auch "Eulersche Pseudoprimzahlen" genannt.

Da der Wert des Jacobi-Symbols mit teilerfremden Parametern nur 1 oder -1 sein kann, ist jede Euler-Jacobi-Pseudoprimzahl auch eine eulersche Pseudoprimzahl;

• für 1 gilt Kongruenz 1a,
• für -1 gilt 1b.

Anzahl der Basen

Wenn die Primteiler$\ p_{i}\$einer zusammengesetzten Zahl $n$ bekannt sind, kann die Anzahl der Basen, zu denen sie Euler-Jacobi-Pseudoprimzahl ist, berechnet werden:

Mit der Faktorisierung

$n=\prod _{i=1}^{k}p_{i}^{\alpha _{i}}{\text{ und }}\ n-1=d\cdot 2^{s}{\text{ mit }}d{\text{ ungerade }}$

ist die Anzahl der Basen $<n$ einschließlich 1 und n-1

$\prod _{i=1}^{k}\gcd \left({\frac {n-1}{2}},\ p_{i}^{'}\right)\cdot {\begin{cases}2&{\text{wenn }}\nu =s\\1/2&{\text{wenn }}\exists \ p_{i}{\text{ mit }}\nu _{2}(p_{i})<s{\text{ und }}\alpha _{i}{\text{ ungerade}}\\1&{\text{sonst }}\end{cases}}$

Dabei ist

• $\ s$ der größte Exponent, mit dem $\ 2^{s}|n-1\$gilt,, so dass $\ n-1=d\cdot 2^{s}\$ist,
• $\ p_{i}^{'}$ der größte ungerade Teiler von $\ p_{i}-1$,
• $\ \nu _{2}(p_{i})$ der größte Exponent, mit dem $\ 2^{\nu _{2}(p_{i})}|p_{i}-1\$gilt, so dass $\ p_{i}-1=2^{\nu _{2}(p_{i})}\cdot p_{i}^{'}\$ist und
• $\ \nu$ das Minimum aller $\nu _{2}(p_{i})$.