Pseudoprimzahlen: Qualitative Unterschiede

Aus Wikibooks
Zur Navigation springen Zur Suche springen

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 Primzahlen mit hundert und mehr Stellen würde eine Menscheleben nicht ausreichen, wenn man diese Primzahl nach diesen Verfahren auf Primalität Testen würde. Der andere Teil der Verfahren kann relativ schnell ein Ergebnis ausgeben, ob eine Zahl eine Primzahl ist, oder nicht. Dafür sind die Verfahren aber für Pseudoprimzahlen anfällig. Dabei sind sind die Primzahlen aber nicht von gleicher Qualität. Einige Pseudoprimzahlen lassen sich leicht ausschliessen, dafür sind andere Pseudoprimzahlen richtig hartnäckig.

Pseudoprimzahlen ,

  • die zu allen Basen , zu denen sie eine fermatsche Pseudoprimzahl ist, auch eine eulersche Pseudoprimzahl ist.
  • die zu allen Basen , zu denen sie teilerfremd ist, eine fermatsche Pseudoprimzahl ist (Carmichael-Zahlen).
  • die zu allen Basen , zu denen sie teilerfremd ist, sowohl eine fermatsche Pseudoprimzahl, als auch eulersche Pseudoprimzahl ist (absolute eulersche Pseudoprimzahl).