Cryptography Reference
In-Depth Information
4.3 Komplexität der Multiplikation
(a) Beschreiben Sie die Multiplikation zweier Binär-Zahlen nach der bekannten
Methode aus der Grundschule.
(b) Bestimmen Sie die Komplexität des Algorithmus in (a).
(c) Berechnen Sie 1100100
·
1010101 mit dem Algorithmus in (a).
∈
N
(d) Es seien
a
,
b
in der
g
-adischen Darstellung
n
1
i
=
0
a
i
g
i
,
−
n
1
i
=
0
b
i
g
i
mit
n
=
2
ν
−
=
=
a
b
gegeben. Wir setzen
n
2
−
1
i
=
0
a
i
g
i
und
a
H
:
=
n
2
−
1
i
=
0
a
2
+
i
g
i
, sodass
a
=
a
L
+
a
H
g
2
=
a
L
:
b
H
g
2
. Nun gilt
a
vg
2
wg
n
mit
und entsprechend
b
=
b
L
+
·
b
=
u
+
+
=
=
+
=
+
−
(
−
)(
−
)
=
u
a
L
b
L
,
v
a
L
b
H
a
H
b
L
u
w
a
L
a
H
b
L
b
H
,
w
a
H
b
H
.
Zeigen Sie, dass diese
Methode von Karatsuba-Ofman
eine Komplexität von
O
(
n
log
2
3
)
hat.
4.4
Beweisen Sie den Fundamentalsatz der Arithmetik 4.14.
4.5
Zeigen Sie, dass die Relation
algorithmisch äquivalent
von Seite 64 eine Äqui-
valenzrelation ist.
4.6
Zeigen Sie, dass Kollisionsresistenz die im Text so genannte
schwächere Form
der Kollisionsresistenz impliziert.
n
2
soll eine Kollision mithilfe des Ge-
burtstagsparadoxons (siehe Aufgabe 2.2) konstruiert werden. Man spricht von
der
Geburtstags-Attacke
.
Wie viele Versuche braucht man, ummit Wahrscheinlichkeit
4.7
Für eine Hashfunktion
h
:
P
→
Z
≈
1/2 eine Kollision
zu finden, wenn
n
=
64,
n
=
128 und
n
=
160 ist?
