Cryptography Reference
In-Depth Information
Hierzu vergleiche man auch die Aussage in Lemma 4.1. Man kann nämlich
den üblichen Multiplikations-Algorithmus als Polynom-Multiplikation mit Über-
trag deuten.
Selbst bei diesen einfachen Operationen ist möglicherweise nicht das letzte Wort
gesprochen, wie zum Beispiel Aufgabe 4.3 zeigt.
Bemerkung
Der Multiplikations-Algorithmus von Schönhage und Strassen [24] hat die Kom-
plexität O
log b . Das ist zwar besser als
unsere Laufzeitangabe in Lemma 4.3, wirkt sich aber erst ab n
(
n log n log log n
)
, wobei n
=
log a
10 000 in einer
tatsächlichen Beschleunigung aus.
4.1.5 Division mit Rest
In Satz 3.2 wurde die Division mit Rest für Polynome über einem Körper einge-
führt. Sicher schon aus der Schule bekannt ist die für die Kryptologie fundamen-
tale Division mit Rest für ganze Zahlen. Der Vollständigkeit halber wiederholen
wir den Satz. Der Beweis kann fast wörtlich aus dem Beweis zu Satz 3.2 über-
nommen werden. An die Stelle der Abbildung deg tritt dabei die Betragsfunktion
|·|
, wie man schon an der Formulierung sehen kann.
Satz 4.4 (Division mit Rest)
Zu ganzen Zahlen a , b, wobei b
=
Z
0 , existieren eindeutig bestimmte q , r
mit
a
=
bq
+
r und 0
r
< |
b
|
.
Bemerkung
Wir erinnern an eine Schreibweise, die aus der linearen Algebra bekannt ist. Man
sagt, zwei ganze Zahlen a und r sind kongruent modulo b , falls es ein q
Z
gibt
=
+
mit a
bq
r . Man schreibt dafür auch
a
r
(
mod b
)
.
=
Der Satz zur Division mit Rest besagt, dass, im Falle b
0, jede ganze Zahl a zu
einer Zahl r
∈{
0, . . . ,
|
b
| −
1
}
kongruent modulo b ist. Offenbar ist
(
mod b
)
|
|
eine Äquivalenzrelation, die Anzahl der Äquivalenzklassen ist
b
.
Legt man den aus der Schule bekannten Algorithmus zur Division mit Rest zu-
grunde, so erhalten wir für die Laufzeit:
Lemma 4.5
Die Division mit Rest bei ganzen Zahlen a , b, wobei b
=
0 , d. h. die Bestimmung von
Z
=
+
< |
|
q , r
mit a
bq
r und 0
r
b
, hat die Laufzeit
O log b log a
b .
O
(
log b log q
)=
Search WWH ::




Custom Search