Der kleine Satz von Fermat

Für jede ganze Zahl [math]a \in\mathbb{Z}[/math] und jede Primzahl [math]p[/math] gilt:

[math] a^p\ \ mod\ p=a[/math]

Dabei bedeutet mod „Teilen mit Rest“ : z.B. ist [math]10\ mod\ 7=3[/math], denn [math]10/7=1\ Rest\ 3[/math].
Auf den kleinen Satz von Fermat angewendet bedeutet dies, dass der Rest bei ganzzahliger Division von [math]a^{p}/ p[/math] genau [math]a[/math] ist. Dies ist gleichbedeutend damit, dass [math](a^p-a)\ mod\ p=0[/math], d.h. dass [math]p[/math] die Zahl [math]({a\ }^p\ – a)[/math] teilt. Dies wird auch geschrieben als [math]p|a^p-a\ [/math].

Beweis

Erste Methode: Induktion

Bewiesen werden kann dieser Satz über vollständige Induktion nach [math]a[/math]: Dabei werden zwei Fälle unterschieden:
1.Fall: [math]a\geq0[/math]

Induktionsanfang: [math]a\ =\ 0[/math]

[math]p|a^p-a[/math]

äquivalent zu

[math]p|0^p-0[/math]

Diese Aussage ist wahr für alle Primzahlen [math]p[/math], da jede ganze Zahl die [math]0[/math] teilt.

Induktionsschritt:

Es gelte für ein festes, aber beliebiges [math]a[/math] und alle Primzahlen [math]p[/math]: [math]p|a^p-a\ [/math]

Nun ist zu zeigen, dass die Aussage auch für [math]a+1[/math] gilt, d.h [math]p|{(a+1)}^p-(a+1)[/math]

Durch Anwenden des binomischen Lehrsatzes und anschließendes Herausziehen des ersten und letzten Summanden erhält man:

[math]({a+1)\ }^p-(a+1)=\sum_{k=0}^{p\ }{\ \binom{p}{k}\ }a^{p-k}1^k-(a+1)\ [/math]

[math]=\binom{p}{0}\ a^p\ \ +\ \ \ \sum_{k=1}^{p-1}{\ \binom{p}{k}}{\ a}^{p-k}+\binom{p}{p}a^0-a-1[/math]

[math]=a^p\ \ +\ \ \ \sum_{k=1}^{p-1}{\ \binom{p}{k}}\ {\ a}^{p-k}+1-a-1[/math]

[math]{=a}^p-a\ \ +\ \ \ \sum_{k=1}^{p-1}{\ \binom{p}{k}\ a}^{p-k}[/math]

Der erste Summand ist nach Induktionsvoraussetzung bereits durch [math]p[/math] teilbar.Bleibt zu zeigen, dass auch der zweite Summand durch [math]p[/math] teilbar ist.

Behauptung: [math]p|\binom{p}{k}[/math] für [math]1\le k\le p-1[/math]

Nach Definition des Binomialkoeffizienten gilt:

[math]\binom{p}{k}\ =\frac{p!}{k!\ \left(p-k\right)!}[/math]

äquivalent zu

[math]\binom{p}{k}k!=\ \frac{p!}{\left(p-k\right)!}[/math]

[math]\Rightarrow\frac{p!}{\left(p-k\right)!}=\frac{\left(p-k\right)\ \left(p-k+1\right)\ldots\left(p-1\right)\ p}{\left(p-k\right)!}=\left(p-k+1\right)\ldots\left(p-1\right)\ p[/math]

[math]\Rightarrow p|\frac{p!}{\left(p-k\right)!}[/math] , da [math]p[/math] als Faktor vorkommt.

Somit ist die rechte Seite der obigen Gleichung durch [math]p[/math] teilbar. Da [math]k \le p-1[/math] und [math]p[/math] eine Primzahl ist und somit insbesondere teilerfremd zu allen Zahlen kleiner gleich [math]p-1[/math], ist [math]k![/math] nicht durch [math]p[/math] teilbar. Folglich muss der Primfaktor [math]p[/math] also in [math]\binom{p}{k}\ [/math] enthalten sein, da Primfaktoren nicht „aufgespaltet“ werden können, d.h [math]\binom{p}{k}\ [/math] ist durch [math]p[/math] teilbar.

Man erhält also insgesamt, dass von der Summe [math]a^p-a\ +\ \ \sum_{k=1}^{p-1}{\ \binom{p}{k}}{\ a}^{p-k}[/math] sowohl der erste Summand (nach Induktionsvoraussetzung) als auch jeder einzelne Summand des zweiten Summanden durch [math]p[/math] teilbar ist. Somit ist auch die ganze Summe durch [math]p[/math] teilbar.

2.Fall: [math]a\lt 0[/math]

Wir schreiben [math]-a[/math] anstatt [math]a[/math]:

[math]\Longrightarrow {(-a)}^p-(-a)={(-1)}^pa^p+a[/math]

Für ungerade Primzahlen (also alle außer die [math]2[/math]) gilt dann:

[math]\left(-a\right)^p-\left(-a\right)=-a^p+a=-(a^p-a)[/math]

Für positive [math]a[/math] weiß man aber schon aus dem ersten Fall, dass [math]p|a^p-a\ [/math]. Somit gilt auch [math]{-p|-(a}^p-a)[/math].

Falls [math]p = 2[/math]:

[math]\left(-a\right)^p-\left(-a\right)=a^2+a=a\ \left(a+1\right)[/math]

[math]\Longrightarrow p|{(-a)}^p-(-a)\ \Longleftrightarrow\ \ 2|a\ (a+1)[/math]

Da von zwei aufeinanderfolgenden ganzen Zahlen immer genau eine gerade ist, gilt die Aussage.

Der Miller-Rabin Test

Der Miller-Rabin Test ist ein probabilistischer Primzahltest, der als optimierte Version des klassischen Primzahltestes betrachtet werden kann. Ähnlich wie der Fermat’sche Test wird überprüft, ob eine Eigenschaft von Primzahlen auch für eine gegebene Zahl gilt. Dafür definiert man zuerst die starken Pseudoprimzahlen.

Starke Pseudoprimzahlen

Sei [math]n\gt 2[/math] eine natürliche, ungerade Zahl. [math]n[/math] lässt sich schreiben als [math]2^s\cdot d+1[/math], wobei [math]s,d[/math] natürliche Zahlen sind und [math]d[/math] ungerade. Sei nun [math]a\lt n[/math] eine natürliche Zahl. Man nennt [math]n[/math] eine starke Pseudoprimzahl zur Basis [math]a[/math], wenn [math]n[/math] eine der folgenden Bedingungen erfüllt:

• [math]a^d\equiv1\ mod\ n[/math]
• [math]a^{2^rd}\equiv-1\ mod\ n[/math] für eine beliebige, natürliche Zahl [math]0\le\ r\lt s[/math]

Lemma

Jede Primzahl ist auch eine starke Pseudoprimzahl.

Beweis: Eine notwendige Erkenntnis für den Beweis des Lemmas ist folgende:

Wenn [math]n[/math] eine Primzahl ist, dann hat das Polynom [math]X^2-1[/math] über [math]\mathbb{Z}/n\mathbb{Z}[/math] nur die beiden Wurzeln [math]x=1[/math] und [math]x=-1[/math].

Diese Aussage folgt direkt aus der Tatsache, dass die Anzahl der Nullstellen eines Polynoms über einem Körper höchstens gleich mit dem Grad des Polynoms ist. Da [math]X^2-1[/math] die beiden trivialen Wurzeln 1 und -1 über [math]\mathbb{Z}/n\mathbb{Z}[/math] hat, gibt es keine weiteren Nullstellen.

Nun gilt nach dem Kleinen Satz von Fermat:

[math]a^{2^sd}\equiv1\ mod\ n[/math]

Betrachtet man die Folge [math]a^{2^sd},\ \ a^{2^{s-1}d},\ \ldots,\ \ a^{2d},\ a^d[/math] so merkt man, dass jedes Glied, außer dem ersten, die Wurzel des vorherigen Folgengliedes ist. Da

[math]a^{2^sd}-1=\left(a^{2^{s-1}d}\right)^2-1\equiv0\ \ mod\ n[/math]

gilt:

[math]a^{2^{s-1}d}\equiv1\ mod\ n\ \ \left(1\right)[/math]

oder

[math]a^{2^{s-1}d}\equiv-1\ \ mod\ n\ \ \left(2\right)[/math]

Falls [math]\left(2\right)[/math] richtig ist, so ist die zweite Bedingung bereits erfüllt mit [math]r=s-1[/math]. Falls [math]\left(1\right)[/math] richtig ist, so wendet man wiederholt dieselben Schritte an bis entweder eins der Glieder kongruent modulo [math]n[/math] mit [math]-1[/math] ist oder alle Folgenglieder, insbesondere der letzte, kongruent modulo [math]n[/math] mit [math]1[/math] sind.

Der Miller-Rabin Test

Mittels der vorher bewiesenen Eigenschaft der Primzahlen ergibt sich folgender Algorithmus, bekannt als der Miller-Rabin Test:
Eingaben:

• eine natürliche, ungerade Zahl n, die getestet wird
• eine natürliche Zahl k, die die Anzahl der Wiederholungen des Testes angibt

Ausgabe:

• „zusammengesetzt”, wenn n nicht prim ist
• „wahrscheinlich prim“ sonst

Schritte:

1. Schreibe [math]n[/math] als [math]2^s\cdot d+1[/math] mit [math]s,d\in\mathbb{N}[/math], [math]d[/math] ungerade.
2. Wähle eine Zahl [math]a\in\left\{1,\ \ldots,\ \ n-1\right\}[/math] zufällig und gleichverteilt.
3. Teste ob [math]n[/math] eine starke Pseudoprimzahl zur Basis [math]a[/math] ist.
4. Wurde eine Zahl [math]a[/math] gefunden, für die [math]n[/math] die Eigenschaft nicht erfüllt, so gebe “zusammengesetzt“ aus und stoppe das Verfahren. Wenn nicht, dann wiederhole die vorherigen Schritte, insgesamt nicht mehr als k mal.

Hat die gegebene Zahl beim k-maligen Durchlauf den Test bestanden, so gebe “wahrscheinlich prim“ aus.
Grundlegend für das angegebene Algorithmus ist die Tatsache, dass jede Zahl, die keine starke Pseudoprimzahl zu einer beliebigen Basis [math]a[/math] ist, keine Primzahl sein kann. Der Test besteht nun darin, zu der zu prüfenden Zahl [math]n[/math] eine Basis [math]a[/math] zu finden, so dass [math]n[/math] keine starke Pseudoprimzahl zur Basis [math]a[/math] ist und somit keine Primzahl. Findet man eine solche Zahl [math]a[/math], so nennt sich diese ein Zeuge der Zerlegbarkeit von [math]n[/math].

Für zusammengesetzte Zahlen [math]n[/math] lässt sich immer wenigstens ein Zeuge ihrer Zerlegbarkeit finden, aber nicht alle Zahlen [math]a[/math] eignen sich dazu (siehe das erste Beispiel). Daher muss man [math]n[/math] für mehrere Basen testen. Besteht die Zahl [math]n[/math] bei jedem Durchlauf den Test, so kann nur eine Wahrscheinlichkeitsaussage getroffen werden. Die Fehlerwahrscheinlichkeit, also die Wahrscheinlichkeit, dass die getestete Zahl keine Primzahl ist, nimmt ab je häufiger die Zahl [math]n[/math] den Test besteht. In der Praxis testet man die Zahl [math]n[/math] auf hinreichend vielen Basen [math]a[/math], so dass die Fehlerwahrscheinlichkeit vernachlässigbar klein ist.

Beispiele

I. Führen wir nun den Test [math]k=2[/math] mal für die Zahl [math]n=221[/math] durch.

1. Schritt: [math]n-1=220=2^2\cdot55\ \ \ \ [/math]

Also [math]s=2[/math] und [math]d=55[/math].

Erster Durchlauf:

2. Schritt: Wir wählen die Basis [math]a=174[/math].

3. Schritt: Wir testen, ob [math]n[/math] eine starke Pseudoprimzahl zur Basis [math]a[/math] ist:

[math]a^d\ mod\ n={174}^{55}\ mod\ 221=47\ \neq-1\ und\ \neq1[/math]

[math]a^{2d}\ mod\ n={174}^{110}\ mod\ 221=220=-1[/math]

Für [math]r=1[/math] gilt also [math]a^{2^rd}\equiv-1\ mod\ n[/math], also könnte [math]221[/math] prim sein.

Zweiter Durchlauf:

2. Schritt: Wir wählen die Basis [math]a=137[/math].

3. Schritt: Wir testen, ob [math]n[/math] eine starke Pseudoprimzahl zur Basis [math]a[/math] ist:

[math]a^d\ mod\ n={137}^{55}\ mod\ 221=188\neq-1\ und\ \neq1[/math]

[math]a^{2d}\ mod\ n={137}^{110}\ mod\ 221=205\neq-1[/math]

[math]a=137[/math] ist ein Zeuge der Zerlegbarkeit von [math]n=221[/math], also ist [math]221[/math] keine Primzahl.

II. Im Unterschied zu dem Fermat’schen Primzahltest filtert der Miller-Rabin Test auch die Carmichaelzahlen aus. Betrachten wir dafür die kleinste Carmichaelzahl [math]n=561[/math]. Wir führen den Test ein einziges Mal durch und wählen als Basis [math]a=2[/math].

1.Schritt: [math]n-1=560=2^4\cdot35[/math]

Also [math]s=4[/math] und [math]d=35[/math].

2. Schritt: [math]a=2[/math]

3. Schritt: Wir testen, ob [math]n[/math] eine starke Pseudoprimzahl zur Basis [math]a[/math] ist:

• [math]a^d\ mod\ n=2^{35\ }\ mod\ \ 561=263\neq-1\ und\ \neq1[/math]
• [math]a^{2d}\ mod\ n=2^{70}\ mod\ 561=166\neq-1[/math]
• [math]a^{2^2d}\ mod\ n=2^{140}\ mod\ 561=67\neq-1[/math]
• [math]a^{2^3d}\ mod\ n=2^{280}\ mod\ 561=1\neq-1[/math]

Somit erfüllt [math]n=561[/math] für die Basis [math]a=2[/math] keine der beiden Bedingungen einer starken Pseudoprimzahl und ist daher auch keine Primzahl.