Pseudoprimzahlen: Schnellübersicht

Aus Wikibooks

[Bearbeiten] Schnellübersicht

Hier werden die wichtigen Dinge und Fragen kurz abgehandelt.

Was sind Pseudoprimzahlen? Pseudoprimzahlen sind zusammengesetzte Zahlen, die in ihren Eigenschaften denen der Primzahlen ähneln!

Was sind fermatsche Pseudoprimzahlen? fermatsche Pseudoprimzahlen sind zusammengesetzte Zahlen, die in Bezug auf den kleinen fermatschen Satz ( $a^n \equiv a \mod n$ ) für bestimmte Basen $a\$ 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 sonst jede zusammengesetzte natürlich Zahl $n\$ eine fermatsche Pseudoprimzahl sein müßte!

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!

Warum ist jede eulersche Pseudoprimzahl eine fermatsche Pseudoprimzahl?

Warum ist jede starke Pseudoprimzahl eine eulersche Pseudoprimzahl?

Pseudoprimzahlen: Schnellübersicht

Aus Wikibooks

[Bearbeiten] Schnellübersicht

Ansichten

Persönliche Werkzeuge

Navigation

Suche

Mitmachen

Werkzeuge

Drucken/exportieren