Starke Pseudoprimzahl

Eine ungerade natürliche Zahl ${\displaystyle n}$ wird starke Pseudoprimzahl genannt, wenn sie eine zusammengesetzte Zahl ist, die sich in Bezug auf eine zu ihr teilerfremden Basis ${\displaystyle a}$ wie eine Primzahl verhält:
es sei ${\displaystyle n=d\cdot 2^{s}+1}$ (mit ${\displaystyle d}$ ungerade). Wenn eine der Kongruenzen

• ${\displaystyle a^{d}\equiv 1\mod n}$
• ${\displaystyle a^{d\cdot 2^{r}}\equiv -1\mod n\quad }$für ein ${\displaystyle r}$ mit ${\displaystyle 0\leqq r<s}$

erfüllt ist, dann heißt die Zahl ${\displaystyle n}$ starke Pseudoprimzahl zur Basis ${\displaystyle a}$.

Eine starke Pseudoprimzahl ist immer auch eine Pseudoprimzahl in Bezug auf eine (unten erläuterte) Folgerung aus dem kleinen Fermatschen Satz.

Herleitung

Nach dem kleinen Fermatschen Satz gilt für jede Primzahl ${\displaystyle p}$ und für jedes dazu teilerfremde ${\displaystyle a}$:

${\displaystyle p\mid a^{p-1}-1}$

(in Worten: ${\displaystyle p}$ teilt die ${\displaystyle (p-1)}$-ste Potenz von ${\displaystyle a}$ vermindert um 1). Zusammengesetzte Zahlen, die bezüglich einer teilerfremden Basis ${\displaystyle a}$ auch diese Eigenschaft haben, heißen fermatsche Pseudoprimzahlen zur Basis ${\displaystyle a}$. Aufgrund

${\displaystyle a^{p-1}-1=(a^{\frac {p-1}{2}}+1)\cdot (a^{\frac {p-1}{2}}-1)}$

gilt für jede (ungerade) Primzahl ${\displaystyle p}$, dass einer der beiden rechts stehenden Faktoren durch ${\displaystyle p}$ teilbar sein muss (ist ein Produkt durch eine Primzahl teilbar, so muss einer der Faktoren durch sie teilbar sein). Dies liefert eine schärfere Bedingung und führt zum Begriff der eulerschen Pseudoprimzahlen. Der zweite Faktor lässt sich weiter aufspalten, falls ${\displaystyle {\tfrac {p-1}{2}}}$ eine gerade Zahl ist. In diesem Fall bekommt man:

${\displaystyle a^{p-1}-1=(a^{\frac {p-1}{2}}+1)\cdot (a^{\frac {p-1}{4}}+1)\cdot (a^{\frac {p-1}{4}}-1)}$

Gilt nun ${\displaystyle n=d\cdot 2^{s}+1}$ (mit ${\displaystyle d}$ ungerade), so lässt sich das Verfahren insgesamt ${\displaystyle s}$-mal wiederholen und man erhält die Aussage, dass ${\displaystyle p}$ einen der ${\displaystyle s+1}$ Faktoren teilen muss. In Kongruenzschreibweise ist dies die Bedingung, die am Anfang des Artikels genannt ist (man nennt sie auch starke Fermat-Kongruenz).^[1] Eine starke Pseudoprimzahl ist also eine Pseudoprimzahl in Bezug auf die starke Fermat-Kongruenz.

Beispiele

Für die Carmichael-Zahl 561 (eine fermatsche Pseudoprimzahl bezüglich aller teilerfremden Basen) gilt:

${\displaystyle 560=2^{4}\cdot 35}$

und man findet die Zerlegung

${\displaystyle a^{560}-1=(a^{280}+1)\cdot (a^{140}+1)\cdot (a^{70}+1)\cdot (a^{35}+1)\cdot (a^{35}-1)}$

Als Basis wählen wir 2. Wenn 561 eine Primzahl wäre, dann müsste sie einen der Faktoren auf der rechten Seite teilen. Da die Reste von ${\displaystyle 2^{k}}$ modulo 561 für ${\displaystyle k=35,70,140,280}$ gleich 263, 166, 67 und 1 sind, teilt 561 keinen der Faktoren und somit ist die Zahl nicht prim.

Dies ist das Vorgehen des Miller-Selfridge-Rabin-Primzahltests. Da jede Zahl ${\displaystyle n}$ höchstens für ein Viertel der Basen kleiner als ${\displaystyle n}$ stark pseudoprim ist, gibt es keine absoluten starken Pseudoprimzahlen (im Gegensatz dazu gibt es diese bei den eulerschen und fermatschen Pseudoprimzahlen – letztere sind die erwähnten Carmichael-Zahlen).

Es gibt zu jeder Basis unendlich viele starke Pseudoprimzahlen. Für die ersten Basen kann man in der folgenden Tabelle die kleinsten starken Pseudoprimzahlen (die zumindest kleiner gleich 10000 sind) ablesen:

Die kleinste Zahl, die in allen drei Folgen zur Basis 2, 3 und 5 vorkommt, ist 25.326.001 = 2251 · 11251. Für einen Primzahltest für kleinere Zahlen genügt deshalb die Prüfung zu den Basen 2, 3 und 5.^[2]

Die kleinste Zahl, die in allen neun Folgen zur Basis 2, 3, 5, 7, 11, 13, 17, 19 und 23 vorkommt, ist 3.825.123.056.546.413.051 = 149491 · 747451 · 34233211.^[3]

Literatur

• Peter Giblin: Primes and programming. An introduction to number theory with computing. Cambridge University Press, Cambridge u. a. 1993, ISBN 0-521-40182-8, online und die in Pseudoprimzahl angegebene Literatur.

Weblinks

• Eric W. Weisstein: StrongPseudoprime. In: MathWorld (englisch).

Einzelnachweise

1. ↑ Siehe Artikel Computational Number Theory von Carl Pomerance im ‚Princeton companion to mathematics‘ (vollständig zitiert im Artikel Pseudoprimzahl).
2. ↑ Siehe Giblin, S. 109.
3. ↑ Jiang Yupeng: Strong pseudoprimes to the first 9 prime bases. Cornell University Library, 30. Juni 2012, abgerufen am 13. August 2016.