Cryptography Reference
In-Depth Information
2.5.1
Polynom-Restklassen
Ein Polynom vom Grade r hat die allgemeine Form
P(x)
c
x
r
c
x
r
1
...
c
x
c
c
{0, 1}, i
[0, r]
(2.5-1)
r
r
1
1
0
i
Die Koeffizienten c
i
, (i=0,1,…r) sind 0 oder 1. Sie entstammen dem GF(2), was im Folgenden
stets angenommen wird. Die Zahl der möglichen Polynome vom Grad r ist nicht unendlich
groß, sondern begrenzt. Entsprechend den (r+1) Koeffizienten ist
2
r1
&
die Zahl aller Polynome
(2.5-2)
Polynome sind allgemein bekannt, um für ein gegebenes x den Polynomwert P(x) zu berech-
nen. In unserem Kontext wird ein Polynom M(x) vom Grad r als Modul dazu benutzt, um von
beliebigen Polynomen mit Koeffizienten aus GF(2) Restpolynome zu bilden. Die Restpolyno-
me a(x) sind dann vom Grad kleiner als r und haben r Koeffizienten a
r1
, a
r2
… a
1
, a
0
. Jeder
der r Koeffizienten kann die Werte 0 oder 1 annehmen. Deshalb ist
r
(2.5-3)
Diese 2
r
Restpolynome a(x) dienen als Elemente bzw. als „Zahlen“ in der Arithmetik modu-
lo M(x). „Restpolynome als Zahlen“ ist zunächst sehr ungewohnt. Der Leser möge diese neue
Sicht auf Polynome beachten. Die Eigenschaft der „Zahlen als Polynome“ wird nur genutzt,
um Regeln einer Arithmetik zu definieren.
&
die Zahl aller Re stpolynome
2
Restklassen
Alle Polynome a(x)+i(x)·M(x) mit einem beliebigen Polynom i(x) führen bei Division durch
den Modul M(x) auf das Restpolynom a(x). Deshalb werden diese Polynome zu einer Rest-
klasse R
a
zusammengefasst. Das Restpolynom a(x) bezeichnet stellvertretend seine Restklasse
R
a
.
a(x)
a(x)
i(x) M(x)
(mod M(x), mod 2)
(2.5-4)
2
i(x)
i
i
x
i
x
...
mit Koeffizienten i
GF(2)
0
1
2
i
Nachfolgend sind die Reste und die zugehörigen Restklassen bezüglich M(x) dargestellt. Jedes
beliebige Polynom mit Koeffizienten aus GF(2) tritt in dieser Aufstellung genau einmal auf
(ohne Beweis). Die Zahl aller Restklassen ist mit 2
r
nach (2.5-3) ebenso groß wie die Zahl aller
möglichen Reste.
