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: schreibt man $n = d \cdot 2^s+1$ (mit d ungerade), so muss eine der Kongruenzen

$a^d \equiv 1 \mod n$

oder

$a^{d \cdot 2^r} \equiv -1 \mod n$

für ein r mit 0 ≤ r < s erfüllt sein. Die Zahl n heißt dann starke Pseudoprimzahl zur Basis a.

Eine starke Pseudoprimzahl ist eine Pseudoprimzahl in Bezug auf eine (mehrfach durchgeführte und 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 (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).^[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:

$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 Basen 2, 3 und 5 handelt es sich um die Folgen:

Basis 2

2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, 80581, 85489, 88357, 90751, … (Folge A001262 in OEIS).

Basis 3:

121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, 44287, 47197, 55969, … (Folge A020229 in OEIS).

Basis 5:

781, 1541, 5461, 5611, 7813, 13021, 14981, 15751, 24211, 25351, 29539, 38081, 40501, 44801, 53971, … (Folge A020231 in OEIS).

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

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.