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:
 
Search WWH ::




Custom Search