Starke Pseudoprimzahl

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

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

erfüllt ist, dann heißt die Zahl $n$ starke Pseudoprimzahl zur Basis $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 $p$ und für jedes dazu teilerfremde $a$:

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

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

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

gilt für jede (ungerade) Primzahl $p$, dass einer der beiden rechts stehenden Faktoren durch $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 ${\tfrac {p-1}{2}}$ eine gerade Zahl ist. In diesem Fall bekommt man:

$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 $n=d\cdot 2^{s}+1$ (mit $d$ ungerade), so lässt sich das Verfahren insgesamt $s$-mal wiederholen und man erhält die Aussage, dass $p$ einen der $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). 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:

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

und man findet die Zerlegung

$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 $2^{k}$ modulo 561 für $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 $n$ höchstens für ein Viertel der Basen kleiner als $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:

b	starke Pseudoprimzahlen zur Basis b	OEIS-Folge
2	2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, 80581, 85489, 88357, 90751, …	(Folge A001262 in OEIS)
3	121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, 44287, 47197, 55969, …	(Folge A020229 in OEIS)
4	341, 1387, 2047, 3277, 4033, 4371, 4681, 5461, 8321, 8911, 10261, …	(Folge A020230 in OEIS)
5	781, 1541, 5461, 5611, 7813, 13021, 14981, 15751, 24211, 25351, 29539, 38081, 40501, 44801, 53971, …	(Folge A020231 in OEIS)
6	217, 481, 1111, 1261, 2701, 3589, 5713, 6533, 11041, …	(Folge A020232 in OEIS)
7	25, 325, 703, 2101, 2353, 4525, 11041, …	(Folge A020233 in OEIS)
8	9, 65, 481, 511, 1417, 2047, 2501, 3277, 3641, 4033, 4097, 4681, 8321, 11041, …	(Folge A020234 in OEIS)
9	91, 121, 671, 703, 1541, 1729, 1891, 2821, 3281, 3367, 3751, 5551, 7381, 8401, 8911, 10585, …	(Folge A020235 in OEIS)
10	9, 91, 1729, 4187, 6533, 8149, 8401, 10001, 11111, …	(Folge A020236 in OEIS)
11	133, 793, 2047, 4577, 5041, 12403, …	(Folge A020237 in OEIS)
…	…	…
100	9, 33, 91, 99, 259, 451, 481, 703, 1729, 2821, 2981, 3367, 4187, 5461, 6533, 6541, 6601, 7107, 7471, 8149, 8401, 8911, 10001, 11111, …	(Folge A020326 in OEIS)

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.

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.

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

V – D

Primzahl­mengen