Benutzer:Arbol01/Pseudoprimzahlen Analyse Der kleine fermatsche Satz

Pseudoprimzahlen

Einleitung

Um mal hinter diesen kleinen, unscheinbaren Satz Wenn n eine Primzahl ist, dann gilt $a^{n-1}\equiv 1\mod n$ zu sehen, beschäftigen wir uns mal mit Potenzen und Modulo. Vor allem brauchen wir aber die Carmichael-Funktion.

Die Carmichael-Funktion

Was macht die Carmichael-Funktion? Vor allem gibt sie eine Potenz zurück, bei der für alle Basen $a\$ modulo zu einer bestimmten, zu $a\$ teilerfremden, natürlichen Zahl $n>2\$ gilt: $a^{\lambda (n)}\equiv 1\mod n$.

Für unsere Zwecke liefert sie ein Intervall zurück. Angenommen, wir wollen die Folge $a^{m}\mod n$ mit steigendem $m\$ berechnen, also $a^{1}\mod n,a^{1}\mod n,a^{2}\mod n,a^{3}\mod n,...\$. Machen wir das mal mit $a=5\$ und $n=91\$:

$5,25,34,79,31,64,47,53,83,51,73,1,5,25,34,...$

Nach 12 Gliedern der Folge wiederholt sich das Muster. Das Intervall beträgt also 12, und das ist der Wert, den die Carmichael-Funktion $\lambda (91)\$ zurückliefert. Die Carmichael-Funktion liefert also die Intervallänge zurück.

Die Tabelle

Wir erstellen jetzt eine Tabelle mit der wir uns später verschiedene Zahlen ansehen:

	1	2	3	...	λ(n)
1:	1	1	1	...	1
2:	21	22	23	...	2λ(n)
3:	31	32	33	...	3λ(n)
...	...	...	...	...	...
n-1:	(n-1)1	(n-1)2	(n-1)3	...	(n-1)λ(n)

Das sieht jetz ziemlich furchtbar aus, ist aber am Beispiel einfach zu verstehen.

Die Primzahl 7

Die Intervallänge von 7 ist $\lambda (7)=1*(7-1)=6\$

	1	2	3	4	5	6
1:	1	1	1	1	1	1
2:	2	4	1	2	4	1
3:	3	2	6	4	5	1
4:	4	2	1	4	2	1
5:	5	4	6	2	3	1
6:	6	1	6	1	6	1

Da man beim kleinen fermatschen Satz $a^{n-1}\$ verwendet, brauchen wir bei der Berechnung $(7-1)=6\$, was der fettgedruckten Spalte entspricht:

	1	2	3	4	5	6
1:	1	1	1	1	1	1
2:	2	4	1	2	4	1
3:	3	2	6	4	5	1
4:	4	2	1	4	2	1
5:	5	4	6	2	3	1
6:	6	1	6	1	6	1

Das funktioniert für jede Primzahl, da für Primzahl $p\$ gilt: $\lambda (p)=p-1\$

Die zusammengesetzte Zahl 15

Die Intervallänge von 15 ist $\lambda (3\cdot 5)=\operatorname {kgv} (\lambda (3),\lambda (5))=\operatorname {kgv} (2,4)=4$ Wie man leicht festsellen kann, liegt $(15-1)=14\$ nicht auf der vierten Spalte der Tabelle, sondern auf zweiten Spalte:

	1	2	3	4
1:	1	1	1	1
2:	2	4	8	1
4:	4	1	4	1
7:	7	4	13	1
8:	8	4	2	1
11:	11	1	11	1
13:	13	4	7	1
14:	14	1	14	1

In dieser Spalte sind nun nicht mehr alle Werte 1. Der einfacherhalber wurden alle Basen, die nicht teilerfremd zur 15 sind weggelassen. Nur für die Basen $a\$ 4, 11 und 14 gilt:

$a^{14}\equiv 1\mod 15\$

Zu diesen Basen ist 15 pseudoprim.

Da $4^{2}\equiv 1\mod 15\$ gilt, gilt für alle zur 15 teilerfremden Basis $a\$ aber:

$a^{14*2}\equiv 1\mod 15\$