Pseudoprimzahlen: Was sind Pseudoprimzahlen

Definition

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

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 $\approx 10^{100}$ auf ihre Primalität zu testen, ihre Teilbarkeit durch $\approx 10^{50}$ Zahlen getestet werden müsste.

Aber 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 funktioniert die Aussage. Allerdings lässt sie sich nicht umkehren: "Wenn $p$ gleich 2 oder eine ungerade Zahl ist, dann ist $p$ eine Primzahl" ist ausgemachter Blödsinn. Es gibt weitere solcher "Wenn $p$ eine Primzahl ist, dann hat $p$ die Eigenschaft $x$", die sinnvoller sind, deren Umkehrung aber ebenfalls falsche Schlüsse wären:

Wenn$p$eine Primzahl und größer als 3 ist,

• dann hat$p$die Form $4n+1$ oder $4n-1$ (das gilt für alle ungeraden Zahlen)
• dann hat$p$die Form $6n+1$ oder $6n-1$ (ungerade und nicht durch 3 teilbar)
• 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

Vermeintliche Primzahlen, die man aus der Umkehrung 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 werden nicht als Pseudoprimzahlen bezeichnet, nur weil sie den Formen $4n+1$, $4n-1$, $6n+1$ bzw. $6n-1$ entsprechen. Dazu sind schon striktere Eigenschaften wie beispielsweise $q$ teilt $a^q-a$ oder $q$ teilt $P_q$ oder $q$ teilt $L_q-1$ nötig.

Zusammengesetze Zahlen, die dem Satz $a^p\equiv a(\mathrm{mod}p)$ (kleiner fermatscher Satz) genügen, nennt man fermatsche Pseudoprimzahlen zur Basis $a$. Dies ist die bekannteste und wichtigste Klasse der Pseudoprimzahlen.

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

Der Umkehrschluss

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

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 $a$, dann ist klar, dass man sich genau auf diese Basis $a$bezieht (abgesehen davon, dass diese fermatsche Pseudoprimzahl noch zu anderen Basen pseudoprim ist).

Absolute Pseudoprimzahlen

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 $n$ ist, oder bei Lucas-Pseudoprimzahlen die Diskriminante $D=P^2-4Q$ den gleichen Wert hat.

Starke Pseudoprimzahlen

Starke Pseudoprimzahlen bezüglich einer Kongruenzbedingung sind zusammengesetzte Zahlen, die eine verschärfte Form derselben Kongruenzbedingung mit denselben Parametern erfüllen, z. B. statt $a^{n-1}\equiv 1(\mathrm{mod}n)$:

• $a^d\equiv 1(\mathrm{mod}n)$ oder
• $a^{d\cdot 2^r}\equiv -1(\mathrm{mod}n)$ für ein $0<=r<s$, jeweils mit $n-1=d\cdot 2^s$.

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