Cryptography Reference
In-Depth Information
3.1 Endliche Körper
Aus der linearen Algebra sind die endlichen Körper
Z
p
,
p
prim, mit
p
Elemen-
ten bekannt. Es gibt viele weitere endliche Körper, genauer weiß man:
Zu jeder
Primzahlpotenz p
n
, p prim, n
, existiert bis auf Isomorphie genau ein Körper mit p
n
Elementen.
Dieser Satz wird üblicherweise in einer Vorlesung zur Algebra bewie-
sen. Wir zeigen hier nur die Existenz von Körpern mit
p
n
Elementen.
∈
N
Z
n
3.1.1 Die Restklassenringe
>
Es sei eine natürliche Zahl
n
1 fest gewählt. In der Menge
Z
n
der Restklassen
modulo
n
wird bekanntlich durch
(
+
Z
)
·
(
+
Z
)
=
+
Z
·
=
a
n
b
n
:
ab
n
,d.h.
a
b
ab
eine Multiplikation
·
eingeführt. Es ist
(
Z
n
,
·
)
eine Halbgruppe mit neutralem
+
Z
=
(
Z
n
,
+
·
)
Element 1
ist ein Ring.
Diese Konstruktion des
Restklassenringes
n
1, und
,
Z
n
:
=
Z
(
)
Z
/
n
aus dem Ring
wieder-
holen wir nun: Anstelle des Ringes
Z
betrachten wir den Polynomring
K
[
X
]
über
[
]
(
)
einem Körper
K
und konstruieren aus diesem Ring den Restklassenring
K
X
/
h
für ein Polynom
h
.
Aus der linearen Algebra ist bekannt, dass der Ring
Z
n
genau dann ein Kör-
per ist, wenn
n
eine Primzahl ist (vgl. auch Korollar 4.17). Ein analoges Ergebnis
erhalten wir auch für den Restklassenring
K
[
]
(
)
X
/
h
für ein Polynom
h
:
Der Rest-
klassenring K
ist genau dann ein Körper, wenn das Polynom h irreduzibel ist,
d. h., h ist kein Produkt von Polynomen mit einem Grad
[
X
]
/
(
h
)
≥
1
.
Mit diesem Ergebnis
können wir weitere endliche Körper konstruieren. Etwas allgemeiner nehmen
wir zunächst an, dass
K
ein Ring ist.
3.1.2 Polynome
Polynome werden oftmals als
formale Ausdrücke
der Form
a
n
X
n
+
···
+
a
1
X
+
a
0
[
]
in der
Unbestimmten X
eingeführt. Wir sind genauer: Es sei
K
X
die Menge aller
Folgen
f
=(
f
0
,
f
1
,...,
f
n
,...
)
über
K
, die nur endlich viele Folgenglieder
=
0
(
)
∈
N
0
besitzen. Ist
f
nicht die Nullfolge
0, 0, . . .
, so existiert ein Folgenindex
n
mit
f
n
=
0 und
f
k
=
0 für alle
k
>
n
:
f
=(
f
0
,
f
1
,...,
f
n
,0,...
)
.
Diese Zahl
n
nennen wir den
Grad
von
f
=(
0, 0, . . .
)
, in Zeichen
deg
f
:
=
max
{
i
∈
N
0
;
f
i
=
0
}
;
ergänzend setzen wir deg
(
0, 0, . . .
)=
−
∞
und halten uns an die üblichen Regeln
−
∞
<
n
und
−
∞
+
n
=
−
∞
für alle
n
∈
N
0
.
