Miller-Rabin-Test

Der Miller-Rabin-Test oder Miller-Selfridge-Rabin-Test (kurz MRT) ist ein probabilistischer Primzahltest und damit ein Algorithmus aus dem mathematischen Teilgebiet Zahlentheorie, insbesondere der algorithmischen Zahlentheorie.

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

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

Der MRT ist nach Gary L. Miller und Michael O. Rabin benannt. 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.

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 $n$,$a$, für die der Solovay-Strassen-Test die richtige Ausgabe liefert, werden auch vom MRT richtig erkannt.

Algorithmus

Es sei $n$ eine ungerade Zahl, von der festgestellt werden soll, ob sie eine Primzahl ist. Zuerst wählt man eine Zahl $a$ aus der Menge $\{2,3,\dotsc ,n-2\}$.

Der nächste Schritt ist ein Test, den nur Primzahlen und starke Pseudoprimzahlen (zur Basis $a$) bestehen. Man berechnet $d$ (ungerade) und $j$ so, dass

$n-1=d\cdot 2^{j}$,

und prüft dann, ob entweder

$a^{d}\equiv 1{\pmod {n}}$

oder

$a^{d\cdot 2^{r}}\equiv -1{\pmod {n}}$ für ein $r$ mit $0\leq r<j$

gilt. Für eine Primzahl $n$ ist dies stets der Fall. Wenn die Bedingung nicht erfüllt ist, muss also $n$ zusammengesetzt sein. Die Bedingung wird jedoch auch von einigen Zahlenpaaren Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} ,Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} mit zusammengesetztem $n$ erfüllt, so dass der Test die Zusammengesetztheit von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} mit diesem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a } nicht zeigt. Dann heißt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} eine starke Pseudoprimzahl zur Basis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} .

Funktionsweise

Man betrachtet die Folge

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (a^d, a^{2d}, a^{4d}, \ldots, a^{2^{j-1}d}, a^{2^jd})} ,

In der jedes Element das Quadrat seines Vorgängers ist. Die Elemente werden modulo $n$ berechnet.

Ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} eine Primzahl, dann gilt nach dem kleinen fermatschen Satz

$a^{2^{j}d}=a^{n-1}\equiv 1{\pmod {n}}$

und obige Folge hat deshalb 1 als letztes Element.

Für Primzahlen $n$ ist der Vorgänger einer 1 in der Folge immer kongruent zu 1 oder zu -1:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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}}

Die Folge besteht dann also entweder nur aus Einsen, oder sie enthält Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n-1} (was sich bei modulo-n-Rechnung für einen Wert kongruent zu −1 ergibt), worauf wegen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (n-1)^2 \equiv 1} Einsen folgen. Wenn die Folge nicht diese Form hat, muss Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} zusammengesetzt sein.

Man prüft, ob die Folge mit 1 beginnt oder ob Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n-1} spätestens als vorletztes Element auftritt. Ist dies der Fall, ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} entweder prim oder eine starke Pseudoprimzahl zur Basis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} , und es wird „möglicherweise prim“ ausgegeben. Ansonsten kann $n$ nicht prim sein, und der Algorithmus gibt „zusammengesetzt“ aus. Man kann die Berechnung abbrechen, wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0} oder Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1} ohne vorhergehendes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n-1} auftritt, denn danach kann nur noch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0} bzw. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1} kommen.

Zuverlässigkeit

Ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n \ge 5} ungerade und nicht prim, so enthält die Menge $\{2,3,\ldots ,n-2\}$ höchstens ${\tfrac {n-3}{4}}$ Elemente Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{ggT}(a,n) = 1} , die keine Zeugen für die Zusammengesetztheit von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} sind. Ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g = \operatorname{ggT}(a,n) > 1} , dann wird immer Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a^x \equiv kg \pmod n} für ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k \in \mathbb{N}} sein, und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} wird als zusammengesetzt erkannt.

Ist ein zusammengesetztes ungerades Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} gegeben und wählt man zufällig ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \{2,3,\ldots,n-2\}} , dann ist somit die Wahrscheinlichkeit, dass das Ergebnis „wahrscheinlich prim“ lautet, kleiner als ${\tfrac {1}{4}}$. Wiederholt man den Test mehrfach für verschiedene voneinander unabhängig gewählte $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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 10^{-6}} .

Das ist eine pessimistische Schätzung, die von den „problematischsten“ Werten für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} ausgeht. Für die meisten zusammengesetzten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} ist der Anteil der Basen, die ein falsches Ergebnis liefern, erheblich kleiner als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tfrac{1}{4}} , 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} zusammengesetzt ist, sind die zu $n$ teilerfremden starken Pseudoprimzahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} in einer echten Untergruppe von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left(\mathbb{Z}/n\mathbb{Z}\right)^*} enthalten. Dies bedeutet, dass beim Testen aller Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} aus einer Menge, die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left(\mathbb{Z}/n\mathbb{Z}\right)^*} erzeugt, eines der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} ein Zeuge für das Zusammengesetztsein von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 im Algorithmus von Miller angeführt wurde. Die Konstante in der Landau-Notation wurde von Eric Bach auf 2 reduziert. Deshalb erhält man einen deterministischen Primzahltest, wenn alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \in \{2,\ldots,\min(n-1,\lfloor 2(\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} bis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2 (\ln n)^2} zu testen, da bekannt ist, dass eine viel kleinere Anzahl ausreichend ist. Beispielsweise wurde folgendes verifiziert:

• Wenn n < 2.047, genügt es, a = 2 zu testen,
• Wenn n < 1.373.653, genügt es, a = 2 und 3 zu testen,
• wenn n < 9.080.191, genügt es, a = 31 und 73 zu testen,
• wenn n < 4.759.123.141, genügt es, a = 2, 7, und 61 zu testen,
• wenn n < 2.152.302.898.747, genügt es, a = 2, 3, 5, 7, und 11 zu testen,
• wenn n < 3.474.749.660.383, genügt es, a = 2, 3, 5, 7, 11, und 13 zu testen,
• wenn n < 341.550.071.728.321, genügt es, a = 2, 3, 5, 7, 11, 13, und 17 zu testen,
• wenn n < 3.825.123.056.546.413.051, genügt es, a = 2, 3, 5, 7, 11, 13, 17, 19, und 23 zu testen,
• wenn n < 318.665.857.834.031.151.167.461, genügt es, a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, und 37 zu testen,
• wenn n < 3.317.044.064.679.887.385.961.981, genügt es, a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 und 41 zu testen.

Dabei dürfen nur solche Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} getestet werden, die größer sind als das jeweils größte angegebene Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} .

Für das letzte Beispiel ist die Schranke Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \le \lfloor 2 \cdot (\ln n)^2 \rfloor = 6325} . Daran ist zu erkennen, wie viel eingespart wird, indem nur die Primzahlen bis 41 verwendet werden.

Siehe auch die Prime Pages, Miller-Rabin SPRP bases records, Zhang/Tang und ebenso die Folge A014233 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^{32}} behandeln:

#include <cstdint>
using std::uint32_t;
using std::uint64_t;
bool mrt (const uint32_t n, const uint32_t a) { // n ungerade, 1 < a < n-1
   const uint32_t m = n - 1;
   uint32_t d = m >> 1, e = 1;
   while (!(d & 1)) d >>= 1, ++e;
   uint64_t p = a, q = a;
   while (d >>= 1) { // potenziere modular: p = a^d mod n
      q *= q, q %= n; // quadriere modular: q = q^2 mod n
      if (d & 1) p *= q, p %= n; // multipliziere modular: p = (p * q) mod n
   }
   if (p == 1 || p == m) return true; // n ist wahrscheinlich prim
   while (--e) {
      p *= p, p %= n;
      if (p == m) return true;
      if (p <= 1) break;
   }
   return false; // n ist nicht prim
}

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. 108–111
• Karpfinger, Kiechle: Kryptologie, Algebraische Methoden und Algorithmen. Vieweg+Teubner, 2010, S. 147–152, mit vollständigen Beweisen

Weblinks

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