Pseudoprimzahlen: Was Pseudoprimzahlen sind

Aus Wikibooks
Zur Navigation springen Zur Suche springen
Nuvola apps bookcase 1.svg Pseudoprimzahlen

Was sind Pseudoprimzahlen[Bearbeiten]

Schon seit der Antike (Euklid von Alexandria, ca. 3. Jahrhundert v.u.Z) beschäftigten sich Menschen mit Primzahlen.

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

Allerdings lassen sich damit größere Zahlen schlecht darauf prüfen, ob sie Primzzahlen 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 von Zahlen getestet werden müßte.

Aber die 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 funkioniert die Definition. Allerdings läßt sie sich nicht umdrehen: "Wenn gleich 2 oder eine ungerade Zahl ist, dann ist eine Primzahl" ist ein ausgemachter Blödsinn. Es gibt weitere solcher "Wenn eine Primzahl ist, dann hat die Eigenschaft ", die sinnvoller sind, deren Umdrehung aber ebenfalls falsche Schlüsse wären:

Wenn eine Primzahl ist,
  • dann hat die Form beziehungsweise
  • dann hat die Form beziehungsweise
  • 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

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

Zusammengesetze Zahlen, die den Formen , , bzw. entsprechen, werden deswegen noch lange nicht zwangsläufig als Pseudoprimzahlen bezeichnet. Dazu sind schon striktere Eigenschaften wie Beispielsweise teilt oder teilt oder teilt nötig.

Solche Pseudoprimzahlen, die dem Satz (kleine fermatsche Satz) genügen nennt man fermatsche Pseudoprimzahlen zur Basis . Dies ist die bekannte und wichtigste Klasse der Pseudoprimzahlen.

Der umgekehrte Weg[Bearbeiten]

Für eine Primzahl trifft, daß zu jeder natürlichen Zahl der Satz gilt. Das gleiche gilt auch für Carmichael-Zahlen. In sofern gleichen sich Primzahlen und Carmichael-Zahlen. Aber wenn man nicht den Satz verwendet, sondern statt dessen , dann gibt es einen Unterschied. Für die Primzahlen gilt nur für die teilerfremd zu sind. Auch das gilt für Carmichael-Zahlen. Allerdings sind Carmichael-Zahlen, im Gegensatz zu Primzahlen, zusammengesetzt. Das bedeutet, dass bei Carmichael-Zahlen, im Gegensatz zu Primzahlen, der Bereich, zwischen und , an teilerfremden Zahlen lückenhaft ist.

Es gibt jede Menge Pseudoprimzahlen, die noch lückenhafter sind, als die Carmichael-Zahlen. Die Basis stellt die fermatsche Pseudoprimzahl dar. Jede eulersche Pseudoprimzahl, jede starke Pseudoprimzahl und auch jede Carmichael-Zahl ist eine fermatsche Pseudoprimzahl. Wie findet man alle fermatschen Pseudoprimzahlen in einem vorgegebenen Bereich zwischen und ? Alle fermatschen Pseudoprimzahlen haben gemeinsam, daß es natürliche Zahlen gibt, für die gilt, und gleichzeitig natürliche Zahlen gibt, für die nicht gilt. Kann man den Bereich der natürliche Zahlen einschränken? Es macht Sinn, den Bereich der natürliche Zahlen auf bis einzuschränken, und zwar deswegen, weil sich daß Muster der Basen wiederholt. Als Beispiel die fermatsche Pseudoprimzahl :

ist pseudoprim zu den Basen und . Aus der Regel: Wenn pseudoprim zu ist, dann ist auch pseudoprim zu allen , also der Summe von mit dem vielfachen von . Für sind das die Basen .

Es macht sogar Sinn, den Bereich noch weiter einzuschränken. Für jede natürliche Zahl gilt nämlich folgendes:

1 2 3 4 5 6
1: 1 1 1 1 1 1
X: X X X X X X
X: X X X X X X
X: X X X X X X
X: X X X X X X
A: A 1 A 1 A 1

Wie man sehen kann, trifft auf jede natürliche Zahl folgende zwei Sätze zu:

und

Da diese beiden Sätze auf jede natürliche Zahl zutreffen, haben sie keine Aussagekraft, ob eine Zahl eine Primzahl oder eine Pseudoprimzahl ist. Demzufolge braucht man nur im Bereich zwischen und zu testen. Diese Einschränkung hat zur Folge, dass eine Reihe von Zahlen () als Kandidaten für fermatsche Pseudoprimzahlen herausfallen.

Diese Einschränkung des Bereiches von und zählt zwangsläufig auch für die eulerschen Pseudoprimzahlen, die starken Pseudoprimzahlen und alle anderen Arten von Pseudoprimzahlen, die auf der fermatschen Pseudoprimzahl basieren. Allerdings kann man diese Einschränkung bei den Carmichael-Zahlen ignorieren.