Cryptography Reference
In-Depth Information
m
r
i
Setze
m
:
=
r
1
···
r
n
und
s
i
:
=
für
i
=
1, . . . ,
n
.
Bestimme
x
i
∈
Z
mit
x
i
s
i
≡
1
(
mod
r
i
)
für
i
=
1,...,
n
.
Es ist dann
x
n
s
n
a
n
eine Lösung des obigen Systems von Kongruenzengleichungen, und die Lö-
sungsmenge ist
x
x
=
x
1
s
1
a
1
+
···
+
+
m
Z
.
Die Begründung ist einfach: Satz 4.20 garantiert, dass solche
x
i
existieren, da
r
i
und
s
i
für alle
i
=
1, . . . ,
n
teilerfremd sind - man kann also
x
1
,...,
x
n
mit dem
euklidischen Algorithmus bestimmen.
Weil für
i
=
j
das Element
r
i
ein Teiler von
s
j
ist, ist das angegebene
x
tatsächlich
eine Lösung der
n
Kongruenzgleichungen. Für jedes
i
=
1, . . . ,
n
gilt nämlich
n
j
=
1
x
j
s
j
a
j
≡
x
i
s
i
a
i
≡
a
i
(
mod
r
i
)
.
=
x
Ist
y
neben
x
eine weitere Lösung des Systems, so gilt
≡
≡
(
)
=
⇒
|
−
=
x
y
a
i
mod
r
i
für alle
i
1, . . . ,
n
r
i
x
y
für alle
i
1,...,
n
⇒
m
|
x
−
y
,d.h.
x
≡
y
(
mod
m
)
,
∈
+
+
folglich gilt
y
x
m
Z
. Andererseits ist jedes Element aus
x
m
Z
Lösung des
Systems, sodass
x
+
m
Z
die Lösungsmenge ist.
Beispiel
Gesucht ist die Lösungsmenge des Kongruenzensystems
≡
(
)
≡
(
)
≡
(
)
X
2
mod 5
,
X
3
mod 7
,
X
2
mod 4
.
Es ist also
m
=
140,
s
1
=
28,
s
2
=
20,
s
3
=
35.
∈
Z
Wir bestimmen nun
x
1
,
x
2
,
x
3
mit
28
x
1
≡
1
(
mod 5
)
,20
x
2
≡
1
(
mod 7
)
,35
x
3
≡
1
(
mod 4
)
.
=
=
−
=
−
Offenbar kann man
x
1
1 wählen. Wenn dies nicht so
offensichtlich ist, wende man den euklidischen Algorithmus an. Damit haben wir
die Lösung:
2,
x
2
1,
x
3
=
·
·
+(
−
)
·
·
+(
−
)
·
·
=
−
x
2
28
2
1
20
3
1
35
2
18 .
Die Lösungsmenge lautet
−
18
+
140
Z
.
Bemerkung
Man erkennt, dass man nicht immer den kleinsten positiven Vertreter der Rest-
klasse findet. Ist das gewünscht, muss man noch eine Division mit Rest durch-
führen:
−
18
+
140
Z
=
122
+
140
Z
.