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
.
Search WWH ::




Custom Search