Cryptography Reference
In-Depth Information
Bemerkung
Gilt
d
:
=
(
)
|
=
∈
Z
ggT
a
,
n
c
, etwa
c
dt
,
t
, so erhält man
eine
Lösung der
Kongruenzgleichung
aX
≡
c
(
mod
n
)
mit dem euklidischen Algorithmus. Man
∈
Z
bestimme
k
,
l
mit
+
=
ak
nl
d
.
=
Multipliziert man diese Gleichung mit
t
, so sieht man, dass
x
:
kt
eine Lösung
der Kongruenzgleichung ist, da
ax
≡
c
(
mod
n
)
.
4.3.3
Invertieren modulo
n
Wie der Beweis von Satz 4.16 zeigt, erlaubt es der erweiterte euklidische Algo-
rithmus nicht nur zu klären, ob
a
modulo
n
invertierbar ist, sondern gegebe-
nenfalls das Inverse auch zu bestimmen. Weil diese Tatsache gerade in der Kryp-
tologie von so fundamentaler Bedeutung ist, halten wir sie ausdrücklich fest.
∈
Z
Satz 4.20
Es sei a
∈
Z
−
<
<
(
)=
,
n
a
n, mit
ggT
a
,
n
1
gegeben. Der erweiterte euklidische
2
Algor
it
hmus 4.10 liefert
b
,
y
∈
Z
mit a b
+
ny
=
1
in der Laufzeit O
((
log
n
)
)
.
Es ist b das Inverse von a im Ring
Z
n
.
Beweis.
Die Aussagen sind eine Zusammenfassung der Sätze 4.10, 4.15 (c) un
d
4.16. Dabei ist zu berücksichtigen, dass
a
ungefähr so groß wie
n
ist.
Wir erlauben uns, an dieser Stelle nochmals auf die Bemerkung auf Seite 71 zu
verweisen. Sie zeigt, dass die Berechnung von Inversen im Ring
Z
n
sehr effizient
möglich ist. Es sei darauf hingewiesen, dass man mit dem Versuch, das Inverse
eines Elements in
Z
n
zu bestimmen, zugleich prüft, ob es existiert. Anders aus-
gedrückt: Man muss nicht vorher testen, ob ein Inverses existiert.
Beispiel
Wir
bestimmen mit dem erweiterten euklidischen Algorithmus das Inverse von
351 in
Z
770
:
i
Division mit Rest
Darstellung
wobei
=
·
+
=
+
=
1
770
2
351
68
r
1
770
x
1
351
y
1
x
1
1
y
1
=
−
2
2
351
=
5
·
68
+
11
r
2
=
770
x
2
+
351
y
2
x
2
=
−
5
·
1
=
−
5
=
−
·
(
−
)=
y
2
1
5
2
11
=
·
+
=
+
=
−
·
(
−
)=
3
68
6
11
2
r
3
770
x
3
351
y
3
x
3
1
6
5
31
y
3
=
−
2
−
6
·
11
=
−
68
4
11
=
5
·
2
+
1
r
4
=
770
x
4
+
351
y
4
x
4
=
−
5
−
5
·
31
=
−
160
=
−
·
(
−
)=
y
4
11
5
68
351
=
·
+
=
5
2
2
1
0
r
5
0
Stop!
