Cryptography Reference
In-Depth Information
k
p
min
(
e
i
,
f
i
)
i
gcd
(
a
,
b
)
=
i
=
1
However, this method is, again, unable to find, in general, the gcd of two integers
of several hundred digits each. The reason is that no algorithms are known that can
factor integers of this size in reasonable time (the largest 'difficult' integer factored
so far is one of 232 decimal digits and it took about 2.5 years to factor it using
Fortunately, there is a very efficient algorithm to compute the gcd which is able to
deal with very big numbers—even numbers much larger than the one just mentioned.
This is the Euclidean algorithm, the oldest nontrivial algorithm and hence, according
to Knuth [115], “
the granddaddy of all algorithms
”. In describing it (and throughout
the topic) we will denote by
a
mod
b
the remainder in the set
{
0
,
1
,...
b
−
1
}
of
dividing
a
by
b
, also called the
least non
-
negative residue
of
a
modulo
b
.
The basic fact underlying the Euclidean algorithm is the following:
Theorem 2.4
Let a
,
b
∈ Z
such that a
≥
b
>
0
. Then
gcd
(
a
,
b
)
=
gcd
(
b
,
amodb
)
.
The proof is a straightforward consequence of the obvious fact that
d
is a common
divisor of
a
and
b
if and only if
d
is a common divisor of
b
and
a
mod
b
.If
b
<
a
(otherwise
b
=
a
and gcd
(
a
,
b
)
=
a
) then, since
a
mod
b
<
b
, this theorem reduces
the computation of gcd
(
a
,
b
)
to computing the gcd of two strictly smaller numbers.
Setting
a
=
r
0
and
b
=
r
1
and repeating this process by computing the remainders
r
i
=
r
i
+
1
q
i
+
1
+
r
i
+
2
, with 0
≤
r
i
+
2
<
r
i
+
1
, we obtain a strictly decreasing sequence
of non-negative integers
a
=
r
0
>
r
1
>
r
2
>
··· ≥
0 and hence
r
n
+
1
=
0for
some index
n
≤
a
.If
n
is the least such index we have gcd
(
a
,
b
)
=
gcd
(
r
0
,
r
1
)
=
gcd
r
n
.
We have just described the Euclidean algorithm, which can be given in pseudocode
as a recursive function that calls itself:
(
r
1
,
r
2
)
=
...
gcd
(
r
n
,
0
)
=
Algorithm 2.1. Euclidean algorithm
(recursive version).
recgcd
:
Input
:Integers
a
≥
b
≥
0, not both 0.
Output
:gcd
(
a
,
b
)
.
if
b
0
then
return
a
else
recgcd
(
=
b
,
a
mod
b
)
end if
.
An alternative to the recursive version is the iterative version given in Algorithm
2.2.
Maple has a built-in function called
igcd
for computing the gcd of two integers.
This function is fast and we use it in many of our functions throughout the topic.
