Cryptography Reference
In-Depth Information
2.1.1
Arithmetik modulo n, Restklassen
Wir benötigen eine endliche Zahlenmenge {0, 1, … n1} und diese erhalten wir, indem wir
von einem ganzzahligen Ergebnis x seinen Rest bei Division durch n bilden. Dabei ist n eine
ganze Zahl größer/gleich 2, d.h. 2n
¢ . Der Rest von x wird als „(x)mod n“ bezeichnet.
Sein Wert liegt in der Zahlenmenge {0, 1, … n1}. Es muss selbstverständlich geklärt werden,
welche Rechenregeln in der „Arithmetik modulo n“ gelten.
Wir beziehen uns auf die Menge der (positiven und negativen) ganzen Zahlen ¢ .
¢
0,
1,
2, ...
(2.1-1)
In der Arithmetik modulo n unterscheiden wir nicht zwischen einer ganzen Zahl a
[0, n1]
und beliebigen ganzen Zahlen x
¢ mit dem gleichen Rest a. Alle Zahlen x mit dem gleichen
Rest a ordnen wir einer Restklasse R
a
zu.
a
Ra, a
1 , a
2 , a
3 , ...
it
a
, n1
(2.1-2)
Wir sagen, die Elemente a und ain
sind „kongruent“ (Zeichen „“) modulo n.
a
a
i n
a
j n(modn)
mit
i,j
¢
(2.1-3)
In der Schreibweise bezieht sich „(mod n)“ rechts neben dem Ausdruck auf alle Kongruenzen
dieses Ausdrucks. Der Rest einer Zahl x0 kann entweder gebildet werden mittels Division
durch n oder durch vielfaches Subtrahieren von n. (Bei einer negativen Zahl x würden wir ein
Vielfaches von n addieren, bzw. die ganze Zahl i in der folgenden Formel wäre negativ.)
(x) mod n
x
i n
0, n
1
mit
x,i
¢
(2.1-4)
Abb. 2-1: „Aufwickeln der Zahlen-
geraden“ und die 5 Restklassen für
den Modul n 5:
-2
-1
0
1
2
3
R
0, 0
5, 0
10, 0
15, ...
0
R
0
R
1,15,110,115, .
R
4
R
1
1
R
2,25,210,215, .
2
R
3, 3
5, 3
10, 3
15, ...
3
R
3
R
2
R
4,45,410,415, .
4
Die Schreibweise „(x)mod n“ bedeutet, dass von dem Wert in der Klammer der Rest bezüglich
n gebildet wird. Das Ergebnis liegt dann im Intervall der ganzen Zahlen [0, n1]. Die Rest-
klassen R
x
können anschaulich dargestellt werden, indem man die Zahlengerade auf einem
„Rundholz oder Kreis mit dem Umfang n aufwickelt“, wie dies in Abb. 2-1 für den Fall n=5
dargestellt ist. Alle Zahlenwerte der gleichen Restklasse fallen beim „Aufwickeln“ aufeinan-
der. Z.B. fallen in die Restklasse R
1
alle Punkte: {1, 6, 11, 16, … sowie -4, -9, -14, …}.
Wenn wir in der Arithmetik modulo n rechnen, dann benutzen wir als „Zahlen“ die Restklas-
sen. In jedem Rechenschritt können wir eine Zahl aus einer Restklasse durch jede andere Zahl
