Cryptography Reference
In-Depth Information
Wir nennen die Elemente
f
Polynome
, die Folgenglieder
f
0
,
f
1
, . . . ei-
nes Polynoms
f
nennen wir die
Koeffizienten
von
f
, und ist
f
∈
K
[
X
]
=(
)
0, 0, . . .
,so
nennen wir den Koeffizienten
f
deg
f
den
höchsten Koeffzienten
oder den
Leit-
koeffizienten
von
f
.
Wir definieren eine Addition und eine Multiplikation für Polynome
f
,
g
∈
K
[
X
]
:
i
j
=
0
(
+
)
i
:
=
+
(
)
i
:
=
∈
N
0
.
f
g
f
i
g
i
und
fg
f
j
g
i
−
j
für alle
i
[
]
Eine einfache Rechnung zeigt, dass
K
X
dadurch zu einem Ring wird, genannt
der
Polynomring
über
K
.
Beispiel
Für die Polynome
f
=(
)
=(
−
)
Z
[
]
2, 0, 3, 0, . . .
und
g
1,
1, 0, 1, 0, . . .
aus
X
gilt:
+
=(
−
)
=(
−
−
)
f
g
3,
1, 3, 1, 0, . . .
und
fg
2,
2, 3,
1, 0, 3, 0, . . .
.
n
i
f
i
X
i
= ∑
Um zur gewohnten Schreibweise
f
zu kommen, setzen wir
=
0
=(
)
X
:
0, 1, 0, . . .
und identifizieren jedes Element
a
aus dem zugrunde liegenden Ring
K
mit dem
Polynom
.
Damit erhält man aus der obigen Definition für die Multiplikation von Polyno-
men für alle
n
(
a
,0,0,...
)
∈
K
[
X
]
∈
N
0
und
a
∈
K
X
n
und
aX
n
=(
)
=(
)
0,...,0,1,0,...
0,..., 0,
a
,0,...
,
(
+
)
wobei die 1 bzw.
a
an
n
1
-ter Stelle steht und sonst nur Nullen vorkommen.
Daraus ergibt sich für
f
=(
f
0
,
f
1
,
f
2
,...,
f
deg
f
,0,...
)
=(
0, 0, . . .
)
aus der Defi-
nition für die Addition von Polynomen die Darstellung:
f
2
X
2
f
deg
f
X
deg
f
=
+
+
+
···
+
f
f
0
f
1
X
.
=(
)
Für das
Nullpolynom
f
0, 0, . . .
schreiben wir kurz 0. Wir erhalten für den
Polynomring
K
[
X
]
die Darstellung:
n
k
=
0
a
k
X
k
;
n
∈
N
0
,
a
0
,...,
a
n
∈
K
.
K
[
X
]=
Lemma 3.1
Ist K ein Körper oder K
=
Z
, so gilt für alle f
,
g
∈
K
[
X
]
:
deg
(
f
+
g
)
≤
max
{
deg
f
, deg
g
}
und
deg
(
fg
)=
deg
f
+
deg
g
.
Beweis.
Offenbar stimmen die Regeln für
f
=
0 oder
g
=
0. Sind
f
und
g
beide
(
+
)
≤
{
}
ungleich 0, so gilt natürlich deg
f
g
max
deg
f
, deg
g
.
Die Aussage deg
(
fg
)=
deg
f
+
deg
g
folgt durch Berechnen des höchsten Koef-
(
)
n
+
m
=
(
)
j
=
>
+
fizienten von
fg
. Wegen
fg
f
n
g
m
und
fg
0 für alle
j
n
m
i
st
dieser
f
n
g
m
=
0.
