Cryptography Reference
In-Depth Information
Da
n
ungerade ist, gilt
s
1.
Beim Fermat-Test haben wir ausgenutzt, dass für eine Primzahl
n
und jedes
a
≥
∈
die Kongruenz
a
n
−
1
erfüllt ist. Beim
Miller-Rabin-
Test
werden wir ausnutzen, dass für eine Primzahl die folgende Tatsache gilt:
{
1,,...,
n
−
1
}
≡
1
(
mod
n
)
Lemma 8.6
Es sei n eine Primzahl. Ist a
∈{
1, . . . ,
n
−
1
}
, so gilt entweder
a
d
(
i
)
≡
1
(
mod
n
)
oder
a
2
r
d
(
)
≡−
(
)
∈{
−
}
ii
1
mod
n
für ein r
0, . . . ,
s
1
.
|
Z
n
|
=
2
s
d
. Der Satz 6.9 von Euler
Beweis.
Weil
n
ei
ne Primzahl ist, gilt
n
−
1
=
2
s
a
d
Z
n
. Wegen (iii) in Lemma 6.1 (b) ist
o
a
d
ein Teiler von 2
s
.Es
(
)
=
(
)
liefert
1in
a
d
2
l
mit
l
gelte etwa
o
(
)=
∈{
0, . . . ,
s
}
.
=
0: Dann gilt
a
d
≡
(
)
1.Fall: l
1
mod
n
, d. h., es gilt (i).
2
l
−
1
a
d
<
≤
(
)
−
2.Fall:
0
l
s
: Dann hat
die Ordnung
2
. Da
1 das einzige Element
Z
n
v
on der Ordnung 2 ist (das Polynom
X
2
in
−
1
∈
Z
n
[
X
]
hat im Falle
n
∈
P
2
l
−
1
a
d
±
(
)
≡−
(
)
nur
1 als Nullstellen), gilt also in diesem Fall
1
mod
n
. Setze nu
n
r
:
=
l
−
1. Damit gilt (ii).
Wegen dieses Lemmas können wir nun die folgende Aussage formulieren:
,
a
2
r
d
Gilt
a
d
≡±
1
(
mod
n
)
≡−
1
(
mod
n
)
≤
≤
−
<
<
für alle 1
r
s
1 und ein 1
a
n
,
so ist
n
garantiert zusammengesetzt.
Hiermit gewinnen wir den (probabilistischen)
Miller-Rabin-Test
:
∈{
−
}
Wähle ein
a
2, . . . ,
n
1
.
Z
n
die
s
Potenzen
a
d
,
a
2
d
,...,
a
2
s
−
1
d
.
Bestimme in
Gilt
1,...,
a
2
s
−
1
d
a
d
1,
a
2
d
=
±
=
−
=
−
1,
∈
P
so ist
n
keine Primzahl, gib „
n
“ aus.
Gilt
1 oder
a
2
r
d
a
d
=
±
=
−
1 für ein
r
∈{
1, . . . ,
s
−
1
}
,
∈
P
so ist
n
eventuell eine Primzahl, gib „
n
“ aus (oder wiederhole das Verfah-
ren mit einem neuen
a
).
∈
P
Wie beim Fermat-Test, ist es durchaus möglich, dass der Test „
n
“ ausgibt,
obwohl
n
gar keine Primzahl ist. Gibt der Test aber „
n
“ für
viele
verschiede-
ne
a
aus, so ist die Wahrscheinlichkeit dafür, dass
n
eine Primzahl ist,
sehr groß
.
∈
P
