Pseudoprimzahlen: Qualitative Unterschiede

Pseudoprimzahlen

Eine Primzahl hat viele Eigenschaften, an denen man sie als Primzahl erkennen kann. Dementsprechend gibt es viele Verfahren, um eine Zahl auf ihre Primalität zu prüfen. Ein Teil dieser Verfahren ist 100-prozentig sicher, dafür aber auch unheimlich zeitaufwendig. Für Zahlen mit hundert und mehr Stellen würde ein Menschenleben nicht ausreichen, sie nach diesen Verfahren auf Primalität zu testen. Der andere Teil der Verfahren kann relativ schnell ein Ergebnis ausgeben, ob eine Zahl wahrscheinlich eine Primzahl ist, oder sicher keine. Dafür sind solche Verfahren aber für Pseudoprimzahlen anfällig. Dabei sind die Pseudoprimzahlen aber nicht von gleicher Qualität. Einige Pseudoprimzahlen lassen sich leicht ausschließen, dafür sind andere richtig hartnäckig:

Pseudoprimzahlen $n$,

• die zu allen Basen $a$, zu denen sie fermatsche Pseudoprimzahlen sind, auch eulersche Pseudoprimzahlen sind (Pure eulersche Pseudoprimzahlen).

• die zu allen Basen $a$, zu denen sie teilerfremd sind, fermatsche Pseudoprimzahlen sind (Carmichael-Zahlen).

• die zu allen Basen $a$, zu denen sie teilerfremd sind, auch eulersche Pseudoprimzahlen sind (absolute eulersche Pseudoprimzahlen).