Cryptography Reference
In-Depth Information
Beispiel
Es sei
K
X
2
=
R
=
+
=
R
[
]
(
)=
{
+
∈
R
}
und
h
1. Es ist dann
C
:
X
/
h
a
bX
;
a
,
b
,
und es gilt
bdX
2
X
2
(
+
)
·
h
(
+
)=
+(
+
)
+
−
(
+
)
a
bX
c
dX
ac
ad
bc
X
bd
1
=
ac
−
bd
+(
ad
+
bc
)
X
.
Das ist die übliche Multiplikation komplexer Zahlen, wobei
X
2
=
−
1. Es ist somit
C
der Körper der komplexen Zahlen.
Bemerkung
In der Algebra wird der Ring
K
[
X
]
/
(
h
)
als Restklassenring nach dem von
h
er-
(
)
zeugten
Ideal
definiert. Diese Konstruktion abstrahiert auch die Bildung von
Z
n
und ist eine wichtige Methode der Ringtheorie (siehe [14, § 14]). Wir greifen
das Thema in Abschnitt 8.4.1 noch einmal auf.
h
3.1.5 Der ggT von Polynomen
Ein Polynom
f
∈
K
[
X
]
heißt
normiert
, wenn der höchste Koeffizient
f
deg
f
gleich
=
|
1 ist,
f
deg
f
1. Wir sagen
f
teilt
g
, in Zeichen
f
g
, wenn es ein Polynom
q
∈
K
[
X
]
gibt mit
g
=
fq
. Das ist gleichbedeutend mit
g
≡
0
(
mod
f
)
.Wir
=
schreiben dann auch
q
g
/
f
.
Beispiel
In
gilt etwa
X
2
X
3
X
2
9
X
2
Z
[
]
+
|
−
+
−
|
−
X
1
X
1 und 3
3
X
.
Wir formulieren einige Regeln für die Relation
|
als Übungsaufgabe.
Lemma 3.5
Es sei K ein Körper oder K
=
Z
. Für Polynome f
,
g
,
h
∈
K
[
X
]
gilt:
|
|
|
|
|
(a) Die Relation
ist reflexiv und transitiv, d. h. f
f und aus f
g und g
h folgt f
h.
|
|
|
(
+
)
∈
[
]
(b) Aus f
g und f
h folgt f
ga
hb
für alle a
,
b
K
X
.
(c) Falls f
|
g und g
|
f , so existiert ein a
∈
K mit f
=
ag.
=
Wir zeigen nun, dass es zu je zwei Polynomen
f
und
g
0 ein eindeutig be-
stimmtes Polynom maximalen Grades gibt, das beide Polynome teilt und nor-
miert ist. Dieses eindeutig bestimmte Polynom werden wir den
größten gemeinsa-
men Teiler
von
f
und
g
nennen.
Satz 3.6
Es seien f
,
g
∈
[
]
=
=
K
X
,f
0
oder g
0
, zwei Polynome über einem Körper K. In der
Menge
]
}
existiert ein eindeutig bestimmtes, normiertes Polynom d minimalen Grades. Es gilt
(
)
=
{
+
∈
[
f
,
g
:
fa
gb
;
a
,
b
K
X
