Cryptography Reference
In-Depth Information
Genauere Aussagen hierzu werden wir im Satz 8.7 machen. Auch hier erhält man
mit
a
einen Zeugen für die Zusammengesetztheit von
n
, falls der Test „
n
∈
P
“
mit
a
∈{
2,...,
n
−
1
}
ausgibt. Die Zahl
a
beweist, dass
n
keine Primzahl ist.
Bemerkung
Man beachte, dass man beim Miller-Rabin-Te
st
die Elemente
a
2
d
,...,
a
2
s
−
1
d
durch sukzessives Quadrieren aus dem Element
a
d
erhält.
Beispiel
Die Zahl 561
=
·
·
17 ist eine Carmichael-Zahl und damit problematisch für
den Fermat-Test. Wir wenden nun den Miller-Rabin-Test auf die Zahl 561 an.
Es gilt 561
3
11
2
4
−
=
·
=
=
1
35, also
s
4 und
d
35. In
Z
561
gilt
2
2
2
2
2
3
2
35
2
2
·
35
·
35
·
35
=
=
=
=
263 ,
166 ,
67 ,
1.
=
Damit ist gezeigt, dass 561 keine Primzahl ist. Die Basis
a
2 ist ein Zeuge für
die Zusammengesetztheit von 561.
Wir kümmern uns nun um die Zahlen
n
, für die der Miller-Rabin-Test das Ergeb-
nis „
n
“ ausgibt. Unser Ziel ist eine Abschätzung für die Wahrscheinlichkeit,
dass der Test „
n
∈
P
∈
P
“ ausgibt, obwohl
n
gar keine Primzahl ist.
8.3.2 Starke Pseudoprimzahlen
∈
N
∈
Eine natürliche Zahl
n
heißt
starke Pseudoprimzahl
zur
Basis
a
{
1, . . . ,
n
−
1
}
, wenn
1 oder
a
2
r
d
a
d
=
±
=
−
1 für ein
r
∈{
1, . . . ,
s
−
1
}
erfüllt ist. Wir können die starken Pseudoprimzahlen auch wie folgt beschreiben:
Es sind dies jene Zahlen
n
, für die der Rabin-Miller-Test „
n
“ ausgibt (unge-
achtet dessen, ob dieses Ergebnis korrekt ist oder nicht). Nach Lemma 8.6 ist jede
Primzahl
n
eine starke Pseudoprimzahl zu jeder Basis
a
mit 1
∈
P
≤
a
≤
n
−
1. Es
folgt ein Beispiel einer starken Pseudoprimzahl, die keine Primzahl ist.
Beispiel
Wegen
,d.h.47
85
2
2
85 und 47
85
341
−
1
=
·
≡
1
(
mod 341
)
=
1
(=
·
)
ist 341
11
31
eine starke Pseudoprimzahl zur Basis 47.
Die Güte des Miller-Rabin-Tests beruht auf der Tatsache, dass es nur
wenige
star-
ke Pseudoprimzahlen gibt, die keine Primzahlen sind. Bevor wir das beweisen,
erinnern wir an den aus der linearen Algebra bekannten
Homomorphiesatz
der
Gruppentheorie, den wir für den Beweis benötigen: