Pseudoprimzahlen: Was sind Pseudoprimzahlen

Aus Wikibooks

Definition[Bearbeiten]

Eine Pseudoprimzahl ist eine zusammengesetzte natürliche Zahl, die bestimmte Eigenschaften mit Primzahlen gemeinsam hat. Sie wird Pseudoprimzahl bezüglich dieser Eigenschaft genannt. Da es viele solche Eigenschaften gibt, ist der Begriff Pseudoprimzahl ohne Angabe der Eigenschaft nicht sinnvoll.

Hintergrund[Bearbeiten]

Die Beschäftigung mit Pseudoprimzahlen ist aus dem Bedürfnis entstanden, schnelle Primzahltests für große Zahlen zu finden.

Primzahlen sind natürliche Zahlen größer 1, die nur durch 1 und durch sich selbst teilbar sind. So sind sie definiert.

Allerdings lassen sich damit größere Zahlen schlecht darauf prüfen, ob sie Primzahlen sind. Wie unpraktisch diese Eigenschaft für den Primzahlentest ist, lässt sich daran ermessen, dass um eine Zahl der Größenordnung auf ihre Primalität zu testen, ihre Teilbarkeit durch Zahlen getestet werden müsste.

Aber Primzahlen haben noch viele andere Eigenschaften, Eigenschaften der Form: "Wenn eine Primzahl ist, dann hat die Eigenschaft ".

Um aus dem Buch Prime Numbers - A Computational Perspective 1 zu zitieren: "Wenn eine Primzahl ist, dann ist gleich 2, oder ist eine ungerade Zahl". In dieser Richtung funktioniert die Aussage. Allerdings lässt sie sich nicht umkehren: "Wenn gleich 2 oder eine ungerade Zahl ist, dann ist eine Primzahl" ist ausgemachter Blödsinn. Es gibt weitere solcher "Wenn eine Primzahl ist, dann hat die Eigenschaft ", die sinnvoller sind, deren Umkehrung aber ebenfalls falsche Schlüsse wären:

Wenneine Primzahl und größer als 3 ist,
  • dann hatdie Form oder (das gilt für alle ungeraden Zahlen)
  • dann hatdie Form oder (ungerade und nicht durch 3 teilbar)
  • dann teiltjede Zahl der Form mit
  • dann teiltden Ausdruck , wobei das p.te Glied der Lucas-Folge ist.
  • dann teiltdas p.te Glied der Perrin-Folge

Vermeintliche Primzahlen, die man aus der Umkehrung solcher "Wenn eine Primzahl ist, dann hat die Eigenschaft "-Regeln bekommt, nennt man Pseudoprimzahlen. Das allerdings mit einer gewissen Einschränkung:

Zusammengesetze Zahlen werden nicht als Pseudoprimzahlen bezeichnet, nur weil sie den Formen , , bzw. entsprechen. Dazu sind schon striktere Eigenschaften wie beispielsweise teilt oder teilt oder teilt nötig.

Zusammengesetze Zahlen, die dem Satz (kleiner fermatscher Satz) genügen, nennt man fermatsche Pseudoprimzahlen zur Basis . Dies ist die bekannteste und wichtigste Klasse der Pseudoprimzahlen.

Allgemein sind Pseudoprimzahlen zusammengesetze Zahlen, die einen probabilistischen Primzahltest bestehen.

Der Umkehrschluss[Bearbeiten]

Wenn eine natürliche Zahl eine Eigenschaft, die alle Primzahlen haben, nicht hat, kann sie keine Primzahl sein; dieser Schluss ist immer zulässig. Wenn die Zahl eine solche Eigenschaft hat, und die Eigenschaft selten bei zusammengesetzten Zahlen auftritt, kann daraus nur geschlossen werden, dass sie wahrscheinlich eine Primzahl ist.

Unterscheidung[Bearbeiten]

Wenn im Text über eine Zahl gesagt wird, sie sei eine Pseudoprimzahl, dann bedeutet das, dass diese Zahl zusammengesetzt ist, und sich nach irgendeinem Kriterium wie eine Primzahl verhält. Genauso bedeutet ein eine Zahl ist eine starke Pseudoprimzahl, dass eine Basis existiert, zu der sich diese zusammengesetzte Zahl, aufgrund des Kriteriums für starke Pseudoprimzahlen, wie eine Primzahl verhält.

Ist dagegen von einer fpsp(a) die Rede, also einer fermatschen Pseudoprimzahl zu einer bestimmten Basis , dann ist klar, dass man sich genau auf diese Basis bezieht (abgesehen davon, dass diese fermatsche Pseudoprimzahl noch zu anderen Basen pseudoprim ist).

Absolute Pseudoprimzahlen[Bearbeiten]

Absolute Pseudoprimzahlen bezüglich einer Eigenschaft sind zusammengesetze Zahlen, die mit allen Parametern, die bestimmte Bedingungen erfüllen, pseudoprim bezüglich dieser Eigenschaft sind; Bedingungen für Parameter sind zum Beispiel, dass bei Fermatschen Pseudoprimzahlen die Basis teilerfremd zu ist, oder bei Lucas-Pseudoprimzahlen die Diskriminante den gleichen Wert hat.

Starke Pseudoprimzahlen[Bearbeiten]

Starke Pseudoprimzahlen bezüglich einer Kongruenzbedingung sind zusammengesetzte Zahlen, die eine verschärfte Form derselben Kongruenzbedingung mit denselben Parametern erfüllen, z. B. statt :

  • oder
  • für ein , jeweils mit .

Aus der Erfüllung der starken Kongruenzbedingung folgt die Erfüllung der ursprünglichen. Der Parameter bleibt dabei gleich.