Verfahren

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

  • Wähle a{1,,n1} zufällig. Falls ggT(a,n)>1 gilt, dann gib „n nicht prim“ aus.

  • Wenn an1n1, dann gib „n wahrscheinlich prim“ aus, ansonsten „n nicht prim“.

Der Test basiert auf dem kleinen Satz von Fermat: Für ggT(a,n)=1 und n prim gilt an1n1. Ist die Kongruenz also nicht erfüllt, kann n nicht prim sein.

Carmichael-Zahl:
Eine Zahl nN heißt Carmichael-Zahl, falls n zusammengesetzt ist und a(Z/nZ)an1n1.

Es gibt unendlich vieler solcher Zahlen, die kleinste ist 561=31117. Bei bestimmten n gibt also der Fermat-Test immer „n wahrscheinlich prim“ aus, obwohl n nicht prim ist (wenn der Test nicht zufällig einen nicht-trivialen Teiler a von n 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 nN ungerade mit n3.

  • Schreibe n1=2u mit uN ungerade und N.

  • Wähle a{1,,n1} zufällig. Falls ggT(a,n)>1 gilt, dann gib „n nicht prim“ aus.
    Sonst berechne b:=aumodn.

  • Wenn b=1 ist, dann gib „n wahrscheinlich prim“ aus.

  • Sonst berechne die Folge (b,b2,b22,,b21) in Z/nZ.

  • Falls 1 in dieser Folge vorkommt, dann gib „n wahrscheinlich prim“ aus, ansonst gib „n nicht prim“ aus.

Der Miller-Rabin-Test ist gewissermaßen eine Verallgemeinerung des Fermat-Tests: Wenn der MR-Test „n wahrscheinlich prim“ ausgibt, dann gibt der Fermat-Test dies auch aus (wenn der Fermat-Test „n nicht prim“ ausgibt, dann ist ggT(a,n)>1 oder an1n1). Die Umkehrung gilt allerdings nicht, d. h. der MR-Test erkennt mehr zusammengesetzte Zahlen sicher als solche.

Korrektheit

Satz (Korrektheit des MR-Tests):
Wenn der MR-Test „n nicht prim“ ausgibt, dann ist n nicht prim.

Beweis: Sei n3 prim. Dann gibt es kein a{1,,n1} mit ggT(a,n)>1, d. h. in Schritt (2) wird nichts ausgegeben. Sei also a(Z/nZ) beliebig. Ist b:=aumodn=1, dann gibt der Test „n wahrscheinlich prim“ aus.

Sei also b1. Es gilt an1n1 nach dem kleinen Satz von Fermat (weil n prim), also 1na2unb2. Daher gilt b21n±1 (Z/nZ Körper wegen n prim).
Ist b21n1, dann gibt der Test „n wahrscheinlich prim“ aus. Sonst ist b21n1 und man kann die Argumentation wiederholen. Der Test gibt also „n wahrscheinlich prim“ aus oder es gilt b2nb21nnbn1, ein Widerspruch zur Annahme b1. Somit gibt der Algorithmus in jedem Fall „n wahrscheinlich prim“ aus.   ƒ

Zuverlässigkeit

Im Folgenden wird gezeigt, dass für n zusammengesetzt die Wahrscheinlichkeit, dass ein a gewählt wird, sodass „n wahrscheinlich prim“ ausgegeben wird, höchstens 50 % ist (in Wahrheit ist diese Fehlerwahrscheinlichkeit sogar höchstens 25 %). Bei m Iterationen des Algorithmus ist deswegen die Fehlerwahrscheinlichkeit höchstens 12m. Andersherum ist die Wahrscheinlichkeit, dass n prim ist, wenn m-mal „n wahrscheinlich prim“ ausgegeben wurde, mindestens 112m.

Lemma: Seien p3 prim und d2. Dann gilt (pd1+1)pd1±1(modpd).

Beweis: Im Folgenden wird immer modulo pd gerechnet.

Nach dem Binomischen Lehrsatz gilt (pd1+1)pd1=kN0(pd1k)p(d1)k. Für k2 ist (d1)kd, weil k2dd1 wegen d2. Damit gilt pdp(d1)k für k2, d. h. p(d1)k0 und alle Summanden für k2 verschwinden modulo pd.

Daher gilt (pd1+1)pd1=1+(pd1)pd11+(01)pd1=1pd1.
Wäre 1pd11, so würde pd10 gelten, also pdpd1, ein Widerspruch.
Wäre 1pd11, so würde pd12 gelten, also pd(pd12), ein Widerspruch.   ƒ

Insbesondere ist pd für p3 und d2 keine Carmichael-Zahl, weil dann pd zusammengesetzt ist und ggT(pd1+1,pd)=1 gilt.

Satz: Seien n3 ungerade und zusammengesetzt, uN ungerade und N.
Definiere G:={a(Z/nZ)|a2un1} und H:={aG|a21un±1} mit
:=min{kN0|aGa2kun1}. Dann gilt H<G<(Z/nZ) mit H(Z/nZ).

Beweis: Zunächst ist >0, da 1G (wegen 1) und a2ku=(1)u=1n1 für a=1G und k=0 (wegen u ungerade und n2). Außerdem ist , weil aGa2kun1 für k=. (Damit ist {1,,} tatsächlich endlich.)

Es gilt G<(Z/nZ), weil 1G, (ab)2u=a2ub2un1 und (a1)2u=(a2u)1n1 für a,bG. Analog ist H<G, weil 1H, (ab)21u=a21ub21un(±1)2=1 und (a1)21u=(a21u)1n(±1)1=±1 für a,bG.

Für G(Z/nZ) ist nichts zu zeigen. Sei also G=(Z/nZ). Wegen der Minimalität von existiert ein aG mit a21un1. Schreibe n=rs mit r,s3 und ggT(r,s)=1. Nach dem chin. Restsatz kann a21u1 nicht gleichzeitig modulo r und modulo s gelten. Sei also oBdA a21ur1. Wähle ein c(Z/nZ) mit cra und cs1 (existiert nach dem chin. Restsatz). Dann gilt cG=(Z/nZ), aber cH:

Wäre c21un1, dann a21urc21ur1 (wegen cra), Widerspruch zu a21ur1.
Wäre c21un1, dann 1sc21us1 (wegen cs1), was nur für s=2 gehen würde.

Damit gilt HG=(Z/nZ).   ƒ

Seien uN ungerade und N ab jetzt wieder so gewählt, dass n1=2u.

Lemma: Seien n3 ungerade und a(Z/nZ).
Wenn aH gilt, dann gibt der MR-Test „n nicht prim“ aus.

Beweis: Sei b:=aumodn. Wäre b=1, dann wäre a21u=b21=1, d. h. aH, ein Widerspruch zur Voraussetzung. Daher gilt b1 und in Schritt (3) wird nichts ausgegeben.

Ist 1{b,b2,b22,,b21} modulo n, dann gilt aG, da dann a2u=(au)2nb2n1. Damit gilt aGH und b21n±1. Daraus folgt b2kn1 für alle k{0,,1}. Nach Def. von gilt außerdem b2n1. Daraus folgt b2kn1 für alle k{,,1}. In jedem Fall gilt b2kn1 für alle k{0,,1}.

Ist 1{b,b2,b22,,b21} modulo n, dann ist b2kn1 für k{0,,2}. Zusätzlich gilt b21n1, da sonst aG (wegen a2un(b21)2n(1)2=1) und man wie eben argumentieren kann.

Es gilt also immer, dass 1 nicht in der Folge (b,b2,b22,,b21) in Z/nZ vorkommt. Damit gibt der Algorithmus „n nicht prim“ aus.   ƒ

Satz (Zuverlässigkeit des MR-Tests): Sei n3 ungerade und zusammengesetzt.
Dann liefert der MR-Test bei mindestens der Hälfte aller a(Z/nZ)n nicht prim“.

Beweis: Seien n1=2u und G und H wie im obigen Satz. Nach demselben Satz gilt H(Z/nZ), d. h. [(Z/nZ):H]2. Für mindestens der Hälfte aller a(Z/nZ) gilt daher aH. Nach obigem Lemma gibt der MR-Test für diese an nicht prim“ aus.   ƒ

Faktorisierung: Gilt b2kn1 für ein k{1,,1}, dann kommt nach dem Beweis des letzten Lemmas keine 1 in der Folge vor und man kann n sogar faktorisieren.
Sei dazu c:=(b2k1modn)1 mit b2kn1. Dann gilt c2n1 sowie cn±1, d. h. (c1)(c+1)n0 bzw. n(c1)(c+1), aber n(c1) und n(c+1).
Damit folgt 1<ggT(c1,n),ggT(c+1,n)<n.