Cryptography Reference
In-Depth Information
that in the last iteration the remainder is
r
4
= 0, which indicates the termination of
the algorithm.
21
6
gcd(27, 21) = gcd(1 21+6, 21) = gcd(21, 6)
gcd(21, 6) = gcd(3 6+3, 6) = gcd(6, 3)
6
6
6
3
gcd(6, 3) = gcd(2 3+0, 3) = gcd(3, 0) = 3
3
3
gcd(27, 21) = gcd(21, 6) = gcd(6, 3) = gcd(3, 0) = 3
Fig. 6.6
Example of the Euclidean algorithm for the input values
r
0
= 27 and
r
1
= 21
It is also helpful to look at the Euclidean algorithm with slightly larger numbers, as
happens in Example 6.4.
Example 6.4.
Let
r
0
= 973 and
r
1
= 301. The gcd is then computed as
973 = 3
·
301 + 70 gcd(973
,
301) = gcd(301
,
70)
301 = 4
·
70 + 21
gcd(301
,
70)
= gcd(70
,
21)
70
= 3
·
21 + 7
gcd(70
,
21)
= gcd(21
,
7)
·
gcd(21
,
7)
= gcd(7
,
0)=7
21
= 3
7 + 0
By now we should have an idea of Euclid's algorithm, and we can give a more
formal description of the algorithm.
Euclidean Algorithm
Input
: positive integers
r
0
and
r
1
with
r
0
>
r
1
Output
: gcd(
r
0
,
r
1
)
Initialization
:
i
= 1
Algorithm
:
1
O
1.1
i
=
i
+ 1
1.2
r
i
=
r
i
−
2
mod
r
i
−
1
WHILE
r
i
= 0
2
RETURN
gcd(
r
0
,
r
1
)=
r
i
−
1
Note that the algorithm terminates if a remainder with the value
r
i
= 0 is com-
puted. The remainder computed in the previous iteration, denoted by
r
l
−
1
, is the gcd
of the original problem.
