Pseudoprimzahlen: Absolute Fermatsche Pseudoprimzahlen

Pseudoprimzahlen

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 Primzahlen als auch für Carmichael-Zahlen 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.

Carmichael-Zahlen haben folgende Eigenschaften:

1. Eine Carmichael-Zahl ist quadratfrei.
2. Eine Carmichael-Zahl hat 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 einer Carmichael-Zahl $c\$ teilerfremd sind, ist $a^{c-1}\equiv 1{\pmod {c}}$.

Quadratfreiheit

Warum muss eine Carmichael-Zahl quadratfrei sein? Angenommen es gibt eine Carmichael-Zahl, die nicht quadratfrei ist. Sie hat der Einfachheit halber die Form $c=p_{1}^{n}\cdot p_{2}$ mit $n\geq 2$. Außerdem 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 $\lambda (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 dass $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, dass $c\$ und $c-1\$ zueinander teilerfremd sind, also keinen gemeinsamen Teiler besitzen. Also ist es nicht möglich, dass eine Carmichael-Zahl nicht quadratfrei ist.

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\neq 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 nur einem Primfaktor kann es nach Definition nicht geben (denn sie sind 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, dass eine Carmichael-Zahl mindestens 3 Primfaktoren hat.

Satz von Korselt

Der deutsche Mathematiker Alwin Reinhold Korselt hat 1899 ein Theorem über eine bestimmte Art von Pseudoprimzahlen, die später Carmichael-Zahlen genannt wurden, aufgestellt:

1. Es existieren ungerade, quadratfreie natürliche Zahlen $c$, so dass $a^{c}-a$ für alle natürlichen Zahlen $a$ ein Vielfaches von $c$ ist
2. Für alle Primteiler $p$ von $c$ gilt, dass $p-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 Satz von Korselt:

${\frac {1104}{4}}=276$	$\Rightarrow 4\$ teilt $1104\$
${\frac {1104}{12}}=92$	$\Rightarrow 12\$ teilt $1104\$ und
${\frac {1104}{16}}=69$	$\Rightarrow 16\$ teilt $1104\$.

Pseudoprim zu allen zu c teilfremden Basen a

Unter den fermatschen Pseudoprimzahlen ist sie die Königin, denn für sie gilt, mit jeder natürlichen Zahl $a\geq 2$, zu der die Carmichael-Zahl $c\$ teilerfremd ist,

$a^{c-1}\equiv 1{\pmod {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$

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{\pmod {c}}$ und $\operatorname {ggT} (a,c)=1$ für alle $2\leq a\leq c-2$ zu testen. Die Wahrscheinlichkeit, auf diese Weise Carmichael-Zahlen zu finden ist sehr gering. Will man allerdings Carmichael-Zahlen 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 Korselt-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 ausschließen? Man kann! Es gilt nämlich, dass zwei natürliche Zahlen $n\$ und $n-1\$ zueinander teilerfremd sind. Das bedeutet, dass $n\$ und $n-1\$ keine gemeinsamen Teiler besitzen.

Es ist also wichtig, dass bei der generierten Zahl $n=p_{1}\cdot p_{2}\cdot p_{3}\cdot ...p_{n}$ alle $p_{i}\$ zu allen $p_{j}-1\$ teilerfremd sind. Das ist nicht selbstverständlich, wie das folgende Beispiel zeigt:

$5\cdot 11\cdot 23\cdot 47=59455$

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

Wenn also die Primzahl $p_{i}\$ Teiler einer Carmichael-Zahl sein soll, so sind alle Primzahlen der Form $m\cdot p_{i}+1$ als Teiler der Carmichael-Zahl ausgeschlossen.

$p_{i}$	$m\cdot p_{i}+1$
3	7	13	19	31	37	43	61	67	73	79	...
5	11	31	41	61	71	101	...
7	29	43	71	...

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^{i}m+1)$

wobei alle Faktoren Primzahlen sind, und für k > 4 die Zahl $m\$ durch $2^{k-4}\$ 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)\$.

Beweis der Äquivalenz

Warum sind die beiden Konstruktionsvorschriften:

Eine Zahl $M_{3}(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.

Absolute eulersche Pseudoprimzahlen

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

Für jeden Primteiler $p_{i}\$ einer absoluten Eulerschen Pseudoprimzahl $n\$ gilt:

$p_{i}-1\$ teilt ${\frac {n-1}{2}}\$.

Die ersten absoluten Eulerschen Pseudoprimzahlen sind 1729, 2465, 15841, 41041, 46657, 75361.

Es gibt keine absoluten Euler-Jacobi-Pseudoprimzahlen.

Häufigkeit und Überschneidung mit Lucas-Pseudoprimzahlen

Anzahl der Carmichael-Zahlen und Überschneidung
mit starken und Lucas-Pseudoprimzahlen

				gleichzeitig Carmichael- &
Obergrenze x	Carmichael	f(x)(I)	abs epsp	sPsp(2)	lpsp	Lucas3(7,*)
10 3	1	0.014	0	0	0	0
10 4	7	0.072	2	0	0	0
10 5	16	0.054	6	3	0	0
10 6	43	0.047	16	5	0	0
10 7	105	0.050	45	11	0	0
10 8	255	0.042	124	19	0	0
10 9	646	0.036	306	43	0	0
1010	1547	0.031	740	87	0	0
1011	3605	0.024	1736	171	0	0
1012	8241	0.019	4011	316	0	0
1013	19279	0.015	9362	621	0	0
1014	44706	0.012	21974	1153	0	0
1015	105212	0.009	52221	2234	0	0
1016	246683	0.007	122608	4185	0	0

^(I) Mittlerer Anteil falscher Zeugen beim Miller-Rabin-Test.