Cryptography Reference
In-Depth Information
3.1.4 Restklassen in Polynomringen
Aus der linearen Algebra sind die Restklassen modulo
n
∈
N
in
Z
bekannt und
auch die Schreibweise
a
≡
r
(
mod
n
)
, falls die Zahl
a
−
r
durch
n
teilbar ist. Im
=
·
+
∈
[
]
Fall
f
g
q
r
für Polynome
f
,
g
,
q
,
r
K
X
schreiben wir in Analogie zu den
ganzen Zahlen:
≡
(
)
⇔
=
+
∈
[
]
f
r
mod
g
:
f
gq
r
für ein
q
K
X
.
Wie bei den ganzen Zahlen ist auch dies eine Äquivalenzrelation auf
K
.
Satz 3.2 besagt gerade, dass in jeder Äquivalenzklasse ein Polynom mit Grad
kleiner als deg
g
liegt.
Für ein
h
[
X
]
∈
[
]
=
K
X
,
h
0, ist die Menge
K
[
X
]
/
(
h
)
:
=
{
f
∈
K
[
X
]
; deg
f
<
deg
h
}
(
[
]
+)
nach Lemma 3.1 eine Untergruppe von
K
X
,
. Wir definieren eine Multipli-
kation auf der Menge
K
[
X
]
/
(
h
)
:
·
h
g
≡
(
)
(
·
h
g
)
<
f
fg
mod
h
und
deg
f
deg
h
.
Wir multiplizieren also die zwei Polynome
f
und
g
mittels der oben erklärten
Multiplikation für Polynome und führen dann evtl. eine Division mit Rest durch.
Wir wählen als
f
·
h
g
das nach Satz 3.2 zur Division mit Rest eindeutig bestimmte
∈
[
]
(
)
Polynom
r
K
X
/
h
mit
fg
=
hq
+
r
und
deg
r
<
deg
h
.
[
]
(
)
Nun können wir ohne große Mühe nachweisen, dass
K
X
/
h
mit den erklärten
Verknüpfungen
+
und
·
h
einen Ring bildet.
Lemma 3.4
Für jedes Polynom h
=
0
aus K
[
X
]
ist
(
K
[
X
]
/
(
h
)
,
+
,
·
h
)
ein Ring mit Einselement
1
.
Beweis.
Es sind nur das Assoziativgesetz für die Multiplikation und das Dis-
tributivgesetz zu zeigen. Wir betrachten exemplarisch das Letztere. Es seien
f
,
g
,
g
∈
[
]
(
)
K
X
/
h
. Es gilt:
g
)
−
·
h
g
=
·
h
(
+
·
h
g
−
f
g
f
f
qh
für ein
q
∈
K
[
X
]
. Aus Gradgründen folgt
q
=
0, d. h.
g
)=
·
h
g
.
·
h
(
+
·
h
g
+
f
g
f
f
Wir betrachten ein wohlbekanntes Beispiel.
