Pseudoprimzahlen: Potenzen und Modulo

Pseudoprimzahlen

Potenzen

Wenn man eine Zahl immer wieder mit sich selbst multipliziert, erhält man eine Potenz. Eine bekannte Folge von steigenden Potenzen ist die folgende Folge aus Zweierpotenzen:

$2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,...\$

Verallgemeinert sieht eine solche Folge für eine beliebige Basis so aus:

$a,a^{2},a^{3},a^{4},a^{5},a^{6},...\$

Ein Feld solcher Zahlen sieht so aus:

	n	1	2	3	4	5	6	7	8	9	...
a
1		1	1	1	1	1	1	1	1	1	...
2		2	4	8	16	32	64	128	256	512	...
3		3	9	27	81	243	729	2187	6561	19683	...
4		4	16	64	256	1024	4096	16384	65536	262144	...
5		5	25	125	625	3125	15625	78125	390625	1953125	...
6		6	36	216	1296	7776	46656	279936	1679616	10077696	...
7		7	49	343	2401	16807	117649	823543	5764801	40353607	...
8		8	64	512	4096	32768	262144	2097152	16777216	134217728	...
9		9	81	729	6561	59049	531441	4782969	43046721	387420489	...
10		10	100	1000	10000	100000	1000000	10000000	100000000	1000000000	...
11		11	121	1331	14641	161051	1771561	19487171	214358881	2357947691	...
12		12	144	1728	20736	248832	2985984	35831808	429981696	5159780352	...
..		..	...	...	...	...	...	...	...	...	...

Die Struktur, die dahinter steckt, wird sichtbar, wenn man das ganze Feld eine mithilfe von Modulo und einem festen Faktor unterzieht:

• Beispiel: Modulo 7

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	...
1:	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	...
2:	2	4	1	2	4	1	2	4	1	2	4	1	2	4	1	2	4	1	...
3:	3	2	6	4	5	1	3	2	6	4	5	1	3	2	6	4	5	1	...
4:	4	2	1	4	2	1	4	2	1	4	2	1	4	2	1	4	2	1	...
5:	5	4	6	2	3	1	5	4	6	2	3	1	5	4	6	2	3	1	...
6:	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	...
7:	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	...
8:	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	...
9:	2	4	1	2	4	1	2	4	1	2	4	1	2	4	1	2	4	1	...
10:	3	2	6	4	5	1	3	2	6	4	5	1	3	2	6	4	5	1	...
11:	4	2	1	4	2	1	4	2	1	4	2	1	4	2	1	4	2	1	...
12:	5	4	6	2	3	1	5	4	6	2	3	1	5	4	6	2	3	1	...
13:	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	...
14:	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	...
15:	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	...
16:	2	4	1	2	4	1	2	4	1	2	4	1	2	4	1	2	4	1	...
17:	3	2	6	4	5	1	3	2	6	4	5	1	3	2	6	4	5	1	...
18:	4	2	1	4	2	1	4	2	1	4	2	1	4	2	1	4	2	1	...
19:	5	4	6	2	3	1	5	4	6	2	3	1	5	4	6	2	3	1	...
20:	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	...
21:	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	...

Die kleinste Einheit wird durch zwei Größen festgelegt, nämlich einmal den Wert $n\$, zu dem man das Ganze Modulo nimmt und der die Einheit nach unten begrenzt, und andererseits die Carmichael-Funktion $\lambda (n)$, die der kleinste gemeinsame Faktor darstellt, zu der für jeden zu $n\$ teilerfremden Wert $a\$ gilt: $a^{\lambda (n)}\equiv 1\mod n$.

Muster

Zu jeder natürlichen Zahl $n\$ gibt es ein individuelles Erscheinungsbild. Andererseits haben bestimmte Arten von Zahlen Gemeinsamkeiten. Um das, was Zahlen gemeinsam haben, geht es hier:

natürliche Zahlen

Alle natürlichen Zahlen haben eine Gemeinsamkeit in ihrer Struktur:

	1	2	3	4	5	6
1:	1	1	1	1	1	1
X:	X	X	X	X	X	X
X:	X	X	X	X	X	X
X:	X	X	X	X	X	X
X:	X	X	X	X	X	X
A:	A	1	A	1	A	1

In der obersten Zeile befinden sich immer Einsen und in der untersten Zeile befinden sich immer im Wechsel A und 1, wobei A für $n-1\$ steht. Dies ist also keine Charakteristik, die für Primzahlen typisch ist.

Primzahlen

Die für eine Primzahl typische Struktur sieht so aus:

	1	2	3	4	5	6
1:	1	1	1	1	1	1
X:	X	X	1	X	X	1
X:	X	X	A	X	X	1
X:	X	X	1	X	X	1
X:	X	X	A	X	X	1
A:	A	1	A	1	A	1

Zu der für jede natürliche Zahl typischen Zeilen kommen zwei Charaktaristika bei Primzahlen hinzu:

Erstens die geschlossene Einserspalte

1

1

1

...

in blau gefärbt. Die Einser sind die Werte, welche die Carmichael-Funktion $a^{\lambda (n)}$ zurückliefert.

Zweitens die, ebenfalls geschlossene, Zeile aus Einsern und Zahlen A die die Zahl (n-1) repräsentieren.

1

A

...

Hier sind es die Werte, die die nach der nach Euler modifizierten Funktion $a^{\frac {\lambda (n)}{2}}$ zurückgeliefert werden.

Unterscheidung der Primzahlen in 4k-1 und 4k+1-Form

Die Struktur von Primzahlen der Form 4k-1 und 4k+1 unterscheidet sich in einer Spalte:

1 2 3 4 5 6 7 8 9 10 1: 1 1 1 1 1 1 1 1 1 1 2: 2 4 8 5 10 9 7 3 6 1 3: 3 9 5 4 1 3 9 5 4 1 4: 4 5 9 3 1 4 5 9 3 1 5: 5 3 4 9 1 5 3 4 9 1 6: 6 3 7 9 10 5 8 4 2 1 7: 7 5 2 3 10 4 6 9 8 1 8: 8 9 6 4 10 3 2 5 7 1 9: 9 4 3 5 1 9 4 3 5 1 10: 10 1 10 1 10 1 10 1 10 1	1 2 3 4 5 6 7 8 9 10 11 12 1: 1 1 1 1 1 1 1 1 1 1 1 1 2: 2 4 8 3 6 12 11 9 5 10 7 1 3: 3 9 1 3 9 1 3 9 1 3 9 1 4: 4 3 12 9 10 1 4 3 12 9 10 1 5: 5 12 8 1 5 12 8 1 5 12 8 1 6: 6 10 8 9 2 12 7 3 5 4 11 1 7: 7 10 5 9 11 12 6 3 8 4 2 1 8: 8 12 5 1 8 12 5 1 8 12 5 1 9: 9 3 1 9 3 1 9 3 1 9 3 1 10: 10 9 12 3 4 1 10 9 12 3 4 1 11: 11 4 5 3 7 12 2 9 8 10 6 1 12: 12 1 12 1 12 1 12 1 12 1 12 1
Primzahl der Form 4k+3	Primzahl der Form 4k+1

Wie man sehen kann, ist die violette Spalte bei Primzahlen der Form 4k+1 symmetrisch und bei Primzahlen der Form 4k+3 komplementär.

Abgrenzung der Primzahlen von anderen natürlichen Zahlen

Bei allen anderen Arten natürlicher Zahlen fehlt die Geschlossenheit der beiden senkrechten Spalten.

1 2 3 4 5 6 1: 1 1 1 1 1 1 2: 2 4 8 7 5 1 3: 3 0 0 0 0 0 4: 4 7 1 4 7 1 5: 5 7 8 4 2 1 6: 6 0 0 0 0 0 7: 7 4 1 7 4 1 8: 8 1 8 1 8 1	1 2 3 4 1: 1 1 1 1 2: 2 4 8 1 3: 3 9 2 6 4: 4 1 4 1 5: 5 10 5 10 6: 6 6 6 6 7: 7 4 13 1 8: 8 4 2 1 9: 9 6 9 6 10: 10 10 10 10 11: 11 1 11 1 12: 12 9 3 6 13: 13 4 7 1 14: 14 1 14 1
Neun	Fünfzehn

Wie man bei der Neun sehen kann, ist der Mittelbalken noch, wenn auch unterbrochen, vorhanden. Bei der 15 fehlt er vollständig.

Carmichael-Zahlen

Nachdem was bisher geschrieben worden ist, müßte die Neun, und damit alle Quadrate einer Primzahl, eine perfekte Fast-Primzahl sein. Dem ist aber nicht so. Damit eine Nichtprimzahl eine gute Fast-Primzahl sein kann, muß eines zutreffen: $n-1\$ muß durch $\lambda (n)\$ teilbar sein. Nichtprimzahlen mit dieser Eigenschaft nennt man Carmichael-Zahlen.

Was stimmt nun also an der Neun nicht? Die Einser liegen auf der blauen und, mit den Achten, auf der violetten Spalte.

Sie müßten allerdings auf der grünen Spalte liegen, und zusammen mit Achten auf der cyanen Spalte. Da ist aber weder eine Eins, noch eine Acht vorhanden. Einsen auf der grünen Spalte sind typisch für fermatsche Pseudoprimzahlen, und Einsen, bzw. (n-1) auf der cyanen Spalte sind typisch für eulersche Pseudoprimzahlen.

	1	2	3	4	5	6
1:	1	1	1	1	1	1
2:	2	4	8	7	5	1
3:	3	0	0	0	0	0
4:	4	7	1	4	7	1
5:	5	7	8	4	2	1
6:	6	0	0	0	0	0
7:	7	4	1	7	4	1
8:	8	1	8	1	8	1

Die weiter oben abgebildete 15 ist eine fermatsche Pseudoprimzahl zu den Basen 4 und 11.

Folgerichtig muß man die Struktur für eine typische Primzahl ergänzen:

	1	2	3	4	5	6
1:	1	1	1	1	1	1
X:	X	X	1	X	X	1
X:	X	X	A	X	X	1
X:	X	X	1	X	X	1
X:	X	X	A	X	X	1
A:	A	1	A	1	A	1

Pseudoprimzahlen

Selbstreferenzierende Spalte

Wie ja schon bekannt ist, gilt für eine Primzahl $p\$, das für jede zu $p\$ teilerfremde Basis $a\$ $a^{p-1}\equiv 1\mod p$ gilt (Siehe blaue Spalte in der unteren Tabelle).

	1	2	3	4	5	6	7	8	9	10	11	12
1:	1	1	1	1	1	1	1	1	1	1	1	1
2:	2	4	8	3	6	12	11	9	5	10	7	1
3:	3	9	1	3	9	1	3	9	1	3	9	1
4:	4	3	12	9	10	1	4	3	12	9	10	1
5:	5	12	8	1	5	12	8	1	5	12	8	1
6:	6	10	8	9	2	12	7	3	5	4	11	1
7:	7	10	5	9	11	12	6	3	8	4	2	1
8:	8	12	5	1	8	12	5	1	8	12	5	1
9:	9	3	1	9	3	1	9	3	1	9	3	1
10:	10	9	12	3	4	1	10	9	12	3	4	1
11:	11	4	5	3	7	12	2	9	8	10	6	1
12:	12	1	12	1	12	1	12	1	12	1	12	1

Nun ist $p-1\$ aber keine Primzahl, sondern läßt sich in Faktoren zerlegen. So gilt für die unten stehende Tabelle für die Primzahl $p=13\$ das $(p-1)=12=2\cdot 2\cdot 3$ ist, sich also z.B. in $2\cdot 6$ und $3\cdot 4$ zerlegen läßt. Das bedeutet, wenn sich ein Exponent $n\$ in zwei Faktoren $r\$ uns $s\$ zerlegen läßt, das $(a^{r})^{s}=(a^{s})^{r}=a^{r\cdot s}=a^{n}$ gilt.

Beispiele:

• $(5^{3})^{4}=5^{3\cdot 4}=5^{12}$
• $(5^{2})^{6}=5^{2\cdot 6}=5^{12}$

	1	2	3	4	5	6	7	8	9	10	11	12
1:	1	1	1	1	1	1	1	1	1	1	1	1
2:	2	4	8	3	6	12	11	9	5	10	7	1
3:	3	9	1	3	9	1	3	9	1	3	9	1
4:	4	3	12	9	10	1	4	3	12	9	10	1
5:	5	12	8	1	5	12	8	1	5	12	8	1
6:	6	10	8	9	2	12	7	3	5	4	11	1
7:	7	10	5	9	11	12	6	3	8	4	2	1
8:	8	12	5	1	8	12	5	1	8	12	5	1
9:	9	3	1	9	3	1	9	3	1	9	3	1
10:	10	9	12	3	4	1	10	9	12	3	4	1
11:	11	4	5	3	7	12	2	9	8	10	6	1
12:	12	1	12	1	12	1	12	1	12	1	12	1

pure eulersche Pseudoprimzahl

Mit der puren eulerschen Pseudoprimzahl ist eine fermatsche Pseudoprimzahl gemeint, bei der jede Basis, zu der die Zahl eine fermatsche Pseuodoprimzahl ist, auch gilt, das die Zahl zu der gleichen Basis auch eine eulersche Pseudoprimzahl ist.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2: 2 4 8 16 7 14 3 6 12 24 23 21 17 9 18 11 22 19 13 1 3: 3 9 2 6 18 4 12 11 8 24 22 16 23 19 7 21 13 14 17 1 4: 4 16 14 6 24 21 9 11 19 1 4 16 14 6 24 21 9 11 19 1 5: 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6: 6 11 16 21 1 6 11 16 21 1 6 11 16 21 1 6 11 16 21 1 7: 7 24 18 1 7 24 18 1 7 24 18 1 7 24 18 1 7 24 18 1 8: 8 14 12 21 18 19 2 16 3 24 17 11 13 4 7 6 23 9 22 1 9: 9 6 4 11 24 16 19 21 14 1 9 6 4 11 24 16 19 21 14 1 10: 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11: 11 21 6 16 1 11 21 6 16 1 11 21 6 16 1 11 21 6 16 1 12: 12 19 3 11 7 9 8 21 2 24 13 6 22 14 18 16 17 4 23 1 13: 13 19 22 11 18 9 17 21 23 24 12 6 3 14 7 16 8 4 2 1 14: 14 21 19 16 24 11 4 6 9 1 14 21 19 16 24 11 4 6 9 1 15: 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 16: 16 6 21 11 1 16 6 21 11 1 16 6 21 11 1 16 6 21 11 1 17: 17 14 13 21 7 19 23 16 22 24 8 11 12 4 18 6 2 9 3 1 18: 18 24 7 1 18 24 7 1 18 24 7 1 18 24 7 1 18 24 7 1 19: 19 11 9 21 24 6 14 16 4 1 19 11 9 21 24 6 14 16 4 1 20: 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 21: 21 16 11 6 1 21 16 11 6 1 21 16 11 6 1 21 16 11 6 1 22: 22 9 23 6 7 4 13 11 17 24 3 16 2 19 18 21 12 14 8 1 23: 23 4 17 16 18 14 22 6 13 24 2 21 8 9 7 11 3 19 12 1 24: 24 1 24 1 24 1 24 1 24 1 24 1 24 1 24 1 24 1 24 1

1 2 3 4 5 6 7 8 9 10 1: 1 1 1 1 1 1 1 1 1 1 2: 2 4 8 16 32 31 29 25 17 1 3: 3 9 27 15 12 3 9 27 15 12 4: 4 16 31 25 1 4 16 31 25 1 5: 5 25 26 31 23 16 14 4 20 1 6: 6 3 18 9 21 27 30 15 24 12 7: 7 16 13 25 10 4 28 31 19 1 8: 8 31 17 4 32 25 2 16 29 1 9: 9 15 3 27 12 9 15 3 27 12 10: 10 1 10 1 10 1 10 1 10 1 11: 11 22 11 22 11 22 11 22 11 22 12: 12 12 12 12 12 12 12 12 12 12 13: 13 4 19 16 10 31 7 25 28 1 14: 14 31 5 4 23 25 20 16 26 1 15: 15 27 9 3 12 15 27 9 3 12 16: 16 25 4 31 1 16 25 4 31 1 17: 17 25 29 31 32 16 8 4 2 1 18: 18 27 24 3 21 15 6 9 30 12 19: 19 31 28 4 10 25 13 16 7 1 20: 20 4 14 16 23 31 26 25 5 1 21: 21 12 21 12 21 12 21 12 21 12 22: 22 22 22 22 22 22 22 22 22 22 23: 23 1 23 1 23 1 23 1 23 1 24: 24 15 30 27 21 9 18 3 6 12 25: 25 31 16 4 1 25 31 16 4 1 26: 26 16 20 25 23 4 5 31 14 1 27: 27 3 15 9 12 27 3 15 9 12 28: 28 25 7 31 10 16 19 4 13 1 29: 29 16 2 25 32 4 17 31 8 1 30: 30 9 6 15 21 3 24 27 18 12 31: 31 4 25 16 1 31 4 25 16 1 32: 32 1 32 1 32 1 32 1 32 1

Es gibt auch fermatsche Pseudoprimzahlen, bei denen die Pseudoprimzahl keine eulersche Pseudoprimzahl ist. Zu diesen fermatschen Pseudoprimzahlen zählen u.a. die 45, 91 und 153.