Miller-Rabin-Test

Der Miller-Rabin-Test oder Miller-Selfridge-Rabin-Test ist ein Algorithmus aus dem mathematischen Teilgebiet Zahlentheorie, insbesondere der algorithmischen Zahlentheorie.

Er ist ein probabilistischer Primzahltest, für den aber für Zahlen unter 10¹⁶ eine deterministische Verwendung möglich ist.

Erhält der probabilistische Test eine natürliche Zahl n als Eingabe, so gibt er entweder „n ist keine Primzahl“ oder „n ist wahrscheinlich eine Primzahl“ aus, das Ergebnis ist von n und dem Zufall abhängig. Er zählt zur Klasse der Monte-Carlo-Algorithmen.

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

Der Miller-Rabin-Test funktioniert ähnlich wie der Solovay-Strassen-Test, ist diesem allerdings in allen Aspekten überlegen. Er ist schneller, seine Irrtumswahrscheinlichkeit ist geringer und jede Zahl, die der Solovay-Strassen-Test als zusammengesetzt erkennt, weist auch der Miller-Rabin-Test als zusammengesetzte Zahl aus.

Algorithmus

Es sei n eine ungerade Zahl, von der festgestellt werden soll, ob sie eine Primzahl ist oder nicht. Zuerst wählt man eine Basis a zufällig aus den Zahlen 2, 3, …, n - 1.

Der nächste Schritt benutzt einen Test, den nur Primzahlen und starke Pseudoprimzahlen (zur Basis a) bestehen. Schreibt man nämlich

$n - 1 = d \cdot 2^j$

mit ungeradem d, so gilt, falls n prim ist:

$a^d \equiv 1 \mod n$

oder

$a^{d \cdot 2^r} \equiv -1 \mod n$

für ein r mit 0 ≤ r < j. Die Herleitung dieser Kongruenzen ist im nächsten Abschnitt und im Artikel starke Pseudoprimzahl zu finden. Diese Bedingung wird jedoch (zu jeder Basis a) gelegentlich auch von zusammengesetzten Zahlen erfüllt. Diese heißen starke Pseudoprimzahlen zur Basis a.

Funktionsweise

Der Miller-Rabin-Test berechnet modulo n die Folge

$(a^d, a^{2d}, a^{4d}, \ldots, a^{2^{j-1}d}, a^{2^jd})$

mit 2^jd = n − 1. Jedes Element der Folge ist hierbei das Quadrat seines Vorgängers.

Ist n eine Primzahl, dann gilt nach dem kleinen fermatschen Satz

$a^{2^jd} \equiv a^{n-1} \equiv 1 \pmod n$

und die vom Miller-Rabin-Test berechnete Folge hat deshalb die Form

$(a^d, a^{2d}, a^{4d}, \ldots, a^{2^{j-1}d}, 1)$

Die einzigen Zahlen x mit

$x^2 \equiv 1 \pmod n$

sind für eine Primzahl n die Zahlen 1 und -1, wie der folgenden Beweis zeigt.

$\begin{align} x^2 \equiv 1 \pmod n &\Leftrightarrow x^2 - 1 \equiv 0 \pmod n\\ &\Leftrightarrow n | x^2 - 1\\ &\Leftrightarrow n | (x - 1)(x + 1)\\ &\Leftrightarrow n | (x - 1) \quad \text{oder} \quad n|(x + 1)\\ &\Leftrightarrow x - 1 \equiv 0 \pmod n \quad \text{oder} \quad x + 1 \equiv 0 \pmod n\\ &\Leftrightarrow x \equiv 1 \pmod n \quad \text{oder} \quad x \equiv -1 \pmod n\\ \end{align}$

Aus diesem Grund ist der Vorgänger einer 1 in der Folge immer eine 1 oder eine -1. Dies führt dazu, dass für eine Primzahl n die Folge des Miller-Rabin-Tests entweder $(1, 1, \ldots, 1)$ oder $(?, ?, \ldots, ?, -1, 1, \ldots, 1)$ ist, wobei die Fragezeichen für beliebige Zahlen stehen.

Ist n eine beliebige Zahl und beginnt die vom Miller-Rabin-Test berechnete Folge nicht mit 1 und enthält auch keine -1, dann kann n keine Primzahl sein. Es gibt allerdings zusammengesetzte Zahlen, bei denen die Folge bei einer Basis a mit 1 beginnt oder eine -1 enthält. Das sind die schon erwähnten starken Pseudoprimzahlen zur Basis a.

Zuverlässigkeit

Ist n ≥ 3 ungerade und nicht prim, so enthält die Menge {2,3,…,n-2} höchstens $\tfrac{n-3}{4}$ Elemente a mit ggT(a,n) = 1, die keine Zeugen für die Zusammengesetztheit von n sind. (Ist ggT(a,n) > 1, oder $a^{d\cdot2^r} \equiv 0 \mod n$ für irgendein r < j, dann wird n natürlich sofort als nicht-prim erkannt).

Ist ein zusammengesetztes ungerades n gegeben und wählt man zufällig ein a aus $\{2,3,\ldots,n-2\}$, dann ist somit die Wahrscheinlichkeit, dass n damit nicht als zusammengesetzt erkannt wird, kleiner als $\tfrac{1}{4}$. Wiederholt man den Test mehrfach für verschiedene a aus dieser Menge, sinkt die Wahrscheinlichkeit weiter ab. Nach s Schritten ist die Wahrscheinlichkeit, eine zusammengesetzte Zahl für prim zu halten, kleiner als $\tfrac{1}{4^s}$, also z. B. nach vier Schritten kleiner als 0,4 % und nach zehn Schritten kleiner als 10 ^{− 6}.

Deterministische Varianten

Der Miller–Rabin-Algorithmus kann deterministisch angewendet werden, indem alle Basen in einer bestimmten Menge getestet werden (Beispiel: wenn n < 9.080.191, dann ist es ausreichend a = 31 und 73 zu testen, siehe unten).

Wenn das getestete n zusammengesetzt ist, sind die zu n teilerfremden starken Pseudoprimzahlen a in einer echten Untergruppe von $\left(\mathbb{Z}/n\mathbb{Z}\right)^*$ enthalten. Dies bedeutet, dass beim Testen aller a aus einer Menge, die $\left(\mathbb{Z}/n\mathbb{Z}\right)^*$ erzeugt, eines der a ein Zeuge für das Zusammengesetztsein von n ist. Wenn angenommen wird, dass die Riemannsche Vermutung wahr ist, dann folgt daraus, dass die Gruppe durch ihre Elemente kleiner O((log n)²) generiert wird, was bereits von Miller angeführt wurde.^[3] Die Konstante in der Landau-Notation wurde von Eric Bach auf 2 reduziert.^[4] Deshalb erhält man einen deterministischen Primzahltest, wenn alle $a \in \{2,\ldots,\min(n-1,\lfloor2(\ln n)^2\rfloor)\}$ getestet werden. Die Laufzeit dieses Algorithmus ist O((log n)⁴).

Wenn die Zahl n klein ist, ist es nicht notwendig, alle a < 2(ln n)² zu testen, da bekannt ist, dass eine viel kleinere Anzahl ausreichend ist. Beispielsweise haben Pomerance, Selfridge und Wagstaff^[5] sowie Jaeschke^[6] folgendes verifiziert:

• Wenn n < 1.373.653, ist es ausreichend a = 2 und 3 zu testen,
• wenn n < 9.080.191, ist es ausreichend a = 31 und 73 zu testen,
• wenn n < 4.759.123.141, ist es ausreichend a = 2, 7, und 61 zu testen,
• wenn n < 2.152.302.898.747, ist es ausreichend a = 2, 3, 5, 7, und 11 zu testen,
• wenn n < 3.474.749.660.383, ist es ausreichend a = 2, 3, 5, 7, 11, und 13 zu testen,
• wenn n < 341.550.071.728.321, ist es ausreichend a = 2, 3, 5, 7, 11, 13, und 17 zu testen.^[7]

Siehe auch die Prime Pages^[8], Miller-Rabin SPRP bases records^[9], Zhang/Tang^[10] und ebenso die Folge A014233^[11] in OEIS zu anderen Kriterien ähnlicher Art. Auf diese Weise hat man sehr schnelle deterministische Primzahltests für Zahlen im geeigneten Bereich, ohne auf unbewiesene Annahmen zurückgreifen zu müssen.

Praktische Relevanz

Primzahltests werden vor allem in der Kryptographie benötigt. Ein typisches Beispiel ist die Schlüsselerstellung für das RSA-Kryptosystem, hierfür werden mehrere große Primzahlen benötigt. Zwar wurde im Jahr 2002 mit dem AKS-Primzahltest erstmals ein beweisbar deterministischer, in polynomialer Zeit laufender Primzahltest vorgestellt. Dessen Laufzeit ist jedoch für praktische Anwendungen meist zu hoch, weswegen für Kryptographie-Software meist immer noch der Miller-Rabin-Test eingesetzt wird. Dabei ist es zwar theoretisch möglich, dass eine zusammengesetzte Zahl als Primzahl genutzt wird, die Wahrscheinlichkeit ist jedoch so gering, dass es in der Praxis keine Rolle spielt.

Einzelnachweise

1. ↑ M. O. Rabin: Probabilistic algorithms. In: J. F. Traub (ed.): Algorithms and complexity. Academic Press 1976, S. 21–39, speziell S. 35/36, zum Teil nach Ideen von Miller
2. ↑ Song Y. Yan: Number theory for computing. 2. Auflage. Springer, 2002, S. 208–214
3. ↑ Gary L. Miller, Riemann's Hypothesis and Tests for Primality, Journal of Computer and System Sciences 13 (1976), no. 3, pp. 300–317.
4. ↑ Eric Bach, Explicit bounds for primality testing and related problems, Mathematics of Computation 55 (1990), no. 191, pp. 355–380.
5. ↑ C. Pomerance, J. L. Selfridge, S. S. Wagstaff, Jr.: The pseudoprimes to 25·10⁹, Math. Comp., 35 (1980) no. 151, S. 1003–1026.
6. ↑ Gerhard Jaeschke: On strong pseudoprimes to several bases, Math. Comp. 61 (1993), no. 204, S. 915–926.
7. ↑ Nur solche n dürfen getestet werden, die größer sind als das jeweils größte angegeben a. Für das letzte Beispiel ist die Schranke 2(ln n)² = 2239. Daran erkennt man, wie viel man durch die Verwendung der Primzahlen bis 17 einspart.
8. ↑ Prime Pages der University of Tennessee at Martin
9. ↑ Miller-Rabin SPRP bases records
10. ↑ Zhenxiang Zhang, Min Tang, "Finding strong pseudoprimes to several bases. II", Math. Comp. 72 (2003), S. 2085–2097
11. ↑ Die Folge A014233 in OEIS

Literatur

• Johannes Buchmann: Einführung in die Kryptographie. 2. Auflage. Springer, 2001, S. 108–111

Weblinks

• Eric W. Weisstein: Miller-Rabin-Test. In: MathWorld. (englisch)