Cryptography Reference
In-Depth Information
Algorithmus 6.4 Der Miller-Rabin-Primzahltest
MillerRabin(
n
)
Vorbedingung:
n ≥
3
,ungerade
1.
Trenne Zweierpotenzen von
n −
1
ab.
wähle
m
ungerade und
l
derart, dass
n −
1=2
l
· m
2.
Wähle potentielle Artjunov-Zeugen zufällig.
a
=
flip
(
)
3.
Bestimme und teste erstes Glied der Artjunov-Folge.
b
=
a
m
rmod
n
falls
b ∈{−
{
2
,...,n−
2
}
,so
gib »
n
ist prim« aus
4.
Bestimme und teste die anderen Glieder der Artjunov-Folge.
für
i
=0
bis
l −
1
,
1
}
2
b
=
b
2
rmod
n
falls
b
=
1
,so
gib »
n
ist prim« aus
falls
b
=1
,so
gib »
n
ist zusammengesetzt« aus
5.
Fange restliche Fälle auf.
gib »
n
ist zusammengesetzt« zurück
Nachbedingung:
n
ist Primzahl und die Ausgabe ist »
n
ist prim«. Oder: »
n
ist zusammen-
gesetzt« und die Wahrscheinlichkeit, dass »
n
ist prim« ausgegeben wird, ist
−
≤
1
/
4
.
Die Wahrscheinlichkeit auf eine Zahl
a
zu stoßen, welche Bedingung 1.
erfüllt, ist also
4
/
(
n −
1)
, und damit verschwindend gering.
Einzeln betrachtet taugen Bedingung 1. und 2. aus Lemma 6.3.7 also letztlich doch
nicht für einen Primzahltest. Glücklicherweise kann man die beiden Bedingungen ge-
schickt kombinieren, um einen guten Primzahltest zu erhalten. Dies führt uns zum
Miller-
Rabin-Primzahltest
(siehe Algorithmus 6.4), der in der Praxis eingesetzt wird und den
wir nun näher erläutern.
Beim Miller-Rabin-Primzahltest betrachtet man zu einem
a
∈{
1
,...,n
−
1
}
∈{
2
,...,n
−
2
}
die so-
genannte
Artjunov-Folge
b
0
,...,b
l−
1
mit
b
i
=(
a
m
)
2
i
rmod
n
und
n
2
l
für
m
−
1=
m
·
1
. Insbesondere gilt
b
i
=
b
i−
1
ungerade und
l
≥
rmod
n
für alle
i
∈{
1
,...,l
−
1
}
und
b
l−
1
mod
n
=
a
n−
1
mod
n
.
Ist
b
0
∈{
, dann gilt
b
1
=
b
0
1
.
In diesem Fall stößt man mit der Artjunov-Folge also auf kein Element, das Bedingung
1. oder 2. aus Lemma 6.3.7 erfüllen würde. Im Miller-Rabin-Primzahltest wird deshalb
»
n
ist prim« ausgegeben (siehe Algorithmus 6.4, 3.).
Ist dagegen
b
0
/∈{
1
, −
1
}
1
,
−
1
}
rmod
n
=1
. Folglich gilt
b
i
=1
für alle
i
≥
, so schauen wir die Elemente
b
1
,...,b
l−
1
nacheinander an.
Treffen wir auf
1
, dann sind alle folgenden Zahlen
1
. Wir sind also wieder nicht auf ein
Element gestoßen, das Bedingung 1. oder 2. erfüllen würde. Im Miller-Rabin-Primzahltest
wird deshalb »
n
ist prim« ausgegeben (siehe Algorithmus 6.4, 4.). Treffen wir aber auf
1
,
ohne vorher
−
1
gesehen zu haben, dann haben wir ein Element gefunden, das Bedingung
1. erfüllt. Es wird deshalb »
n
ist zusammengesetzt« ausgegeben (siehe Algorithmus 6.4,
4.). Tauchen beide Fälle bis zum Schluss nicht auf, so ist
b
l−
1
/
−
und
b
l−
1
mod
n
=
∈{
1
,
−
1
}
