Cryptography Reference
In-Depth Information
Algorithm 2.2. Euclidean algorithm
(iterative version).
Input
:Integers
a
≥
b
>
0.
Output
:gcd
(
a
,
b
)
.
while
b
>
0
r
:=
a
mod
b
a
:=
b
r
end while
return
a
.
b
:=
However, for illustrative purposes, we next give simple implementations of the two
versions of the Euclidean algorithm we have just seen. The recursive version of the
Euclidean algorithm is implemented in the Maple function
recgcd
below, which is
an almost verbatim transliteration of Algorithm 2.1. In order to visualize the numbers
to which the algorithm is being applied in the successive steps, we include an optional
parameter
verbose
which, if set to
true
, makes the function print these pairs of
integers on screen:
> recgcd := proc(a::nonnegint, b::nonnegint, verbose := false)
if verbose then
print(a,b)
end if;
ifb=0then
return a
end if;
recgcd(b, a mod b, verbose);
end proc:
Example 2.7
Let us use
recgcd
to compute the gcd of two numbers:
> recgcd(387349873729876, 4896209096872);
4
We will see that the number of steps in applying the Euclidean algorithm to two
integers is relatively small and, because of this fact, the algorithm is very efficient.
This claim will be made precise when studying the algorithm's complexity but now
we use the numbers above to give intuition about these steps. We visualize the
recursive calls on screen as follows:
> recgcd(387349873729876, 4896209096872, true);
387349873729876, 4896209096872
4896209096872, 549355076988
549355076988, 501368480968
501368480968, 47986596020
47986596020, 21502520768
21502520768, 4981554484
4981554484, 1576302832
1576302832, 252645988
252645988, 60426904
60426904, 10938372
10938372, 5735044
5735044, 5203328
5203328, 531716
531716, 417884
