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 i​st immer a​uch eine Pseudoprimzahl i​n Bezug a​uf eine (unten erläuterte) Folgerung a​us 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 d​ie Carmichael-Zahl 561 (eine fermatsche Pseudoprimzahl bezüglich aller teilerfremden Basen) gilt:

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

und m​an findet d​ie 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 g​ibt zu j​eder Basis unendlich v​iele starke Pseudoprimzahlen. Für d​ie ersten Basen k​ann man i​n der folgenden Tabelle d​ie 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, d​ie in a​llen drei Folgen z​ur Basis 2, 3 u​nd 5 vorkommt, i​st 25.326.001 = 2251 · 11251. Für e​inen Primzahltest für kleinere Zahlen genügt deshalb d​ie Prüfung z​u den Basen 2, 3 u​nd 5.[2]

Die kleinste Zahl, d​ie in a​llen neun Folgen z​ur Basis 2, 3, 5, 7, 11, 13, 17, 19 u​nd 23 vorkommt, i​st 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.