Pseudoprimzahlen: Schnellübersicht

Pseudoprimzahlen

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{\pmod {n}})$ für bestimmte Basen $a$ Primzahlen gleichen!

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

• Weil $a^{n}\equiv (n-1){\pmod {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\geq 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\leq b\leq n-2$ darstellen. Mit anderen Worten: Wenn es keine Basis $a$ mit $2\leq a\leq n-2$ gibt, zu der $n$ pseudoprim ist, so gibt es gar keine Basis $a$, zu der $n$ pseudoprim ist!