Pseudoprimzahlen: Was sind Pseudoprimzahlen

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:

Wenn eine Primzahl und größer als 3 ist,
  • dann hat die Form   oder   (das gilt für alle ungeraden Zahlen)
  • dann hat die Form   oder   (ungerade und nicht durch 3 teilbar)
  • dann teilt jede Zahl der Form   mit  
  • dann teilt den Ausdruck  , wobei  das p.te Glied der Lucas-Folge ist.
  • dann teilt das 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.