Cryptography Reference
In-Depth Information
und dieses ist das multiplikativ inverse Element zu a(x). In dem 1. Teilbeweis musste voraus-
gesetzt werden, dass M(x) irreduzibel ist. Deshalb ist nur in diesem Fall das Axiom 11 erfüllt.
Beispiel für die Arithmetik modulo M(x)
Für das Beispiel wird ein irreduzibles Modularpolynom vom Grad r=3 gewählt (vergleiche
Tab. 2-3):
2
Die 2
r
=2
2
=4 Restpolynome bilden dann die Elemente bzw. die „Zahlen“ eines Galois-Körpers.
M(x)
x
x
1
Tab. 2-4: Restpolynome bezüglich M(x)=x
2
+x+1.
Restpolynom Symbol
0·x+0
{00}={0}
0·x+1
{01}={1}
1·x+0
{10}={2}
1·x+1
{11}={3}
Die Symbole {0},{1},{2} und {3} bezeichnen die Elemente der Arithmetik modulo M(x) und
sind eine Kurzschrift für die Restpolynome. Es lassen sich die Tafeln für die Addition und
Multiplikation aufstellen. Sie lauten in der symbolischen Schreibweise:
Tab. 2-5: Additiostafel und Multiplikationstafel für die Arithmetik modulo M(x)=x
2
+x+1.
+ {0} {1} {2} {3}
• {0} {1} {2} {3}
{0} {0} {1} {2} {3} {0} {0} {0} {0} {0}
{1} {1} {0} {3} {2} {1} {0} {1} {2} {3}
{2} {2} {3} {0} {1} {2} {0} {2} {3} {1}
{3} {3} {2} {1} {0} {3} {0} {3} {1} {2}
Beispielsweise wird für die Multiplikationstafel {3}·{3}={2} folgendermaßen berechnet:
{3} {3}=(x+1) (x+1) = x +x+x+1
x +1
2
2
2
2
2
(x +1)+M(x) = (x +1)+(x +x+1)
x = {2}
(mod 2, mod M(x))
Vereinfachend könnte {3}·{3}={2} auch entsprechend dem Schema Tab. 2-2 ermittelt werden.
Die Tafeln für Addition und Multiplikation unterscheiden sich von jenen der Arithmetik
mod 4. Man beachte die folgenden Merkmale: Die {0} ist das Null-Element, in der Additions-
tafel ist a+{0}=a für jedes a. Jedes Element ist zu sich selbst additiv invers, a+a={0}, entspre-
chend dem Element {0} in der Hauptdiagonalen der Additionstafel. Das Element {1} ist das
Eins-Element, entsprechend a·{1}=a für jedes a in der Multiplikationstafel. Für jedes Element
a{0} gibt es ein multiplikativ inverses Element, denn in jeder Zeile (oder Spalte) gibt es für
a{0} als Produkt das Element {1}.
