Pseudoprimzahl

Pseudoprimzahl

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. Da es viele Möglichkeiten für solche Eigenschaften gibt, ist der Begriff Pseudoprimzahl ohne Angabe der Eigenschaft nicht sinnvoll.
Ein typisches Beispiel einer Pseudoprimzahl ist die Zahl 341 = 11·31. Sie ist eine fermatsche Pseudoprimzahl zur Basis 2, aber nicht zur Basis 3.

Inhaltsverzeichnis

Hintergrund

Pseudoprimzahlen sind aus dem Bedürfnis entstanden, Algorithmen zu finden, die zuverlässig sagen können, ob eine Zahl eine Primzahl ist oder nicht (siehe Fermatscher Primzahltest, Lucas-Test, Solovay-Strassen-Test und Miller-Rabin-Test). Da diese Algorithmen nicht perfekt sind, bekommt man auch Zahlen, die keine Primzahlen sind, sich aber dennoch, auf einen speziellen Algorithmus bezogen, wie Primzahlen verhalten. Um die Algorithmen zur Primzahlsuche zu optimieren, werden auch diese Pseudoprimzahlen genauer untersucht.

Eine bedeutende Klasse von Pseudoprimzahlen leitet sich vom kleinen Fermat-Satz ab. Die entsprechenden Zahlen werden deshalb auch Fermatsche Pseudoprimzahlen genannt.

Arten von Pseudoprimzahlen

Fermatsche Pseudoprimzahlen

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

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

a^{n-1} \equiv 1 \mod n .

Das erste Beispiel wurde 1819 von Sarrus gefunden: Die Zahl 2341 − 1 − 1 ist durch 341 teilbar, obwohl 341 = 11·31 zusammengesetzt ist.

Verwandte der fermatschen Pseudoprimzahlen

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

  • Carmichael-Zahl:
    Eine Carmichael-Zahl ist eine fermatsche Pseudoprimzahl n, für die für jede zu n teilerfremde Basis a mit 1 < a < n gilt:
    a^{n-1} \equiv 1 \mod n
  • Eulersche Pseudoprimzahl:
    Eine ungerade zusammengesetzte natürliche Zahl n wird Eulersche Pseudoprimzahl zur Basis a genannt, wenn a und n teilerfremd zueinander sind und
    a^{\frac{n-1}{2}} \equiv \pm 1 \mod n
    gilt.
    Jede eulersche Pseudoprimzahl zur Basis a ist eine fermatsche Pseudoprimzahl zur gleichen Basis.
  • Starke Pseudoprimzahl:
    Eine ungerade zusammengesetzte natürliche Zahl n = d \cdot 2^s+1 wird starke Pseudoprimzahl zur Basis a genannt, wenn
    a^d \equiv 1 \mod n
    oder
    a^{d \cdot 2^r} \equiv -1 \mod n
    für ein r mit 0 ≤ r < s gilt.
    Jede starke Pseudoprimzahl zur Basis a ist eine eulersche Pseudoprimzahl zur gleichen Basis.

Perrinsche Pseudoprimzahlen

Die rekursiv definierte Perrin-Folge hat die Eigenschaft, dass für jede Primzahl p das p-te Folgenglied Pp durch p teilbar ist. Perrinsche Pseudoprimzahlen sind natürliche Zahlen n, für die das n-te Glied Pn durch n teilbar ist, obwohl n zusammengesetzt ist. Die kleinste Perrinsche Pseudoprimzahl ist 271441=5212.

Weitere 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, sowie 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: The Princeton companion to mathematics (ed. Timothy Gowers), S. 348–362, Princeton University Press, 2008 (online)
  • Paulo Ribenboim: The New Book of Prime Number Records, Springer-Verlag, 1996

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Eulersche Pseudoprimzahl — Eine ungerade natürliche Zahl n wird eulersche Pseudoprimzahl genannt, wenn sie eine zusammengesetzte Zahl ist, die sich in Bezug auf eine zu ihr teilerfremde Basis a wie eine Primzahl verhält: wenn nämlich die Kongruenz erfüllt ist. Anders… …   Deutsch Wikipedia

  • 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 (mit d ungerade), so muss eine der… …   Deutsch Wikipedia

  • Fermatsche Pseudoprimzahl — Eine natürliche Zahl n wird Fermatsche Pseudoprimzahl genannt, wenn sie eine zusammengesetzte Zahl ist, die sich in Bezug auf eine zu n teilerfremde Basis a wie eine Primzahl verhält: wenn nämlich die Kongruenz erfüllt ist. Anders ausgedrückt… …   Deutsch Wikipedia

  • Super-Eulersche Pseudoprimzahl — Eine Super Eulersche Pseudoprimzahl ist eine eulersche Pseudoprimzahl zur Basis a, deren sämtliche Teiler ausschließlich aus der 1, Primzahlen, anderen Eulerschen Pseudoprimzahlen der gleichen Basis a und sich selbst besteht. Äquivalent ist die… …   Deutsch Wikipedia

  • Fermat'scher Primzahltest — Mit dem fermatschen Primzahltest kann man Primzahlen von zusammengesetzten Zahlen unterscheiden. Der Test erhält eine Zahl n und eine Basis a als Eingabe. n muss eine ungerade Zahl > 3 sein. Außerdem muss a die Bedingung 1 < a < n − 1… …   Deutsch Wikipedia

  • Super-Poulet-Zahl — Eine Super Eulersche Pseudoprimzahl ist eine eulersche Pseudoprimzahl zur Basis a, deren sämtliche Teiler ausschließlich aus der 1, Primzahlen, anderen Eulersche Pseudoprimzahlen der gleichen Basis a und sich selbst besteht. Alternativ lässt sich …   Deutsch Wikipedia

  • Besondere Zahlen — sind zum einen Zahlen, die im Sinne der Zahlentheorie eine oder mehrere auffällige Eigenschaften besitzen. Außerdem haben viele Zahlen eine besondere Bedeutung in der Mathematik und/oder in Bezug auf die reale Welt. Diese letzteren Zahlen werden… …   Deutsch Wikipedia

  • Soloway-Strassen-Test — Der Solovay Strassen Test (nach Robert Solovay und Volker Strassen) ist ein probabilistischer Primzahltest. Der Test prüft für eine ungerade Zahl n, ob sie eine Primzahl oder das Produkt mehrerer Faktoren ist. Für den Fall, dass der Test als… …   Deutsch Wikipedia

  • PRIMES — Als Primzahltest bezeichnet man ein mathematisches Verfahren, mit dem ermittelt wird, ob eine gegebene Zahl eine Primzahl ist oder nicht. Inhaltsverzeichnis 1 Praktische Anwendung 2 Bekannte Primzahltest Verfahren 2.1 Probedivision 2.2 Sieb des… …   Deutsch Wikipedia

  • Primzahlentest — Als Primzahltest bezeichnet man ein mathematisches Verfahren, mit dem ermittelt wird, ob eine gegebene Zahl eine Primzahl ist oder nicht. Inhaltsverzeichnis 1 Praktische Anwendung 2 Bekannte Primzahltest Verfahren 2.1 Probedivision 2.2 Sieb des… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”