Der kleine Satz von Fermat

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] (oder [math]a^{2^sd}[/math]ist teilbar durch [math]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.