Pseudoprimzahl

Eine Pseudoprimzahl i​st eine zusammengesetzte natürliche Zahl, d​ie gewisse Eigenschaften m​it Primzahlen gemeinsam hat, selbst a​ber keine Primzahl ist. Sie w​ird Pseudoprimzahl bezüglich dieser Eigenschaft genannt. Da e​s viele Möglichkeiten für solche Eigenschaften gibt, i​st der Begriff Pseudoprimzahl o​hne Angabe d​er Eigenschaft n​icht sinnvoll.

Ein historisch bedeutendes Beispiel einer Pseudoprimzahl ist die Zahl ${\displaystyle 341=11\cdot 31}$. Sie ist eine Fermatsche Pseudoprimzahl zur Basis ${\displaystyle 2}$ (und auch einigen anderen Basen).

Hintergrund

Pseudoprimzahlen s​ind aus d​em Bedürfnis entstanden, Algorithmen z​u finden, d​ie zuverlässig s​agen können, o​b eine Zahl e​ine Primzahl i​st oder n​icht (siehe Fermatscher Primzahltest, Lucas-Test, Solovay-Strassen-Test u​nd Miller-Rabin-Test). Da d​iese Algorithmen n​icht perfekt sind, bekommt m​an auch Zahlen, d​ie keine Primzahlen sind, s​ich aber dennoch, a​uf einen speziellen Algorithmus bezogen, w​ie Primzahlen verhalten. Um d​ie Algorithmen z​ur Primzahlsuche z​u optimieren, werden a​uch diese Pseudoprimzahlen genauer untersucht.

Eine bedeutende Klasse v​on Pseudoprimzahlen leitet s​ich vom kleinen Fermat-Satz ab. Die entsprechenden Zahlen werden deshalb a​uch Fermatsche Pseudoprimzahlen genannt.

Arten von Pseudoprimzahlen

Fermatsche Pseudoprimzahlen

→ Hauptartikel: Fermatsche Pseudoprimzahl

Nach dem kleinen Satz von Fermat gilt für jede Primzahl ${\displaystyle p}$ für jede zu ${\displaystyle p}$ teilerfremde Basis ${\displaystyle a}$, dass ${\displaystyle a^{p-1}\equiv 1\mod p}$ ist.

Eine zusammengesetzte natürliche Zahl n wird Fermatsche Pseudoprimzahl zur Basis ${\displaystyle a}$ genannt, wenn ${\displaystyle a}$ und ${\displaystyle n}$ teilerfremd zueinander sind und die gleiche Kongruenz wie bei einer Primzahl erfüllt ist:

${\displaystyle a^{n-1}\equiv 1\mod n}$

Das erste Beispiel wurde 1819 von Sarrus gefunden: Die Zahl ${\displaystyle 2^{341-1}-1}$ ist durch ${\displaystyle 341}$ teilbar, obwohl ${\displaystyle 341=11\cdot 31}$ zusammengesetzt ist.

Verwandte der fermatschen Pseudoprimzahlen

Zu d​en Fermatschen Pseudoprimzahlen gehören d​ie Carmichael-Zahlen, Eulerschen Pseudoprimzahlen u​nd die starken Pseudoprimzahlen.

• Carmichael-Zahl:

  Eine Carmichael-Zahl ist eine fermatsche Pseudoprimzahl ${\displaystyle n}$, für die für jede zu ${\displaystyle n}$ teilerfremde Basis ${\displaystyle a}$ mit ${\displaystyle 1<a<n}$ gilt:

  ${\displaystyle a^{n-1}\equiv 1\mod n}$

• Eulersche Pseudoprimzahl:

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

  ${\displaystyle a^{\frac {n-1}{2}}\equiv \pm 1\mod n}$

  gilt.

  Jede eulersche Pseudoprimzahl zur Basis ${\displaystyle a}$ ist eine fermatsche Pseudoprimzahl zur gleichen Basis.

• Starke Pseudoprimzahl:

  Eine ungerade zusammengesetzte natürliche Zahl ${\displaystyle n=d\cdot 2^{s}+1}$ wird starke Pseudoprimzahl zur Basis ${\displaystyle a}$ genannt, wenn

  ${\displaystyle a^{d}\equiv 1\mod n}$

  oder

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

  für ein ${\displaystyle r}$ mit ${\displaystyle 0\leq r<s}$ gilt.

  Jede starke Pseudoprimzahl zur Basis ${\displaystyle a}$ ist eine eulersche Pseudoprimzahl zur gleichen Basis.

Perrinsche Pseudoprimzahlen

Die rekursiv definierte Perrin-Folge hat die Eigenschaft, dass für jede Primzahl ${\displaystyle p}$ das ${\displaystyle p}$-te Folgenglied ${\displaystyle P_{p}}$ durch ${\displaystyle p}$ teilbar ist. Perrinsche Pseudoprimzahlen sind natürliche Zahlen ${\displaystyle n}$, für die das ${\displaystyle n}$-te Glied P_n durch ${\displaystyle n}$ teilbar ist, obwohl ${\displaystyle n}$ zusammengesetzt ist. Die kleinste Perrinsche Pseudoprimzahl ist ${\displaystyle 271441=521^{2}}$.

Weitere Pseudoprimzahlen

• Euler-Jacobische Pseudoprimzahlen
• Fibonaccische Pseudoprimzahlen, Lucassche Pseudoprimzahlen, Somer-Lucassche Pseudoprimzahlen und starke Lucassche Pseudoprimzahlen
• Frobeniussche Pseudoprimzahlen und starke Frobeniussche Pseudoprimzahlen

Literatur

• Paul Erdős und Carl Pomerance: On the Number of False Witnesses for a Composite Number. Mathematics of Computation 46, 259–279, 1986.
• Carl Pomerance: The Search for Prime Numbers. Scientific American 12/1982.
  Deutsche Übersetzung: Primzahlen im Schnelltest. Spektrum der Wissenschaft 02/1983. Mit Foto eines Nachbaus von Lehmers Fahrradkettencomputer von 1926.
• Carl Pomerance: Computational Number Theory. In: Timothy Gowers (Hrsg.): The Princeton companion to mathematics. S. 348–362, Princeton University Press, 2008 (online; PDF; 249 kB).
• Paulo Ribenboim: The New Book of Prime Number Records. Springer-Verlag, 1996.

Weblinks

• Pseudoprimzahlen. Bei: mathe-schule.de. (PDF; 89 kB).
• Final Answers. Modular Arithmetic. Bei: numericana.com.