Pseudoprimzahlen: Schnellübersicht

Schnellübersicht

Hier werden die wichtigen Dinge und Fragen kurz abgehandelt.

Was sind Pseudoprimzahlen?

• Pseudoprimzahlen sind zusammengesetzte Zahlen (d.h. Nichtprimzahlen), die Eigenschaften haben, die normalerweise nur Primzahlen haben.

Fermatsche Pseudoprimzahlen

Was sind fermatsche Pseudoprimzahlen?

• Fermatsche Pseudoprimzahlen sind zusammengesetzte Zahlen, die in Bezug auf den kleinen fermatschen Satz $(a^n\equiv a(\mathrm{mod}n))$ für bestimmte Basen $a$ Primzahlen gleichen!

Warum reicht es, eine zusammengesetzte Zahl $n$ auf $2\le a\le n-2$ zu testen, statt auf $2\le a\le n-1$?

• Weil $a^n\equiv (n-1)(\mathrm{mod}n)$ für jede ungerade natürliche Zahl $n$ gilt, wenn $a=n-1$ ist.

Welche zusammengesetzten, ungeraden Zahlen sind keine fermatschen Pseudoprimzahlen?

• Keine der Dreierpotenzen $3^m$ mit $m\ge 2$ ist eine fermatsche Pseudoprimzahl!

Warum ist es nicht unbedingt notwendig, zusammengesetzte Zahlen $n$ auf Basen $a>n$ zu testen?

• Alle Basen $a>n$ lassen sich als $a=b+m\cdot n$ mit $2\le b\le n-2$ darstellen. Mit anderen Worten: Wenn es keine Basis $a$ mit $2\le a\le n-2$ gibt, zu der $n$ pseudoprim ist, so gibt es gar keine Basis $a$, zu der $n$ pseudoprim ist!