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
)=