Miller-Rabin-Test - LinkFang.de





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 [math]n \ge 5[/math], von der man wissen will, ob sie prim ist, und eine weitere Zahl [math]a \in \{ 2, 3, 4, \cdots, 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 zusammengesetztem [math]n[/math] ist die Ausgabe trotzdem „wahrscheinlich prim“.

Oft wird [math]a[/math] zufällig gewählt, der MRT zählt in dieser Form zur Klasse der Monte-Carlo-Algorithmen. Durch wiederholtes Testen mit verschiedenen [math]a[/math] kann man die Wahrscheinlichkeit eines Irrtums beliebig klein machen. Es gibt auch 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.[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 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,a[/math], 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 Basis a aus der Menge [math]\{ 2, 3, \cdots, n-2 \}[/math].

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

[math]n - 1 = d \cdot 2^j[/math],

und prüft dann, ob entweder

[math]a^d \equiv 1 \pmod n[/math]

oder

[math]a^{d \cdot 2^r} \equiv -1 \pmod n[/math] für ein [math]r[/math] mit [math]0 \le r \lt j[/math]

gilt. Für eine Primzahl [math]n[/math] ist dies stets der Fall. [math]n[/math] muss also zusammengesetzt sein, wenn diese Bedingung nicht erfüllt ist. Sie wird jedoch auch von einigen Zahlenpaaren [math]n,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 nennt man [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 modulo [math]n[/math] berechnet.

Ist [math]n[/math] eine Primzahl, dann gilt nach dem 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 primes [math]n[/math] ist der Vorgänger einer 1 in der Folge immer kongruent zu 1 oder zu -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 lautet dann also entweder [math](1, 1, \ldots, 1)[/math] oder [math](n-1, 1, \ldots, 1)[/math] oder [math](?, ?, \ldots, ?, n-1, 1, \ldots, 1)[/math], wobei die Fragezeichen für beliebige Zahlen stehen.

Man prüft, ob die Folge mit 1 beginnt oder [math]n-1[/math] enthält. Ist dies der Fall, ist [math]n[/math] entweder prim oder eine starke Pseudoprimzahl zur Basis [math]a[/math], und es wird „wahrscheinlich prim“ ausgegeben. In allen anderen Fällen kann [math]n[/math] nicht prim sein, und der Algorithmus gibt „zusammengesetzt“ aus. Das letzte Folgenglied [math]a^{2^jd}[/math] muss dabei nicht mehr berechnet werden, und man kann die Berechnung auch 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,\cdots,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) \gt 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. 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 die zu [math]n[/math] teilerfremden starken Pseudoprimzahlen [math]a[/math] 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 n)2) 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 [math]a \in \{2,\ldots,\min(n-1,\lfloor 2(\ln n)^2\rfloor)\}[/math] getestet werden. Die Laufzeit dieses Algorithmus ist O((log n)4).

Wenn die Zahl n klein ist, ist es nicht notwendig, alle a < 2(ln n)2 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, 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.

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

Für das letzte Beispiel ist die Schranke [math]a \lt= \lfloor 2 \cdot (\ln n)^2 \rfloor = 5857[/math]. Daran erkennt man, wie viel man einspart, indem man nur die Primzahlen bis 37 verwendet.

Siehe auch die Prime Pages[7], Miller-Rabin SPRP bases records[8], Zhang/Tang[9] und ebenso die Folge A014233[10] 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:

#include <stdint.h>
 
bool mrt (const uint32_t n, const uint32_t a) { // n ungerade, 1 < a < n-1
   const uint32_t n1 = n - 1;
   uint32_t d = n1 >> 1;
   int j = 1;
   while ((d & 1) == 0) d >>= 1, ++j;
   uint64_t t = a, p = a;
   while (d >>= 1) { //square and multiply: a^d mod n
      p = p*p % n;
      if (d & 1) t = t*p % n;
   }
   if (t == 1 || t == n1) return true; // n ist wahrscheinlich prim
   for (int k=1 ; k<j ; ++k) {
      t = t*t % n;
      if (t == n1) return true;
      if (t <= 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.

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·109, 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. Prime Pages der University of Tennessee at Martin
  8. Miller-Rabin SPRP bases records
  9. Zhenxiang Zhang, Min Tang, "Finding strong pseudoprimes to several bases. II", Math. Comp. 72 (2003), S. 2085–2097
  10. Die Folge A014233 in OEIS

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 (hier findet man vollständige Beweise)

Weblinks


Kategorien: Zahlentheoretischer Algorithmus

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Miller-Rabin-Test (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.