Starke Pseudoprimzahl

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Eine ungerade natürliche Zahl wird starke Pseudoprimzahl genannt, wenn sie eine zusammengesetzte Zahl ist, die sich in Bezug auf eine zu ihr teilerfremden Basis wie eine Primzahl verhält: schreibt man (mit ungerade), so muss eine der Kongruenzen

oder

für ein mit erfüllt sein. Die Zahl heißt dann starke Pseudoprimzahl zur Basis .

Eine starke Pseudoprimzahl ist eine Pseudoprimzahl in Bezug auf eine (mehrfach durchgeführte und unten erläuterte) Folgerung aus dem kleinen Fermatschen Satz.

Herleitung[Bearbeiten | Quelltext bearbeiten]

Nach dem kleinen Fermatschen Satz gilt für jede Primzahl und für jedes dazu teilerfremde :

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

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

Gilt nun (mit ungerade), so lässt sich das Verfahren insgesamt -mal wiederholen und man erhält die Aussage, dass einen der 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[Bearbeiten | Quelltext bearbeiten]

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

und man findet die Zerlegung

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 modulo 561 für 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 höchstens für ein Viertel der Basen kleiner als 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.[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[Bearbeiten | Quelltext bearbeiten]

  • 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[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  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.