Cryptography Reference
In-Depth Information
Der Algorithmus bricht ab, weil die
r
i
∈
N
0
streng monoton fallen. Wegen Lem-
ma 4.9 gilt in jedem Schritt ggT
(
)=
(
)
. Daher erhalten wir per
Induktion nach
k
(mit den Bezeichnungen aus obiger Tabelle):
r
k
,
r
k
−
1
ggT
r
k
+
1
,
r
k
Satz 4.10
(Der euklidische Algorithmus)
Der euklidische Algorithmus bricht nach n
+
1
Schritten ab. Sind a
,
b ganze Zahlen,
b
=
0
, so ist der Rest r
n
der
ggT
von a und b:
=
(
)
r
n
ggT
a
,
b
.
Weiter liefert der Alorithmus ganze Zahlen x
:
=
x
n
und y
:
=
y
n
mit
ggT
(
a
,
b
)=
ax
+
by
.
Beispiel 4.11
Wir bestimmen mit dem erweiterten euklidischen Algorithmus ganze Zahlen
x
und
y
mit ggT
(
840, 455
)=
x
·
840
+
y
·
455:
i
Division mit Rest
Darstellung
wobei
=
·
+
=
+
=
1
840
1
455
385
r
1
840
x
1
455
y
1
x
1
1
y
1
=
−
1
2
455
=
1
·
385
+
70
r
2
=
840
x
2
+
455
y
2
x
2
=
−
1
·
1
=
−
·
(
−
)
y
2
1
1
1
=
·
+
=
+
=
−
·
(
−
)
3
385
5
70
35
r
3
840
x
3
455
y
3
x
3
1
5
1
y
3
=
−
1
−
5
·
2
4
70
=
2
·
35
+
0
r
4
=
0
Stop!
Wir erhalten
(
)=
=
·
+(
−
)
·
ggT
840, 455
35
6
840
11
455 .
Eine einfache, aber wichtige Folgerung ist die fast offensichtliche Kennzeichnung
für den ggT.
Lemma 4.12
Für a
,
b
∈
Z
∈
N
0
gilt d
=
(
)
und d
ggT
a
,
b
genau dann, wenn
|
|
(i)
d
a und d
b, und
(ii)
für jedes t
∈
Z
mit t
|
a und t
|
b gilt t
|
d.
Beweis.
: (i) gilt nach Voraussetzung.
(ii) Es gelte
t
⇒
a
t
und
b
b
t
, für ein
t
|
|
=
=
∈
Z
=
(
)
a
und
t
b
, etwa
a
. Ist
d
ggT
a
,
b
,
so existieren nach dem euklidischen Algorithmus Zahlen
x
,
y
∈
Z
mit
a
tx
b
ty
a
x
b
y
d
=
ax
+
by
=
+
=(
+
)
t
,
