Cryptography Reference
In-Depth Information
Tab. 2-1: Reste und Restklassen für das Modularpolynom M(x) vom Grad r.
Reste
Restklassen
0
{0,
0+1·M(x),
0+x·M(x),
0+(x+1)·M(x),
…}
1
{1,
1+1·M(x),
1+x·M(x),
1+(x+1)·M(x),
…}
x
{x,
x+1·M(x),
x+x·M(x),
x+(x+1)·M(x),
…}
(x+1)
{(x+1),
(x+1)+1·M(x)
,
(x+1)+x·M(x)
,
(x+1)+
(x+1)·M(x),
…}
…
…
(x
r-1
+…+x+1)
{(x
r-
1
+…+x+1),
(…)+1·M(x),
(…)+x·M(x),
(…)+(x+1)·M(x),
…}
Beispiel für das Rechnen mit Polynom-Restklassen
Das Rechnen mit Restpolynomen als Zahlen soll an einem kleinen Beispiel veranschaulicht
werden. Das Modularpolynom sei M(x)=x
3
+x+1 mit dem Grad r=3. Es sollen zwei Elemente
a(x)=x
2
+x und b(x)=x
2
+1 multipliziert werden. Wie lautet das Ergebnis c(x)=a(x)·b(x)?
c(x)=(x
2
+x)·(x
2
+1)=x
4
+x
3
+x
2
+xx+1 mod(x
3
+x+1)
Die Verwendung der Polynome als „Zahlen“ wird augenscheinlicher, wenn man die Folge der
Polynom-Koeffizienten, beginnend mit der höchsten Potenz, zur Darstellung benutzt. Zur
Unterscheidung von normalen Zahlen wird die Koeffizientendarstellung in geschweifte
Klammern „{}“ geschrieben. Die Operationen mit den Polynomen erscheinen dann als über-
sichtliches Schema:
Tab. 2-2: Schema für Multiplikation und Restbildung der Restpolynome a(x)·b(x)
a(x) = x
2
+x = 1·x
2
+1·x
1
+0·x
0
= {110}
b(x) = x
2
+1 = 1·x
2
+0·x
1
+1·x
0
= {101}
M(x) = x
3
+x+1 = {1011}
1
1
0
·
1
0
1
Multiplikand, Multiplikator
(1·x
2
+1·x
1
+0·x
0
)·1·x
2
, für 1. Stelle des Multiplikators
1
1
0
(1·x
2
+1·x
1
+0·x
0
)·0·x
1
,
0
0
0
(1·x
2
+1·x
1
+0·x
0
)·1·x
0
, für 3. Stelle des Multiplikators
1
1
0
1
1
1
1
0
Ergebnis der Polynom-Multiplikation
M(x)·x
1
zur Restbildung,
1
0
1
1
stellenweise Addition
M(x)·x
0
zur Restbildung
1
0
1
1
0
1
1
Ergebnis, Restpolynom bezüglich M(x)
x
4
x
3
x
2
x
1
x
0
Wertigkeiten der Stellen
