Cryptography Reference
In-Depth Information
Beweis.
Die Abbildung
ψ
ist wohldefiniert und injektiv, da für
r
:
=
r
1
···
r
n
gilt:
k
+
r
Z
=
l
+
r
Z
⇔
r
|
l
−
k
⇔
r
i
|
l
−
k
für alle
i
=
1, . . . ,
n
⇔
+
r
i
Z
=
+
=
k
l
r
i
Z
für alle
i
1, . . . ,
n
⇔
ψ
(
k
+
r
Z
)=
ψ
(
l
+
r
Z
)
.
Wegen
n
i
=
1
r
i
=
n
i
=
1
|
Z
r
i
|
=
|
Z
r
1
×···×
Z
r
n
|
|
Z
r
|
=
=
r
ist
ψ
auch surjektiv. Nach Definition der Verknüpfungen ist
ψ
additiv und mult
i-
plikativ.
Bemerkung
Die
Wohldefiniertheit
ist die Umkehrung der
Injektivität
.
Wir machen uns klar, was die Surjektivität der Abbildung
ψ
in Lemma 7.3 besagt:
∈
Z
∈
Z
Zu beliebigen
a
1
,...,
a
n
gibt es ein
x
mit
+
r
1
Z
=
+
+
r
n
Z
=
+
x
a
1
r
1
Z
,...,
x
a
n
r
n
Z
oder anders geschrieben
≡
(
)
≡
(
)
x
a
1
mod
r
1
,...,
x
a
n
mod
r
n
.
Dies besagt, dass man ein System von Kongruenzgleichungen zu teilerfremden
Moduln
simultan
lösen kann. Das war bereits Sun-Tsu im 1. Jahrhundert unserer
Zeitrechnung bekannt.
Satz 7.4
(Chinesischer Restsatz)
Sind r
1
,...,
r
n
∈
Z
∈
Z
paarweise teilerfremd, so existiert zu beliebigen a
1
,...,
a
n
ein
x
∈
Z
mit
≡
(
)
=
x
a
i
mod
r
i
für alle i
1, . . . ,
n
.
Man beachte, dass dies eine Existenzaussage ist. Es
gibt
ein solches
x
. Wir zeigen
nun, wie wir die Menge aller solchen
x
explizit bestimmen können.
7.2.2 Lösen eines Systems von Kongruenzgleichungen
Für das konstruktive Lösen eines Systems von Kongruenzgleichungen der Form
X
≡
a
1
(
mod
r
1
)
,...,
X
≡
a
n
(
mod
r
n
)
mit paarweise teilerfremden
r
1
,...,
r
n
∈
Z
und beliebigen
a
1
,...,
a
n
∈
Z
beachte
man die folgenden Schritte:
