Cryptography Reference
In-Depth Information
algorithm, then one may obtain more information than simply the greatest common
divisor. In fact, the
extended Euclidean algorithm
can be used to compute two
integers
x
and
y
that satisfy (3.1):
xa
+
yb
=
gcd
(
a, b
)
(3.1)
Note that the first equation of the previously mentioned series of
k
equations
can be written as
a
+
b
(
−
q
1
)=
r
1
If we multiply both sides of this equation with
q
2
,weget
aq
2
+
b
(
−
q
1
q
2
)=
r
1
q
2
.
Combining this equation with the second equation of the series, we get
a
(
−
q
2
)+
b
(1 +
q
1
q
2
)=
r
2
.
A similar calculation can be used to express each
r
i
for
i
=1
,
2
,...,k
as a
linear combination of
a
and
b
. In fact,
ax
i
+
by
i
=
r
i
(3.2)
where
x
i
and
y
i
are some integers. As explained earlier, we eventually reach the
point where
r
k
=0and
r
k−
1
represents
gcd
(
a, b
):
ax
k−
1
+
by
k−
1
=
r
k−
1
=
gcd
(
a, b
)
.
In essence, the extended Euclidean algorithm specifies a way to accumulate
the intermediate quotients to compute
x
k−
1
and
y
k−
1
. Like the Euclidean algorithm,
the extended Euclidean algorithm takes as input two integers
a
and
b
with
|
a
|≥|
b
|
and
a
=0, and computes as output two integers
x
and
y
that satisfy (3.1).
If we set
r
−
1
=
a
,
r
0
=
b
,
x
−
1
=1,
y
−
1
=0,
x
0
=0,and
y
0
=1, then the
i
th
equation of the previously mentioned series of
k
equations relates
r
i−
1
,
r
i
,and
r
i
+1
in the following way:
