Cryptography Reference
In-Depth Information
kurz wiederholt. Wir werden dabei nur wenige ausgewählte Aussagen beweisen. Für eine
eingehendere Einführung verweisen wir auf die einschlägige Literatur.
1
Chinesischer Restsatz
Wir beginnen mit einem sehr wichtigen und grundlegenden Ergebnis der Zahlentheorie.
Dazu erinnern wir daran, dass
Z
c
für eine natürliche Zahl
c
≥
2
ein kommutativer Ring
mit
1
ist. Für
a, b
Z
a
×
Z
b
ein kommutativer Ring mit
1
, falls komponenten-
weise addiert und multipliziert wird; das Nullelement ist
(0
,
0)
und das Einselement ist
(1
,
1)
.
≥
2
ist auch
Satz 6.3.1 (Chinesischer Restsatz).
Es seien
a, b ≥
2
teilerfremd, d. h., ggT
(
a, b
)=
1
,und
n
=
a
·
b
. Dann ist die Abbildung
h
:
Z
n
→
Z
a
×
Z
b
definiert durch
k
→
(
k
mod
a, k
mod
b
)
ein Ring-Isomorphismus.
Gilt
1=
r
·
a
+
s
·
b
,für
r, s
∈
Z
, dann ist
(
l,k
)
→
l
·
s
·
b
+
k
·
r
·
a
mod
n
die
Umkehrabbildung
h
−
1
zu
h
.
Beweis.
Man überzeugt sich leicht davon, dass
h
ein Homomorphismus von
Z
n
nach
Z
a
×
Z
b
ist, d. h.,
h
(1) = (1
,
1)
,
h
(
c
+
n
d
)=
h
(
c
)+
(
a,b
)
h
(
d
)
und
h
(
c
·
n
d
)=
h
(
c
)
·
(
a,b
)
h
(
d
)
für alle
c, d ∈
Z
n
,wobei
+
(
a,b
)
und
·
(
a,b
)
die Addition bzw. Multiplikation in
Z
a
×
Z
b
bezeichnet. Es ist auch leicht zu sehen, dass
h
−
1
(
l,k
)=
l
a
mod
n
die
Umkehrabbildung zu
h
ist, denn wegen
1=
r·a
+
s·b
ist
r·a
mod
b
=1
und
s·b
mod
a
=1
,
und damit gilt:
·
s
·
b
+
k
·
r
·
h
(
h
−
1
(
l,k
)) = (
h
−
1
(
l,k
)
mod
a, h
−
1
(
l,k
)
mod
b
)
=(
l
·
s
·
b
+
k
·
r
·
a
mod
a, l
·
s
·
b
+
k
·
r
·
a
mod
b
)
=(
l · s · b
mod
a, k · r · a
mod
b
)
=(
l,k
)
.
Daraus folgt nun auch leicht, dass
h
bijektiv ist. Insgesamt erhalten wir somit, dass
h
ei
n
Ring-Isomorphismus ist.
Dieser Satz ermöglicht es, ein zahlentheoretisches Problem in ein einfacheres zu zer-
legen. Dies kann, wie wir sehen werden, zum einen in Beweisen nützlich sein, aber zum
anderen auch bei der Berechnung zahlentheoretischer Funktionen: statt in
Z
n
kann man
einfach in
Z
a
×
Z
b
rechnen, dann hat man es mit kleineren Zahlen zu tun. Der Chinesi-
sche Restsatz kann außerdem angewendet werden, um etwas über die Einheitengruppe
von
Z
n
zu erfahren:
Folgerung 6.3.1.
Es seien
a, b
b
. Dann ist die Abbildung
h
:
Z
n
→
Z
a
×
Z
b
definiert durch
k →
(
k
mod
a, k
mod
b
)
wohldefiniert und ein Gruppe
n
-
Isomorphismus.
≥
2
teilerfremd und
n
=
a
·
Grundlagen über Gruppen
Die
Ordnung
einer Gruppe
G
ist die Anzahl ihrer Elemente und wird mit
|
G
|
bezeichnet.
1 Siehe, zum Beispiel, [153].
