Cryptography Reference
In-Depth Information
erhält man durch Einsetzen von
x
=
k
d
und
y
=
Beweis.
Die Richtung
⇐
x
+
k
d
in
ax
+
by
:
−
y
a
x
b
y
d
k
b
d
k
a
ax
+
by
=
+
+
−
=
+
=
ax
by
d
.
a
x
b
y
folgt:
⇒
+
=
=
+
Wir zeigen nun die Richtung
: Aus
ax
by
d
a
d
x
b
d
y
a
b
d
x
+
d
y
.
+
=
=
1
Wir erhalten aus dieser Gleichung, indem wir modulo
d
rechnen, die Kongruenz
d
x
mod
b
.
a
d
x
a
≡
d
a
d
,
d
)=
a
(
Da ggT
1 kann man nach Satz 4.16 den Faktor
d
kürzen, und es folgt
x
mod
b
d
,
≡
x
wie behauptet. Die Darstellung von
y
ergibt sich, indem man die resultierende
Gleichung
a
x
k
b
d
by
ax
+
by
=
+
+
nach
y
auflöst.
Eine
Gleichung
der Form
≡
(
)
∈
Z
∈
N
aX
c
mod
n
mit
a
,
c
und
n
nennt man eine
(lineare) Kongruenzgleichung
. Die Lösungsmenge
L
der Kon-
gruenzgleichung
aX
≡
c
(
mod
n
)
ist die Menge aller Zahlen
x
∈
Z
mit
n
|
ax
−
c
,
anders ausgedrückt:
L
=
{
x
∈
Z
;
∃
y
∈
Z
mit
ax
+
ny
=
c
}
.
Wir erhalten folglich aus Lemma 4.18:
Korollar 4.19
Es seien a
,
c
∈
Z
und n
∈
N
. Die Kongruenzgleichung
(
∗
)
≡
(
)
aX
c
mod
n
Z
=
(
)
|
∈
Z
hat genau dann eine Lösung in
, wenn d
:
ggT
a
,
n
c. Ist x
eine Lösung der
n
Kongruenzgleichung
(
∗
)
, so ist x
+
d
Z
die Menge aller Lösungen von
(
∗
)
.
