Pseudoprimzahlen: Makropseudoprimzahlen

Aus Wikibooks

Wechseln zu: Navigation, Suche
Nuvola apps bookcase 1.svg Pseudoprimzahlen

Inhaltsverzeichnis

[Bearbeiten] Carmichael-Zahlen

Die Carmichael-Zahl ist eine besondere Form der fermatschen Pseudoprimzahl. In ihren Eigenschaften kommt sie der Primzahl am Nächsten. Sowohl für die Primzahl, als auch für die Carmichael-Zahl gilt der kleine Fermatsche Satz: Für jede ganze Zahl a\ gilt n | a^n - a\ . Erst wenn man diesen Satz modifiziert, ergibt sich ein Unterschied zwischen Primzahl und Carmichael-Zahl.

Für eine Carmichael-Zahl gelten folgende Eigenschaften:

  1. Eine Carmichael-Zahl ist quadratfrei.
  2. Eine Carmichael-Zahl besteht aus mindestens drei Primfaktoren.
  3. Für jeden Primfaktor p_i\ einer Carmichael-Zahl c=p_1\cdot p_2\cdot ... \cdot p_n gilt p_i-1\ teilt c-1\ .
  4. Für alle Basen a\ , die zu der Carmichael-Zahl c\ teilerfremd sind, gilt a^{c-1} \equiv 1 \mod c.

[Bearbeiten] Quadratfreiheit

Warum muß eine Carmichael-Zahl quadratfrei sein? Angenommen es gibt eine Carmichael-Zahl, die nicht quadratfrei ist. Sie hat der Einfachhalber die Form c = p_1^n\cdot p_2 mit n \ge 2. Ausserdem sind p_1\ und p_2\ Primzahlen. Es gilt also p_1\ teilt c\ . Mit der Kenntnis der Faktorisierung von c\ kann man die Carmichael-Funktion λ(c) berechnen:

\lambda(c) = \lambda(p_1^n\cdot p_2) = \operatorname{kgV}\{\lambda(p_1^n), \lambda(p_2) \} = \operatorname{kgV}\{(p_1-1)(p_1^{n-1}), p_2-1 \}

Da c-1\ durch \lambda(c)\ teilbar ist, ist c-1\ auch durch (p_1-1)(p_1^{n-1})\ teilbar, und damit gilt dadurch auch daß c-1\ durch p_1\ teilbar ist. Und das führt zu einem Widerspruch.

Es gilt nämlich p_1\ teilt c\ und p_1\ teilt c-1\ . Der Widerspruch liegt darin, das c\ und c-1\ zueinander teilerfremd sind, also keine gemeinsamen Teiler besitzen. Also ist es nicht möglich, das eine Carmichael-Zahl nicht quadratfrei ist.

[Bearbeiten] mindestens drei Primfaktoren

Jede Carmichael-Zahl besitzt mindestens 3 voneinander verschiedene Primfaktoren.

Beweis: Durch Widerspruch.

Sei n\ eine Carmichael-Zahl. Angenommen, n=p\cdot q, wobei p\ und q\ Primfaktoren seien. Zunächst muss wegen der oben gezeigten Quadratfreiheit gelten, dass p \ne q. Wir können also annehmen, dass p<q\ (man kann die Schlüsse analog mit p>q\ ziehen). Nun gilt wegen Eigenschaft (3) q-1 | n-1\ also q-1 | p\cdot q-1.

Damit ist \frac{p\cdot q-1}{q-1}=p+\frac{p-1}{q-1} \in \mathbb{Z}. Das bedeutet aber, (q-1) | (p-1)\ im Widerspruch zu p<q\ . Also war die Annahme falsch. Carmichael-Zahlen mit 1 Primfaktor kann es nach Definition nicht geben (denn sie sind gerade Pseudo-Primzahlen und selbst keine Primzahlen), und dass es Carmichael-Zahlen mit 3 Primfaktoren gibt, zeigt bereits die allererste: 561 = 17\cdot 11\cdot 3. Zusammen genommen ist also gezeigt worden, eine Carmichael-Zahl besitzt mindestens 3 Primfaktoren.

[Bearbeiten] pi -1 teilt c-1 für c = p1 ·p2 · ... · pn

Für jeden Primteiler p_i\ einer Carmichael-Zahl c\ gilt, das p_i - 1\ die Zahl c -1\ teilt.

  • Beispiel
1105\ ist das Produkt von 5\ , 13\ und 17\ . Da 1105\ eine Carmichael-Zahl ist, gilt nach dem Korselt-Kriterium:
4\ teilt 1104\ \Rightarrow \frac{1104}{4} = 276
12\ teilt 1104\ \Rightarrow \frac{1104}{12} = 92
und
16\ teilt 1104\ \Rightarrow \frac{1104}{16} = 69


[Bearbeiten] ac-1 ≡ 1 mod c für alle zu c teilfremden a

Unter den fermatschen Pseudoprimzahlen ist sie die Königin, denn für sie gilt, zu jeder Basis natürlichen Basis a \ge 2 zu der die Carmichael-Zahl c\ teilerfremd ist, gilt a^{c-1} \equiv 1 \mod c

  • Beispiel
Die Zahl 561 = 3\cdot 11\cdot 17 ist eine Carmichael-Zahl.
Die Zahlen 43\ , 49\ und 65\ sind teilerfremd zur 561\ , also gelten:
43^{560} \equiv 1 \mod 561
49^{560} \equiv 1 \mod 561
65^{560} \equiv 1 \mod 561
Die Zahlen 51\ , 55\ und 57\ sind nicht teilerfremd zur 561\ , also gelten:
51^{560} \not\equiv 1 \mod 561
55^{560} \not\equiv 1 \mod 561
57^{560} \not\equiv 1 \mod 561


[Bearbeiten] Carmichael-Zahlen generieren

Es gibt zwei Wege, an Carmichael-Zahlen zu kommen. Der eine ist, sich zufällig natürliche Zahlen zu erzeugen, um dann auf a^{c-1} \equiv 1 \mod c und \operatorname{ggT}(a,c)=1 für alle 2 \le a \le c-2 zu testen. Der Erfolg, auf diese Weise Carmichael-Zahlen zu finden ist sehr gering. Will man allerdings Carmichael-Zahlen zu vermeiden, so ist dieser Weg vorzuziehen. Der andere Weg ist, konsequent das Produkt aus mindestens drei, zueinander teilerfremden Primzahlen zu bilden, um die so erzeugten Zahlen auf das Korelt-Kriterium zu prüfen.

Nicht jedes quadratfreie Produkt aus Primzahlen kann eine Carmichael-Zahl sein. Ansonsten gäbe es jede Menge Carmichael-Zahlen. Aber kann man bestimmte Primzahlkombinationen schon vorher ausschliessen? Man kann! Es gilt nämlich, das zwei natürliche Zahlen n\ und n-1\ zueeinander Teilerfremd sind. Das bedeutet, das n\ und n-1\ keine gemeinsamen Teiler besitzen.

Es ist also wichtig, das bei der generierten Zahl n = p_1\cdot p_2\cdot p_3\cdot ... p_n alle p_i\ zu allen p_i-1\ teilerfremd sind. Das ist nicht selbstverständlich, wie das folgende Beispiel zeigt:

5\cdot 11\cdot 23\cdot 47 = 59455
(5-1)\cdot (11-1)\cdot (23-1)\cdot (47-1) = 40480

Wichtig an dem Beispiel ist, das (11-1) durch 5 teilbar ist, (23-1) durch 11 und (47-1) durch 23. Ein solches Produkt kann nie eine Carmichael-Zahl sein.

Wenn also die Primzahl p_i\ Teil einer Carmichael-Zahl sein soll, so sind alle Primzahlen der Form m\cdot p_i+1 als Teil der Carmichael-Zahl ausgeschlossen.

3 7 13 19 31 37 43 61 67 73 79 ...
5 11 31 41 61 71 101 ...
7 29 43 71 ...

[Bearbeiten] Carmichael-Zahlen nach Chernick

Wenn man sich auf eine spezielle Form der Carmichael-Zahlen beschränken will, dann gibt es noch die Carmichael-Zahlen nach Chernick. Diese haben die allgemeine Form:

M_k(m) = (6m + 1)(12m + 1)\prod_{i=1}^{k-2}(9 \cdot 2^im+1)

wobei eine Einschränkung für Carmichael-Zahlen nach Chernick M_k(m)\ für m \ge 5\ existiert:

Für (36*2^jm+1)\ gilt, das die Zahl m\ durch 2^j\ teilbar sein muss.

Für M_k(3)\ lautet die Formel (6m + 1)\cdot (12m + 1)\cdot (18m + 1)\ , die äquivalent zu der Formel p\cdot (2p - 1)\cdot (3p - 2)\ für p > 3\ ist.

Für M_k(4)\ lautet die Formel (6m + 1)\cdot (12m + 1)\cdot (18m + 1)\cdot (36m + 1)\ .

[Bearbeiten] Beweis der Äquivalenz

Warum sind die beiden Konstruktionsvorschriften:

Eine Zahl M3(m) = (6m + 1)(12m + 1)(18m + 1) ist dann eine Carmichael-Zahl,
wenn alle 3 Faktoren (6m + 1), (12m + 1) und (18m + 1) Primzahlen sind.

und

Sei p > 3 eine Primzahl derart, dass auch 2p-1 und 3p-2 Primzahlen sind,
dann ist n = p(2p-1)(3p-2) eine Carmichael-Zahl

zueinander äquivalent? Es wäre doch möglich, das eine Primzahl p\ , die nicht der Form 6m + 1\ entspricht, existiert, so daß 2p-1\ und 3p-2\ auch Primzahlen sind. Nun, so eine Primzahl existiert nicht.

Es gibt nur zwei Arten von Primzahlen p\ mit p > 3\ , nämlich Primzahlen der Form 6m + 1\ und Primzahlen der Form 6m - 1\ . Wenn man p\ durch 6m - 1\ ersetzt, bekommt man statt 2p - 1\ den Ausdruck 2(6m-1) - 1\ . Ausmultipliziert und zusammengefaßt macht das 12m - 3\ . Dieser Ausdruck ist also stets durch drei teilbar. Nur mit einer Primzahl der Form 6m + 1\ kann man mit der Formel p\cdot (2p - 1)\cdot (3p - 2)\ für p > 3\ eine Carmichael-Zahl bekommen.

[Bearbeiten] absolute eulersche Pseudoprimzahlen

Eine absolute eulersche Pseudoprimzahl ist eine Carmichael-Zahl, die außerdem zu jeder, zu ihr teilerfremden, Basis a euler-pseudoprim ist.

Von „http://de.wikibooks.org/wiki/Pseudoprimzahlen:_Makropseudoprimzahlen“
Persönliche Werkzeuge