Miller-Rabin-Test

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Der Miller-Rabin-Test (auch Miller-Selfridge-Rabin-Test) ist ein Algorithmus aus dem mathematischen Teilgebiet Zahlentheorie, insbesondere der algorithmischen Zahlentheorie. Er ist ein probabilistischer Primzahltest. Erhält er eine natürliche Zahl $n$ als Eingabe, so gibt er aus, ob diese Zahl eine Primzahl ist oder nicht. Gibt er dabei „ $n$ ist keine Primzahl“ aus, so ist das richtig. Gibt er allerdings „ $n$ ist eine Primzahl“ aus, so ist dies mit geringer Wahrscheinlichkeit falsch. Die Zahlen, die der Miller-Rabin-Test falscherweise als Primzahlen identifiziert, nennt man starke Pseudoprimzahlen. Da der Algorithmus nicht immer ein korrektes Ergebnis liefert, zählt er zur Klasse der Monte-Carlo-Algorithmen.

Die Miller-Rabin-Test ist nach Gary Miller und Michael O. Rabin benannt. John L. Selfridge hat diesen Test schon 1974 verwendet, bevor Miller ihn veröffentlicht hatte. Daher rührt der alternative Name Miller-Selfridge-Rabin-Test. ^[1]

Der Test basiert auf einem Satz von Miller, der eine Zahl mit hoher Sicherheit korrekt als Primzahl erkennt. Der Miller-Rabin-Test funktioniert ähnlich wie der Solovay-Strassen-Test.

[Bearbeiten] Vorgehensweise

Es sei $n$ diejenige Zahl, von der festgestellt werden soll, ob sie eine Primzahl ist oder nicht.

Zuerst wird eine beliebige Zahl $a$ mit $1 < a < n$ als Basis gewählt.
Der nächste Schritt benutzt einen Test, den nur Primzahlen und starke Pseudoprimzahlen überstehen können:

Wenn $a^d \equiv 1 \mod n$ oder $a^{d \cdot 2^r} \equiv -1 \mod n$ für ein

r

mit $0 \le r \le (s-1)$ gilt, wobei d den nicht durch die Zahl 2 dividierbaren Rest von $n - 1 = d \cdot 2^s$ darstellt, d.h. $s = \max\{r \in \mathbb{N} ~|~ 2^r$ teilt

n - 1}

, dann muss n entweder eine Primzahl oder aber eine starke Pseudoprimzahl sein.

[Bearbeiten] Zuverlässigkeit

Ist $n\geq 3$ ungerade und nicht prim, so enthält die Menge $\{1,2,\dots,n-1\}$ höchstens $\frac{n-1}{4}$ Elemente $a$ , $g g T (a, n) = 1$ die kein Zeuge für die Zusammengesetztheit von $n$ sind. Damit ist die Wahrscheinlichkeit, dass $n$ zusammengesetzt ist und ein zufälliges $a$ dafür kein Zeuge ist, höchstens $\frac{1}{4}$ .

Wiederholt man den Test mehrfach für verschiedene $a$ sinkt die Wahrscheinlichkeit entsprechend ab. So erreicht man beispielsweise schon nach vier Schritten, die das Ergebnis "wahrscheinlich prim" haben, eine Fehlerwahrscheinlichkeit von weniger als 0,5%.