Cryptography Reference
In-Depth Information
(a) d
|
f und d
|
g.
∈
[
]
|
|
|
(b) Für jedes t
K
X
mit t
f und t
g gilt t
d.
Beweis.
Es ist klar, dass es in der Menge von Polynomen
(
f
,
g
)
ein normiertes
=
+
∈
(
)
Polynom
d
mit minimalem Grad gibt. Es sei
d
.
(a) Wir teilen das Polynom
f
durch
d
mit Rest (vgl. Satz 3.2 zur Division mit Rest):
f
fa
gb
f
,
g
=
+
<
dq
r
und deg
r
deg
d
. Es gilt dann
r
=
f
−
(
fa
+
gb
)
q
∈
(
f
,
g
)
.
=
Das ist nur für
r
0 möglich, weil sonst ein Widerspruch zur Minimalität des
Grades von
d
entstünde. Folglich gilt
d
|
|
f
. Analog zeigt man
d
g
.
(b) ist wegen der Darstellung von
d
gb
und Lemma 3.5 (b) klar.
Mit dem Teil (b) folgt aus Lemma 3.5 (c) nun die Eindeutigkeit von
d
. Sind näm-
lich
d
,
d
=
fa
+
a
d
zwei normierte Polynome minimalen Grades aus
(
f
,
g
)
, so gilt
d
=
K
.Da
d
und
d
∈
=
mit einem
a
normiert sind, gilt
a
1.
Das zu
f
und
g
eindeutig bestimmte Polynom
d
aus Lemma 3.6 heißt
größter
gemeinsamer Teiler
von
f
und
g
und wird als
d
=
(
)
ggT
f
,
g
notiert. Zu dem
setzen wir ggT
(
0, 0
)
:
=
0.
Bemerkung
Wir haben im Satz 3.6 gezeigt, dass das
Ideal
(
)
[
]
f
,
g
im Ring
K
X
von einem Ele-
ment, nämlich von
d
=
ggT
(
f
,
g
)
, erzeugt wird. Tatsächlich kann man zeigen,
[
]
dass jedes Ideal in
K
X
von einem Element erzeugt wird (siehe [14, § 17]).
3.1.6
Irreduzible Polynome
Ein Polynom
h
∈
K
[
X
]
\
K
(also deg
h
≥
1) heißt
irreduzibel
, wenn für jede
Zerlegung
h
=
fg
mit Polynomen
f
,
g
∈
K
[
X
]
gilt
f
∈
K
oder
g
∈
K
. Anders
≥
ausgedrückt: Ein Polynom vom Grad
1 ist irreduzibel, falls es nicht Produkt
zweier Polynome ist, deren Grade
≥
1 sind.
Beispiel
Jedes Polynom vom Grad 1 ist wegen Lemma 3.1 irreduzibel.
Das Polynom
X
2
+
1
∈
R
[
X
]
ist irreduzibel.
Das Polynom
X
2
+
∈
Z
2
[
]
1
X
ist nicht irreduzibel.
Ü
ber dem Körper
Z
2
gilt
nämlich
X
2
2
. In der Tat ist
X
2
+
=(
+
)
+
+
1
X
1
X
1 das einzige irreduzible
Polynom vom Grad 2 über
Z
2
(vgl. auch die Aufgaben).
X
8
X
4
X
3
(
)=
+
+
+
+
∈
Z
2
[
]
Das Polynom
m
X
X
1
X
wird auch
AES-
Polynom
genannt. Es ist irreduzibel (vgl. Aufgabe 3.6).
