Pseudoprimzahlen: Was Pseudoprimzahlen sind

Aus Wikibooks

Wechseln zu: Navigation, Suche
Nuvola apps bookcase 1.svg Pseudoprimzahlen

[Bearbeiten] Was sind Pseudoprimzahlen

Schon seit langer Zeit beschäftigt sich der Mensch mit Primzahlen. Eine Primzahl, das ist eine natürliche Zahl größer eins, die nur durch eins und sich selber teilbar ist. Mit dieser Eigenschaft läßt sich eine Primzahl allerdings schlecht bestimmen. Wie unpraktisch diese Eigenschaft ist, läßt sich daran ermessen, daß um eine Zahl der Größenordnung n\cdot10^{100} auf ihre Primalität zu testen, ihre Teilbarkeit von ungefähr m\cdot10^{50} Zahlen getestet werden müßte.

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

Um aus dem Buch Prime Numbers - A Computational Perspective 1 zu zitieren: "Wenn p\ eine Primzahl ist, dann ist p\ gleich 2, oder p\ ist eine ungerade Zahl". In dieser Richtung funkioniert die Definition. Allerdings läßt sie sich nicht umdrehen: "Wenn p\ gleich 2 oder eine ungerade Zahl ist, dann ist p\ eine Primzahl" ist ein ausgemachter Blödsinn. Es gibt weitere solcher "Wenn p\ eine Primzahl ist, dann hat p\ die Eigenschaft x\ ", die sinnvoller sind, deren Umdrehung aber ebenfalls falsche Schlüsse wären:

Wenn p\ eine Primzahl ist,
  • dann hat p\ die Form 4n+1\ beziehungsweise 4n-1\
  • dann hat p\ die Form 6n+1\ beziehungsweise 6n-1\
  • dann teilt p\ jede Zahl der Form a^p-a\ mit a\ge 2
  • dann teilt p\ den Ausdruck L_p - 1\ , wobei L_p\ das p.te Glied der Lucas-Folge ist.
  • dann teilt p\ das p.te Glied der Perrin-Folge

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

Zusammengesetze Zahlen, die den Formen 4n+1\ , 4n-1\ , 6n+1\ bzw. 6n-1\ entsprechen, werden deswegen noch lange nicht zwangsläufig als Pseudoprimzahlen bezeichnet. Dazu sind schon striktere Eigenschaften wie Beispielsweise q\ teilt aq − a oder q\ teilt P_q\ oder q\ teilt L_q - 1\ nötig.

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

[Bearbeiten] Der umgekehrte Weg

Für eine Primzahl n trifft, daß zu jeder natürlichen Zahl a\ der Satz a^n \equiv a \mod n gilt. Das gleiche gilt auch für Carmichael-Zahlen. In sofern gleichen sich Primzahlen und Carmichael-Zahlen. Aber wenn man nicht den Satz a^n \equiv a \mod n verwendet, sondern statt dessen a^{n-1} \equiv 1 \mod n, dann gibt es einen Unterschied. Für die Primzahlen gilt a^{n-1} \equiv 1 \mod n nur für a\ die teilerfremd zu n\ sind. Auch das gilt für Carmichael-Zahlen. Allerdings sind Carmichael-Zahlen, im Gegensatz zu Primzahlen, zusammengesetzt. Das bedeutet, das bei Carmichael-Zahlen, im Gegensatz zu Primzahlen, der Bereich, zwischen 1\ und n\ , an teilerfremden Zahlen a\ 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 3\ und n\ ? Alle fermatschen Pseudoprimzahlen haben gemeinsam, daß es natürliche Zahlen a\ gibt, für die a^{n-1} \equiv 1 \mod ngilt, und gleichzeitig natürliche Zahlen a\ gibt, für die a^{n-1} \equiv 1 \mod n nicht gilt. Kann man den Bereich der natürliche Zahlen a\ einschränken? Es macht Sinn, den Bereich der natürliche Zahlen a\ auf 1\ bis n-1\ einzuschränken, und zwar deswegen, weil sich daß Muster der Basen a\ wiederholt. Als Beispiel die fermatsche Pseudoprimzahl 15\ :

15\ ist pseudoprim zu den Basen 4\ und 11\ . Aus der Regel: Wenn n pseudoprim zu a\ ist, dann ist n auch pseudoprim zu allen a+bn\ , also der Summe von a\ mit dem vielfachen von n. Für 15\ sind das die Basen 19, 26, 31, 41, 49, 56, ...\ .

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 n folgende zwei Sätze zu:

  • (bn+1)^{n-1} \equiv 1 \mod n
und
  • (bn-1)^{n-1} \equiv 1 \mod n

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

Diese Einschränkung des Bereiches von 2\ und n-2\ 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.

Von „http://de.wikibooks.org/wiki/Pseudoprimzahlen:_Was_Pseudoprimzahlen_sind“
Persönliche Werkzeuge