Cryptography Reference
In-Depth Information
Es sei
R
ein Ring. Ein
Polynom
über
R
ist eine unendliche Folge
(
a
0
,a
1
,...
)
von
Elementen aus
R
, die die Eigenschaft besitzt, dass nur endliche viele Elemente von Null
verschieden sind. Die Glieder der unendlichen Folge werden
Koezienten
des Polynoms
genannt. Der
Grad
des Polynoms ist der größte Index
i
, für den
a
i
von Null verschieden
ist. In dem Fall, dass alle Koe
zienten Null sind, spricht man vom
Nullpolynom
und
weist ihm den Grad
−∞
zu. Wenn das Polynom mit
f
bezeichnet wird, dann bezeichnet
deg
(
f
)
seinen Grad.
Ein Polynom
f
=(
a
0
,a
1
,...
)
schreibt man meist in der Form
f
=
i≤
deg(
f
)
a
i
x
i
(4.4.1)
für ein neues Symbol
x
. Um die Verwendung von
x
zu verdeutlichen, schreibt man manch-
mal auch
f
(
x
)
. Für das Polynom
a
x
0
schreibt man meist einfach
a
. Die Menge aller
Polynome über
R
bezeichnet man mit
R
[
x
]
.
Die Menge aller Polynome über
R
kann auf einfache Weise in einen Ring verwandelt
werden. Dazu definiert man die Addition komponentenweise,
(
a
0
,a
1
,...
)+(
b
0
,b
1
,...
)=
(
a
0
+
b
0
,a
1
+
b
1
,...
)
. Stellt man Polynome in der Form (4.4.1) dar, dann entspricht die
gerade definierte Addition genau der »üblichen« Addition von Polynomen. Die Multi-
plikation von Polynomen entspricht auch der »üblichen« Multiplikation von Polynomen.
Formal wird die Multiplikation durch eine Faltung definiert:
(
a
0
,a
1
,...
)
·
·
(
b
0
,b
1
,...
)=
(
c
0
,c
1
,...
)
mit
c
i
=
j≤i
a
j
b
i−j
für jedes
i
. In diesem Ring ist das Nullpolynom
0
das neutrale Element bezüglich der Addition und
1
das neutrale Element bezüglich der
Multiplikation.
In dem Fall, dass
R
ein Körper ist, hat der Ring
R
[
x
]
spezielle Eigenschaften. Ist
nämlich
g
ein Polynom vom Grad mindestens
1
, so lässt sich jedes Polynom
f
eindeutig
schreiben als
f
=
g
h
+
r
mit deg
(
r
)
<
deg
(
g
)
. Man schreibt dann auch
f
div
g
=
h
und
f
mod
g
=
r
, in Anlehnung an die Schreibweise bei den ganzen Zahlen. Außerdem besitzen
je zwei Polynome größte gemeinsame Teiler, die sich mit Algorithmus 3.1 (erweiterter
Euklidscher Algorithmus) bestimmen lassen: Man muss lediglich die Stellen, an denen
≥
auftritt, bezüglich der Ordnung interpretieren, die durch die natürliche Ordnung auf den
Graden der beteiligten Polynome gegeben ist. Da, wie man sich leicht überlegt,
R
[
x
]
ein
Integritätsring ist, folgt mit Lemma 3.5.2, dass sich die größten gemeinsamen Teiler nur
durch Einheiten unterscheiden; für
R
[
x
]
sind die Einheiten alle Element aus
R
·
\{
0
}
,da
R
ein Körper ist.
Genau wie
Z
n
durch geeignete Definition von Addition und Multiplikation zu einem
Ring wird, wird auch die Menge aller Polynome vom Grad
<
deg
(
g
)
,diemit
R
[
x
]
/
(
g
)
bezeichnet wird, für einen Körper
R
zu einem Polynomring, dem
Faktorring modulo
g
:
f
+
g
h
=
f
+
h
mod
g
(4.4.2)
f
·
g
h
=
f
·
h
mod
g
für
f,h
∈
R
[
x
]
/
(
g
)
.
(4.4.3)
Die Einheitengruppe von
R
[
x
]
/
(
g
)
besteht wie bei
Z
n
aus den Polynomen
f
, für die gilt,
1 Siehe, zum Beispiel, [153].
