Cryptography Reference
In-Depth Information
417884, 113832
113832, 76388
76388, 37444
37444, 1500
1500, 1444
1444, 56
56, 44
44, 12
12, 8
8, 4
4, 0
4
It is also straightforward to implement the iterative version of Euclid's algorithm
in Maple, closely following Algorithm 2.2:
> itergcd := proc(a, b, verbose := false)
local x, y, r;
x:=a;
y:=b;
while y <> 0 do
if verbose then
print(x,y)
end if;
r := x mod y;
x:=y;
y:=r;
end do;
x;
end proc:
We are going to analyze the complexity of the Euclidean algorithm and, as we are
going to see, the worst case is provided by consecutive Fibonacci numbers as was
proved by Lamé already in the mid-nineteenth century. TheFibonacci numbers are
defined by the linear recurrence
F
n
=
F
n
−
1
+
F
n
−
2
,
where
F
0
1. They can be computed in Maple by means of the
command
fibonacci
in the
combinat
package. To simplify the notation, we
define an alias for this command and we may use it as follows:
=
0 and
F
1
=
> alias(F = combinat:-fibonacci):
> F(1), F(10), F(100);
1, 55, 354224848179261915075
Let us identify the worst case in the complexity of the Euclidean algorithm:
>
>
Theorem 2.5
Assume a
b
0
and let r
n
be the last nonzero remainder in the
=
,
=
,...,
=
+
r
i
+
1
,...
sequence of integer divisions r
0
a
r
1
b
r
i
−
1
r
i
q
i
Then
a
≥
F
n
+
2
and b
≥
F
n
+
1
.
Proof
Note that, since the sequence of remainders is strictly decreasing,
r
i
−
1
>
r
i
>
r
i
+
1
for 1
≤
i
≤
n
and so
q
i
≥
1. Moreover, since
r
n
+
1
=
0, we have that
r
n
−
1
=
r
n
q
n
and so
q
n
≥
2 (for otherwise we would have
r
n
−
1
=
r
n
). Thus, working
backwards through the sequence of divisions we have that:
