\(\newcommand {\LATEXunderbrace }[1]{\underbrace {#1}}\)
\(\newcommand {\LATEXoverbrace }[1]{\overbrace {#1}}\)
Der Miller-Rabin-Test ist ein probabilistischer Primzahltest. Wenn der Algorithmus ausgibt, dass die Zahl zusammengesetzt ist, dann stimmt das auch, allerdings stimmt die Ausgabe „wahrscheinlich prim“ nur zu
50 %. Der Miller-Rabin-Test baut auf dem Fermat-Test auf.
Fermat-Test: Der Fermat-Test ist ein probabilistischer Primzahltest und läuft wie folgt ab.
Gegeben sei .
Wähle zufällig. Falls gilt, dann gib „ nicht prim“ aus.
Wenn , dann gib „ wahrscheinlich prim“ aus, ansonsten „ nicht prim“.
Der Test basiert auf dem kleinen Satz von Fermat: Für und prim gilt . Ist die Kongruenz also nicht erfüllt, kann nicht prim sein.
Carmichael-Zahl:
Eine Zahl heißt Carmichael-Zahl, falls zusammengesetzt ist und .
Es gibt unendlich vieler solcher Zahlen, die kleinste ist . Bei bestimmten gibt also der Fermat-Test immer „ wahrscheinlich prim“ aus, obwohl nicht prim ist (wenn der Test nicht
zufällig einen nicht-trivialen Teiler von erwischt). Daher ist der Fermat-Test als Primzahltest ungeeignet.
Miller-Rabin-Test: Der Miller-Rabin-Test
(MR-Test) ist ein probabilistischer Primzahltest und läuft wie folgt ab. Gegeben sei ungerade mit .
Schreibe mit ungerade und .
Wähle zufällig. Falls gilt, dann gib „ nicht prim“ aus.
Sonst berechne .
Wenn ist, dann gib „ wahrscheinlich prim“ aus.
Sonst berechne die Folge in .
Falls in dieser Folge vorkommt, dann gib „ wahrscheinlich prim“ aus, ansonst gib „ nicht prim“ aus.
Der Miller-Rabin-Test ist gewissermaßen eine Verallgemeinerung des Fermat-Tests: Wenn der MR-Test „ wahrscheinlich prim“ ausgibt, dann gibt der Fermat-Test dies auch aus (wenn der Fermat-Test „ nicht prim“ ausgibt,
dann ist oder ). Die Umkehrung gilt allerdings nicht, d. h. der MR-Test erkennt mehr zusammengesetzte Zahlen sicher als solche.
Satz (Korrektheit des MR-Tests):
Wenn der MR-Test „ nicht prim“ ausgibt, dann ist nicht prim.
Beweis: Sei prim. Dann gibt es kein mit , d. h. in Schritt (2) wird nichts ausgegeben. Sei also
beliebig. Ist , dann gibt der Test „ wahrscheinlich prim“ aus.
Sei also . Es gilt nach dem kleinen Satz von Fermat (weil prim), also . Daher gilt
( Körper wegen prim).
Ist , dann gibt der Test „ wahrscheinlich prim“ aus. Sonst ist und man kann die Argumentation wiederholen. Der Test gibt also „ wahrscheinlich
prim“ aus oder es gilt , ein Widerspruch zur Annahme . Somit gibt der Algorithmus in jedem Fall „
wahrscheinlich prim“ aus.
Im Folgenden wird gezeigt, dass für zusammengesetzt die Wahrscheinlichkeit, dass ein gewählt wird, sodass „ wahrscheinlich prim“ ausgegeben wird, höchstens 50 % ist (in
Wahrheit ist diese Fehlerwahrscheinlichkeit sogar höchstens 25 %). Bei Iterationen des Algorithmus ist deswegen die Fehlerwahrscheinlichkeit höchstens . Andersherum ist die
Wahrscheinlichkeit, dass prim ist, wenn -mal „ wahrscheinlich prim“ ausgegeben wurde, mindestens .
Lemma: Seien prim und . Dann gilt .
Beweis: Im Folgenden wird immer modulo gerechnet.
Nach dem Binomischen Lehrsatz gilt . Für ist , weil
wegen . Damit gilt für , d. h. und alle Summanden für verschwinden modulo .
Daher gilt .
Wäre , so würde gelten, also , ein Widerspruch.
Wäre , so würde gelten, also , ein Widerspruch.
Insbesondere ist für und keine Carmichael-Zahl, weil dann zusammengesetzt ist und gilt.
Satz: Seien ungerade und zusammengesetzt, ungerade und .
Definiere und mit
. Dann gilt mit .
Beweis: Zunächst ist , da (wegen ) und für und (wegen
ungerade und ). Außerdem ist , weil für . (Damit ist
tatsächlich endlich.)
Es gilt , weil , und für .
Analog ist , weil , und für .
Für ist nichts zu zeigen. Sei also . Wegen der Minimalität von existiert ein mit .
Schreibe mit und . Nach dem chin. Restsatz kann nicht gleichzeitig modulo und modulo gelten. Sei also oBdA . Wähle ein mit und (existiert nach dem chin. Restsatz). Dann gilt , aber :
Wäre , dann (wegen ), Widerspruch zu .
Wäre , dann (wegen ), was nur für gehen würde.
Damit gilt .
Seien ungerade und ab jetzt wieder so gewählt, dass .
Lemma: Seien ungerade und .
Wenn gilt, dann gibt der MR-Test „ nicht prim“ aus.
Beweis: Sei . Wäre , dann wäre , d. h. , ein Widerspruch zur Voraussetzung. Daher gilt und in Schritt (3) wird nichts ausgegeben.
Ist modulo , dann gilt , da dann . Damit gilt und . Daraus folgt für alle . Nach Def. von gilt
außerdem . Daraus folgt für alle . In jedem Fall gilt für alle .
Ist modulo , dann ist für . Zusätzlich gilt , da sonst (wegen ) und man wie eben argumentieren kann.
Es gilt also immer, dass nicht in der Folge in vorkommt. Damit gibt der Algorithmus „ nicht prim“ aus.
Satz (Zuverlässigkeit des MR-Tests): Sei ungerade und zusammengesetzt.
Dann liefert der MR-Test bei mindestens der Hälfte aller „ nicht prim“.
Beweis: Seien und und wie im obigen Satz. Nach demselben Satz gilt , d. h. . Für mindestens der
Hälfte aller gilt daher . Nach obigem Lemma gibt der MR-Test für diese „ nicht prim“ aus.
Faktorisierung: Gilt für ein , dann kommt nach dem Beweis des letzten Lemmas keine in der Folge vor und man kann sogar
faktorisieren.
Sei dazu mit . Dann gilt sowie , d. h. bzw. , aber und .
Damit folgt .