Cryptography Reference
In-Depth Information
Das Multiplikationsschema für Polynome entspricht dem aus der Grundschule bekannten Mul-
tiplikationsschema. Bei der Addition wird jedoch stellenweise modulo 2 addiert. Dadurch
ergeben sich andere Ergebnisse als bei der Multiplikation von Dualzahlen. Die Stellen entspre-
chen bestimmten Potenzen von x. Für die Restbildung bezüglich M(x) werden Vielfache von
M(x) derart subtrahiert, dass nur noch Wertigkeiten von kleiner als r=3 übrig bleiben. In der
Arithmetik mod 2 braucht zwischen Addition und Subtraktion nicht unterschieden zu werden,
sie sind gleich, vgl. (2.1-7) in Kap. 2.1.2.1.
2.5.2
Irreduzible Polynome
Polynome mit Koeffizienten aus GF(2) haben die Eigenschaft, dass sie entweder in ein Pro-
dukt von Teilpolynomen aufgespalten werden können („reduzibel“) oder nicht aufgespalten
werden können („irreduzibel“). Die Teilpolynome müssen ebenfalls Koeffizienten aus GF(2)
haben. Die Produktbildung der Teilpolynome erfolgt nach den Regeln der Arithmetik mod 2.
In der Arithmetik modulo M(x) haben irreduzible Polynome eine vergleichbare Eigenschaft
wie Primzahlen (irreduzible Zahlen) in der Arithmetik modulo n. Irreduzible Modularpolyno-
me M(x) begründen in der Arithmetik modulo M(x) einen Körper, d.h. es ist auch das Axiom
11 erfüllt (vgl. Kap. 2.1.2). Dieser Körper wird als Erweiterungskörper GF(2
r
) bezeichnet.
Für große Grade von r sind irreduzible Polynome schwer zu finden. Ähnlich wie für Primzah-
len gibt es auch Tabellen für irreduzible Polynome. In der folgenden Tabelle sind einige Bei-
spiele zusammengestellt (aus [RWV95], [Pe61], [S73]).
Tab. 2-3: Koeffizienten für einige irreduzible Polynome vom Grad r = 2…8.
r c9 c8 c7 c6 c5 c4 c3 c2 c1 c0 primitiv
2
1
1
1
ja
3
1
0
1
1
ja
4
1
0
0
1
1
ja
5
1
0
0
1
0
1
ja
1
1
1
1
0
1
ja
···
···
···
6
1
0
0
0
0
1
1
ja
1
0
1
0
1
1
1
nein
···
···
···
7
1
0
0
0
1
0
0
1
ja
···
···
···
8
1
0
0
0
1
1
1
0
1
ja
1
0
1
1
1
0
1
1
1
nein
1
0
0
0
1
1
0
1
1
?
···
···
···
