Pseudoprimzahl

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Eine Pseudoprimzahl ist eine zusammengesetzte, natürliche Zahl, die gewisse Eigenschaften mit Primzahlen gemeinsam hat, selbst aber keine Primzahl ist. Sie wird Pseudoprimzahl bezüglich dieser Eigenschaft genannt.

Inhaltsverzeichnis

1 Hintergrund
2 Arten von Pseudoprimzahlen
- 2.1 Fermatsche Pseudoprimzahlen
- 2.2 Perrinsche Pseudoprimzahlen
3 Weitere Pseudoprimzahlen
4 Beweise für die Existenz unendlich vieler Pseudoprimzahlen
5 Literatur
6 Weblinks

[Bearbeiten] Hintergrund

Die Pseudoprimzahlen sind aus dem Bedürfnis entstanden, Algorithmen zu finden, die zuverlässig sagen können, ob eine Zahl eine Primzahl ist oder nicht. Da diese Algorithmen nicht perfekt waren, bekam man auch Zahlen, die keine Primzahlen sind, sich aber dennoch, auf diesen speziellen Algorithmus bezogen, wie Primzahlen verhalten. Um die Algorithmen zur Primzahlensuche zu optimieren, wurden auch die Pseudoprimzahlen genauer untersucht.

Die bedeutendste Klasse von Pseudoprimzahlen, um die sich dieser Artikel hauptsächlich dreht, leitet sich vom kleinen Fermat-Satz ab. Die entsprechenden Zahlen werden deshalb auch Fermatsche Pseudoprimzahlen genannt. Eine echte Teilmenge der Fermatschen Pseudoprimzahlen sind die Carmichael-Zahlen.

[Bearbeiten] Arten von Pseudoprimzahlen

[Bearbeiten] Fermatsche Pseudoprimzahlen

Das sind zusammengesetze Zahlen n, für die zu bestimmten Basen a mit $2\le a\le n-2$ und $\operatorname{ggT}(a,n)=1$ gilt, dass $a^{n-1} \equiv 1 \mod n$ ist.

Zu den Fermatschen Pseudoprimzahlen gehören die Eulerschen Pseudoprimzahlen, die Carmichael-Zahlen und die starken Pseudoprimzahlen.

Eulersche Pseudoprimzahl

Eine ungerade zusammengesetzte natürliche Zahl n wird Eulersche Pseudoprimzahl zur Basis a genannt, wenn a und n teilerfremd zueinander sind und

$\left(\frac{a}{n}\right) = a^{\frac{n-1}{2}} \equiv 1 \mod n$ beziehungsweise $\left(\frac{a}{n}\right) = a^{\frac{n-1}{2}} \equiv -1 \mod n$ gilt.

Carmichael-Zahl

Eine Carmichael-Zahl ist eine solche Pseudoprimzahl n, so dass für jede zu n teilerfremde Basis b mit

1 < b < n

gilt: $b^{n-1}-1 \equiv 0 \mod n$ .

[Bearbeiten] Perrinsche Pseudoprimzahlen

Perrinsche Pseudoprimzahlen sind zusammengesetzte Zahlen n, deren Glied P_n durch n teilbar ist, ohne das n eine Primzahl ist.

[Bearbeiten] Weitere Pseudoprimzahlen

Euler-Jacobische Pseudoprimzahlen
- Euler-Jacobi-Pseudoprimzahlen zur Basis 2
- Euler-Jacobi-Pseudoprimzahlen zur Basis 3
Extrastarke Lucassche Pseudoprimzahlen
Fibonaccische Pseudoprimzahlen
Frobeniussche Pseudoprimzahlen
Lucassche Pseudoprimzahlen
Somer-Lucassche Pseudoprimzahlen
Starke Frobeniussche Pseudoprimzahlen
Starke Lucassche Pseudoprimzahlen

[Bearbeiten] Beweise für die Existenz unendlich vieler Pseudoprimzahlen

Beweis von E. Malo 1903
Beweis von Michele Cipolla 1904

[Bearbeiten] Literatur

Carl Pomerance: The Search for Prime Numbers in: Scientific American, December 1982
Carl Pomerance: Primzahlen im Schnelltest in: Spektrum der Wissenschaft, Februar 1983 S. 80-92. (Es handelt sich um die Übersetzung des vorerwähnten Artikels) mit Foto eines Nachbaus von Lehmers Fahrradkettencomputers von 1926!
The New Book of Prime Number Records, Paolo Ribenboim, Springer Verlag 1996, ISBN 0-387-94457-5