Quelltext der Seite Miller-Rabin-Test

Der '''Miller-Rabin-Test''' oder '''Miller-Selfridge-Rabin-Test''' (kurz MRT) ist ein [[Randomisierter Algorithmus|probabilistischer]] [[Primzahltest]] und damit ein [[Algorithmus]] aus dem [[Teilgebiete der Mathematik|mathematischen Teilgebiet]] [[Zahlentheorie]], insbesondere der [[Algorithmische Zahlentheorie|algorithmischen Zahlentheorie]].

Der MRT erhält als Eingabe eine [[Parität (Mathematik)|ungerade]] [[natürliche Zahl]] <math>n \ge 5</math>, von der man wissen will, ob sie prim ist, und eine weitere Zahl <math>a \in \{ 2, 3, 4, \dotsc, n-2 \}</math> und gibt entweder „zusammengesetzt“ oder „wahrscheinlich prim“ aus. Ist <math>n</math> prim, so lautet die Ausgabe immer „wahrscheinlich prim“. Anderenfalls wird in den meisten Fällen „zusammengesetzt“ ausgegeben, aber für manche Paare <math>n,a</math> mit [[Zusammengesetzte Zahl|zusammengesetztem]] <math>n</math> ist die Ausgabe trotzdem „wahrscheinlich prim“.

Oft wird <math>a</math> [[Zufallszahl|zufällig]] gewählt, der MRT zählt in dieser Form zur Klasse der [[Monte-Carlo-Algorithmus|Monte-Carlo-Algorithmen]]. Durch wiederholtes Testen mit verschiedenen <math>a</math> kann die Wahrscheinlichkeit eines Irrtums beliebig klein gehalten werden. Es gibt [[#Deterministische Varianten|deterministische Varianten]] des MRT, bei denen durch geeignete Wahl der <math>a</math> ein Irrtum ausgeschlossen wird.

Der MRT ist nach [[Gary L. Miller]] und [[Michael O. Rabin]] benannt.<ref>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</ref> [[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.<ref name="YAN">Song Y. Yan: ''Number theory for computing.'' 2. Auflage. Springer, 2002, S. 208–214</ref>

Der MRT funktioniert ähnlich wie der [[Solovay-Strassen-Test]], ist diesem allerdings in allen Aspekten überlegen. Er ist schneller, seine Irrtumswahrscheinlichkeit ist geringer, und alle Paare <math>n</math>,<math>a</math>, für die der Solovay-Strassen-Test die richtige Ausgabe liefert, werden auch vom MRT richtig erkannt.

== Algorithmus ==
Es sei <math>n</math> eine [[ungerade Zahl]], von der festgestellt werden soll, ob sie eine Primzahl ist. Zuerst berechnet man <math>j</math> und <math>d</math> (ungerade) so, dass
: <math>n - 1 = 2^j\cdot d</math>.

Dann wählt man eine Zahl <math>a</math> aus der Menge <math>\{ 2, 3, \dotsc, n-2 \}</math>.
Der nächste Schritt ist ein Test, den nur Primzahlen und [[starke Pseudoprimzahl]]en (zur Basis <math>a</math>) bestehen: Man prüft, ob entweder
: <math>a^d \equiv 1 \pmod n</math>
oder
: <math>a^{2^r\cdot d} \equiv -1 \pmod n</math> <span style="margin-left:2em;"> für ein <math>r</math> mit <math>0 \le r < j</math></span>
gilt. Für eine Primzahl <math>n</math> ist dies stets der Fall.
Wenn die Bedingung nicht erfüllt ist, muss also <math>n</math> zusammengesetzt sein. Die Bedingung wird jedoch auch von einigen Zahlenpaaren <math>n</math>,<math>a</math> mit zusammengesetztem <math>n</math> erfüllt, so dass der Test die Zusammengesetztheit von <math>n</math> mit diesem <math>a </math> nicht zeigt. Dann heißt <math>n</math> eine ''starke Pseudoprimzahl zur Basis <math>a</math>''.

== Funktionsweise ==
Man betrachtet die Folge
: <math>(a^d, a^{2d}, a^{4d}, \ldots, a^{2^{j-1}d}, a^{2^jd})</math>,
In der jedes Element das Quadrat seines Vorgängers ist. Die Elemente werden [[Division mit Rest#Modulo|modulo]] <math>n</math> berechnet.

Ist <math>n</math> eine Primzahl, dann gilt nach dem [[Kleiner fermatscher Satz|kleinen fermatschen Satz]]
: <math>a^{2^jd} = a^{n-1} \equiv 1 \pmod n</math>
und obige Folge hat deshalb 1 als letztes Element.

Für Primzahlen <math>n</math> ist der Vorgänger einer 1 in der Folge immer kongruent zu 1 oder zu &minus;1:
: <math>\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}</math>
Die Folge besteht dann also entweder nur aus Einsen, oder sie enthält <math>n-1</math> (was sich bei modulo-n-Rechnung für einen Wert kongruent zu −1 ergibt), worauf wegen <math>(n-1)^2 \equiv 1</math> Einsen folgen. Wenn die Folge nicht diese Form hat, muss <math>n</math> zusammengesetzt sein.

Man prüft, ob die Folge mit 1 beginnt oder ob <math>n-1</math> spätestens als vorletztes Element auftritt. Ist dies der Fall, ist <math>n</math> entweder prim oder eine starke Pseudoprimzahl zur Basis <math>a</math>, und es wird „möglicherweise prim“ ausgegeben. Ansonsten kann <math>n</math> nicht prim sein, und der Algorithmus gibt „zusammengesetzt“ aus. Man kann die Berechnung abbrechen, wenn <math>0</math> oder <math>1</math> ohne vorhergehendes <math>n-1</math> auftritt, denn danach kann nur noch <math>0</math> bzw. <math>1</math> kommen.

== Zuverlässigkeit ==
Ist <math>n \ge 5</math> ungerade und nicht prim, so enthält die Menge <math>\{2,3,\ldots,n-2\}</math> höchstens <math>\tfrac{n-3}{4}</math> Elemente <math>a</math> mit <math>\operatorname{ggT}(a,n) = 1</math>, die keine Zeugen für die Zusammengesetztheit von <math>n</math> sind. Ist <math>g = \operatorname{ggT}(a,n) > 1</math>, dann wird immer <math>a^x \equiv kg \pmod n</math> für ein <math>k \in \mathbb{N}</math> sein, und <math>n</math> wird als zusammengesetzt erkannt.

Ist ein zusammengesetztes ungerades <math>n</math> gegeben und wählt man zufällig ein <math>a</math> aus <math>\{2,3,\ldots,n-2\}</math>, dann ist somit die [[Wahrscheinlichkeit]], dass das Ergebnis „wahrscheinlich prim“ lautet, kleiner als <math>\tfrac{1}{4}</math>.
Wiederholt man den Test mehrfach für verschiedene voneinander unabhängig gewählte <math>a</math> aus dieser Menge, sinkt die Wahrscheinlichkeit weiter ab. Nach <math>s</math> Schritten ist die Wahrscheinlichkeit, eine zusammengesetzte Zahl für prim zu halten, kleiner als <math>(\tfrac{1}{4})^s</math>, also z.&nbsp;B. nach vier Schritten kleiner als 0,4 % und nach zehn Schritten kleiner als <math>10^{-6}</math>.

Das ist eine pessimistische Schätzung, die von den „problematischsten“ Werten für <math>n</math> ausgeht. Für die meisten zusammengesetzten <math>n</math> ist der Anteil der Basen, die ein falsches Ergebnis liefern, erheblich kleiner als <math>\tfrac{1}{4}</math>, und für viele ist er sogar 0.

== 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 <math>n</math> zusammengesetzt ist, sind diejenigen zu <math>n</math> teilerfremden Zahlen <math>a</math>, die keine Zeugen für die Zusammengesetztheit von n sind, in einer echten [[Untergruppe]] von <math>\left(\mathbb{Z}/n\mathbb{Z}\right)^*</math> enthalten. Dies bedeutet, dass beim Testen aller <math>a</math> aus einer Menge, die <math>\left(\mathbb{Z}/n\mathbb{Z}\right)^*</math> erzeugt, eines der <math>a</math> ein Zeuge für das Zusammengesetztsein von <math>n</math> ist. Wenn angenommen wird, dass die [[Riemannsche Vermutung]] wahr ist, dann folgt daraus, dass die Gruppe durch ihre Elemente kleiner O((log&nbsp;''n'')<sup>2</sup>) generiert wird, was bereits im [[Algorithmus von Miller]] angeführt wurde.<ref name="miller">Gary L. Miller: ''Riemann’s Hypothesis and Tests for Primality.'' In: ''Journal of Computer and System Sciences'' 13 (1976), no. 3, pp. 300–317.</ref> Die Konstante in der [[Landau-Symbole|Landau-Notation]] wurde von Eric Bach auf 2 reduziert.<ref>Eric Bach: ''Explicit bounds for primality testing and related problems'', Mathematics of Computation 55 (1990), no. 191, pp. 355–380.</ref>
Deshalb erhält man einen deterministischen Primzahltest, wenn alle <math>a \in \{2,\ldots,\min(n-1,\lfloor 2(\ln n)^2\rfloor)\}</math> getestet werden. Die Laufzeit dieses Algorithmus ist O((log&nbsp;''n'')<sup>4</sup>).

Wenn die Zahl <math>n</math> klein ist, ist es nicht notwendig, alle <math>a</math> bis <math>2 (\ln n)^2</math> zu testen, da bekannt ist, dass eine viel kleinere Anzahl ausreichend ist. 

Beispielsweise wurde folgendes verifiziert:
{| class="wikitable"
! ''n'' kleiner als || zu testende ''a'' || Quelle
|-
| align="right" | 2.047 || 2 || rowspan="2" | <ref name="Pomerance80" details="1023">{{Literatur
 | Autor = [[Carl Pomerance]], [[John L. Selfridge]], [[Samuel Wagstaff]]
 | Titel = The pseudoprimes to 25·10⁹
 | Sprache = en
 | Sammelwerk = [[Mathematics of Computation]]
 | Band = 35
 | Datum = 1980
 | Seiten = 1003-1026
 | DOI = 10.1090/S0025-5718-1980-0572872-7
}}</ref>
|-
| align="right" | 1.373.653 || 2, 3 
|-
| align="right" | 9.080.191 || 31, 73 || rowspan="2" |<ref name="Jaeschke93" details="926">{{Literatur
 | Autor = Gerhard Jaeschke
 | Titel = On strong pseudoprimes to several bases
 | Sprache = en
 | Sammelwerk = [[Mathematics of Computation]]
 | Band = 61
 | Datum = 1993
 | Seiten = 915-926
 | DOI = 10.2307/2153262
}}</ref>
|-
| align="right" | 4.759.123.141 ||  2, 7, 61 
|-
| align="right" | 2.152.302.898.747 || 2, 3, 5, 7, 11 || rowspan="3" | <ref name="Jaeschke93" details="916"/>
|-
| align="right" | 3.474.749.660.383 || 2, 3, 5, 7, 11, 13  
|-
| align="right" | 341.550.071.728.321 || 2, 3, 5, 7, 11, 13, 17 
|-
| align="right" | 3.825.123.056.546.413.051 || 2, 3, 5, 7, 11, 13, 17, 19, 23 || <ref name="Jiang14">{{Literatur
 | Autor = Yupeng Jiang and Yingpu Deng
 | Titel = Strong pseudoprimes to the first eight prime bases
 | Sprache = en
 | Sammelwerk = [[Mathematics of Computation]]
 | Band = 83
 | Datum = 2014
 | Seiten = 2915-2924
 | DOI = 10.1090/S0025-5718-2014-02830-5
}}</ref>
|-
| align="right" | 318.665.857.834.031.151.167.461 || 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 || rowspan="2" | <ref name="Sorenson17">{{Literatur
 | Autor = Jonathan Sorenson, Jonathan Webster
 | Titel = Strong pseudoprimes to twelve prime bases
 | Sprache = en
 | Sammelwerk = [[Mathematics of Computation]]
 | Band = 86
 | Datum = 2017
 | Seiten = 985-1003
 | DOI = 10.1090/mcom/3134
 | arXiv = math/1509.00864
}}</ref>
|-
| align="right" | 3.317.044.064.679.887.385.961.981 || 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41  
|}

Dabei dürfen nur solche <math>n</math> getestet werden, die größer sind als das jeweils größte angegebene <math>a</math>.

Für das letzte Beispiel ist die Schranke <math>a \le \lfloor 2 \cdot (\ln n)^2 \rfloor = 6325</math>. Daran ist zu erkennen, wie viel eingespart wird, indem nur die Primzahlen bis 41 verwendet werden.

Siehe auch die Prime Pages,<ref>[https://primes.utm.edu/prove/prove2_3.html Prime Pages] der ''University of Tennessee at Martin''</ref> Miller-Rabin SPRP bases records,<ref>[http://miller-rabin.appspot.com/ Miller-Rabin SPRP bases records]</ref> Zhang/Tang<ref>Zhenxiang Zhang, Min Tang: ''Finding strong pseudoprimes to several bases. II.'' In: ''Math. Comp.'' 72 (2003), S. 2085–2097</ref> und ebenso die Folge A014233<ref>Die Folge [https://oeis.org/A014233 A014233] in [[OEIS]]</ref> 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.

== Implementierung ==

Diese [[C++]]-Implementierung kann alle Zahlen kleiner <math>2^{32}</math> behandeln:

<syntaxhighlight lang="c++">
#include <cstdint>

using u32 = std::uint32_t;
using u64 = std::uint64_t;

bool wahrscheinlich_prim(const u32 n, const u32 a)  // n ungerade, 2 <= a <= n-2
{
    u32 d = (n-1) / 2, j = 1;
    while (d % 2 == 0) 
        d /= 2, ++j;

    // berechne p = a^d mod n mit der binären Exponentiation:
    u64 p = a, q = a;
    while (d /= 2) {
        q = q * q % n;
        if (d % 2) p = p * q % n;
    }

    if (p == 1 || p == n-1)
        return true;  // n ist wahrscheinlich prim

    while (--j > 0 && p > 1) {
        p = p * p % n;
        if (p == n-1) return true;
    }
    return false;  // n ist nicht prim
}
</syntaxhighlight>

== 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.

== Literatur ==
* [[Johannes Buchmann]]: ''Einführung in die Kryptographie.'' 2. Auflage. Springer, 2001, S.&nbsp;108–111
* Karpfinger, Kiechle: ''Kryptologie, Algebraische Methoden und Algorithmen.'' Vieweg+Teubner, 2010, S.&nbsp;147–152, mit vollständigen Beweisen

== Weblinks ==
* {{MathWorld |id=Rabin-MillerStrongPseudoprimeTest |title=Miller-Rabin-Test}}

== Einzelnachweise ==
<references />

[[Kategorie:Zahlentheoretischer Algorithmus]]