Cryptography Reference
In-Depth Information
für Primzahlen, wie sie etwa beim RSA-Verfahren benutzt werden, obwohl der
Test
nur
probabilistisch ist. Der Miller-Rabin-Test ist nämlich deutlich schneller
als der AKS-Test, und die Fehlerwahrscheinlichkeit von 4
−
k
nach
k
Iterationen ist
nach hinreichend vielen Iterationen genügend klein. Der
AKS-Test
hat eine sehr
wichtige theoretische Bedeutung: Es gibt einen deterministischen Primzahltest
mit polynomialer Laufzeit. In der Sprache von Kapitel 4 heißt das: Das mathema-
tische Problem „
prüfe, ob n eine Primzahl ist
“ liegt in der Komplexitätsklasse
P
.
Aufgaben
8.1
Gibt es eine natürliche Zahl
a
=
1, sodass
n
=
15 starke Pseudoprimzahl
zur Basis
a
ist?
Welche natürlichen Zahlen zwischen 2 und 14 sind Zeugen für die Zusammen-
gesetztheit von
n
=
15?
8.2
Es sei
n
:
=
225593397919. Wie man beispielsweise mit Maple überprüfen
kann, ist
n
=
2 207
·
6 619
·
15 443
die Primfaktorzerlegung von
n
.
(a) Schreiben Sie in einer Programmiersprache/-umgebung Ihrer Wahl ein Com-
puterprogramm, das den Fermat'schen Primzahltest für obiges
n
und
a
=
2, 3, . . . , 1 000 durchführt. Was fällt Ihnen bei den Ergebnissen der Tests auf?
(b) Versuchen Sie, die Ergebnisse aus (a) zu erklären.
8.3
Bestimmen Sie die kleinste Pseudoprimzahl zur Basis 2.
8.4
Begründen Sie: Sind
p
1
=
6
u
1
+
1,
p
2
=
12
u
2
+
1,
p
3
=
18
u
3
+
1 mit
u
1
,
u
2
,
u
3
∈
N
Primzahlen, so ist
c
=
p
1
p
2
p
3
eine Carmichael-Zahl.
8.5
Begründen Sie die in dem Beispiel auf Seite 153 gemachte Aussage, dass die
Ideale von
Z
genau die Mengen
(
k
)=
k
Z
,
k
∈
N
0
, sind.
8.6
Geben Sie einen polynomialen Algorithmus an, der prüft, ob eine natürliche
Zahl
n
der Länge
=
log
2
(
)
+
n
1 Potenz einer anderen natürlichen Zahl ist.
Gehen Sie wie folgt vor:
(a) Geben Sie ein möglichst kleines Intervall an, in dem alle möglichen Exponen-
ten liegen.
(b) Es sei
e
ein möglicher Exponent, d. h.,
n
d
e
mit einem zu bestimmenden
=
. Zeigen Sie zuerst 2
−
1
2
e
und wenden Sie ein modifiziertes
∈
N
≤
<
d
d
e
Bisektionsverfahren an.
2
a
+
1
2
a
+
1
für alle
a
8.7
Zeigen Sie mit Induktion oder anders
(
)
>
∈
N
>
1
.
a
