Cryptography Reference
In-Depth Information
4.2.2 Der erweiterte euklidische Algorithmus
Der erweiterte euklidische Algorithmus bestimmt den
größten gemeinsamen
Teiler
, in Zeichen ggT, zweier (oder mehrerer) ganzer Zahlen.
Sind
a
1
,...,
a
k
ganze Zahlen, so heißt eine Zahl
t
∈
Z
gemeinsamer Teiler
von
. Die natürliche Zahl 1 ist immer
ein gemeinsamer Teiler. Ist eines der
a
i
, etwa
a
1
, ungleich 0, so gilt
a
1
, ...,
a
k
, wenn
t
|
a
i
für alle
i
∈{
1, ...,
k
}
|
| ≤ |
|
t
a
1
.
Daher gibt es in diesem Fall ein größtes
t
∈
N
, das alle
a
1
,...,
a
k
teilt, genannt
=
(
)
der
größte gemeinsame Teiler
der
a
i
. Wir schreiben dafür
t
ggT
a
1
,...,
a
k
.
Falls alle
a
1
,...,
a
k
gleich 0 sind, so setzt man ggT
(
a
1
,...,
a
k
)
:
=
0. Der ggT von
endlich vielen Zahlen liegt stets in
N
0
.
Lemma 4.9
Für alle a
,
b
,
q
∈
Z
(
)=
(
+
)
gilt
ggT
a
,
b
ggT
a
bq
,
b
.
Beweis.
Wir benutzen Lemma 4.8 (d) zweimal:
(
)
|
(
+
)
|
(
+
−
)=
(
)
ggT
a
,
b
ggT
a
bq
,
b
ggT
a
bq
bq
,
b
ggT
a
,
b
.
Nun folgt die Aussage aus dem Teil (b) in Lemma 4.8.
Aus dieser einfachen Beobachtung ergibt sich der erweiterte euklidische Algo-
rithmus zur Berechnung des ggT von zwei ganzen Zahlen
a
und
b
. Er bestimmt
außerdem zwei ganze Zahlen
x
und
y
mit
+
=
(
)
ax
by
ggT
a
,
b
.
Ohne Einschränkung dürfen wir annehmen, dass
a
0 gilt. Wir bestimmen
durch sukzessive Division mit Rest im
i
-ten Schritt ganze Zahlen
r
i
,
q
i
,
x
i
,
y
i
mit
r
0
=
≥
b
>
b
,0
≤
r
i
<
r
i
−
1
und:
i
Division mit Rest
Darstellung
wobei
=
+
=
+
=
1
a
q
0
b
r
1
r
1
ax
1
by
1
1
y
1
=
−
x
1
q
0
2
b
=
q
1
r
1
+
r
2
r
2
=
ax
2
+
by
2
x
2
=
−
q
1
x
1
=
−
y
2
1
q
1
y
1
=
+
=
+
=
−
3
r
1
q
2
r
2
r
3
r
3
ax
3
by
3
x
3
x
1
q
2
x
2
y
3
=
y
1
−
q
2
y
2
.
.
.
=
+
=
+
=
−
k
r
k
−
1
q
k
r
k
r
k
+
1
r
k
ax
k
by
k
x
k
x
k
−
2
q
k
−
1
x
k
−
1
y
k
=
y
k
−
2
−
q
k
−
1
y
k
−
1
.
.
.
n
r
n
−
2
=
q
n
−
1
r
n
−
1
+
r
n
r
n
=
ax
n
+
by
n
x
n
=
x
n
−
2
−
q
n
−
1
x
n
−
1
=
−
y
n
y
n
−
2
q
n
−
1
y
n
−
1
+
=
+
=
n
1
r
n
−
1
q
n
r
n
r
n
+
1
r
n
+
1
0
Stop!
