Cryptography Reference
In-Depth Information
Modulo-Multiplikation und -Division
Aus der Modulo-Addition können wir auf einfache Weise eine
Modulo-Multipli-
kation
zweier Zahlen herleiten. Wie gewohnt schreibt man dabei eine Multiplika-
tion als mehrfache Addition.
Beispiel:
4·5 = 4+4+4+4+4 (mod 7)
= 1 +4+4+4 (mod 7)
= 5 +4+4 (mod 7)
= 2 +4 (mod 7)
= 6 (mod 7)
Man kann das Ergebnis einer Modulo-Multiplikation jedoch auch etwas schnel-
ler berechnen: Man multipliziert dazu einfach die beiden Zahlen und zieht dann
so lange
n
ab, bis man schließlich eine Zahl zwischen 0 und (
n
-1) erhält.
Beispiel:
4·5 = 20-7-7 = 6 (mod 7)
Als Nächstes fragen wir uns, ob es zu jeder Zahl
a
eine Zahl
b
gibt mit der Eigen-
schaft
a
·
b
=1 (mod
n
). Gibt es eine solche Zahl, dann nennt man sie das
inverse
Element
von
a
und schreibt dafür
a
-1
. Da eine Multiplikation mit dem inversen
Element einer Zahl stets das Gleiche ist wie das Teilen durch diese Zahl, haben
wir somit auch eine
Modulo-Division
definiert. »
b
·
a
-1
(mod
n
)« kann man daher
auch als »
b
/
a
(mod
n
)« schreiben. Wann aber existiert überhaupt ein inverses Ele-
ment zu
a
, wenn modulo
n
gerechnet wird? Die Antwort lautet: wenn
a
und
n
tei-
lerfremd sind, also wenn sie außer 1 keinen gemeinsamen Teiler haben.
Beispiele:
5
-1
(mod 7) existiert, da 5 und 7 teilerfremd sind.
Es gilt: 5
-1
=3.
4
-1
(mod 8) existiert nicht, da 4 und 8 nicht teilerfremd sind
(4 teilt beide Zahlen).
7
-1
(mod 10) existiert, da 10 und 7 teilerfremd sind.
Es gilt: 7
-1
=3.
Ob zu einer Zahl
a
ein inverses Element (mod
n
) existiert, ist also einfach nachzu-
prüfen. Etwas schwieriger ist es da schon, dieses inverse Element auch zu berech-
nen. Auch dieses Problem ist jedoch in den Griff zu bekommen, und zwar mit
dem sogenannten
euklidischen Algorithmus
(den ich aus Platzgründen nicht
beschreiben will). Dieser wird im Normalfall verwendet, um den größten gemein-
samen Teiler zweier Zahlen
a
und
n
zu finden. Man kann den Algorithmus jedoch
so modifizieren, dass er
a
-1
(mod
n
) berechnet, falls diese Zahl existiert. Für
