Cryptography Reference
In-Depth Information
The Euclidean algorithm is very efficient, even with the very long numbers typi-
cally used in public-key cryptography. The number of iterations is close to the num-
ber of digits of the input operands. That means, for instance, that the number of
iterations of a gcd involving 1024-bit numbers is 1024 times a constant. Of course,
algorithms with a few thousand iterations can easily be executed on today's PCs,
making the algorithms very efficient in practice.
6.3.2 Extended Euclidean Algorithm
So far, we have seen that finding the gcd of two integers
r
0
and
r
1
can be done
by recursively reducing the operands. However, it turns out that finding the gcd is
not the main application of the Euclidean algorithm. An extension of the algorithm
allows us to compute modular inverses, which is of major importance in public-key
cryptography. In addition to computing the gcd, the
extended Euclidean algorithm
(EEA) computes a linear combination of the form:
gcd(
r
0
,
r
1
)=
s
·
·
r
0
+
t
r
1
where
s
and
t
are integer coefficients. This equation is often referred to as
Diophan-
tine equation
.
The question now is: how do we compute the two coefficients
s
and
t
? The idea
behind the algorithm is that we execute the standard Euclidean algorithm, but we
express the current remainder
r
i
in every iteration as a linear combination of the
form
r
i
=
s
i
r
0
+
t
i
r
1
.
(6.1)
If we succeed with this, we end up in the last iteration with the equation:
r
l
= gcd(
r
0
,
r
1
)=
s
l
r
0
+
t
l
r
1
=
sr
0
+
tr
1
.
This means that the last coefficient
s
l
is the coefficient
s
in Eq. (6.1) we are looking
for, and also
t
l
=
t
. Let's look at an example.
Example 6.5.
We consider the extended Euclidean algorithm with the same values as
in the previous example,
r
0
= 973 and
r
1
= 301. On the left-hand side, we compute
the standard Euclidean algorithm, i.e., we compute new remainders
r
2
,
r
3
,...
.Also,
we have to compute the integer quotient
q
i
−
1
in every iteration. On the right-hand
side we compute the coefficients
s
i
and
t
i
such that
r
i
=
s
i
r
0
+
t
i
r
1
. The coefficients
are always shown in brackets.
