Cryptography Reference
In-Depth Information
3.2.3
Euclidean Algorithms
In Section 3.2.5 we see how one can compute the greatest common divisor of two
integers if their prime factorization is known. It is, however, not necessary to know
the prime factorization of two integers to compute their greatest common divisor.
In fact, the
Euclidean algorithm
(or
Euclid's algorithm
) can be used to compute
the greatest common divisor of two integers
a, b
∈
Z
\{
0
}
with unknown prime
factorization.
14
Theorem 3.3 says that for two nonzero integers
a
≥
b
, we can always write
a
=
bq
+
r
for some quotient
q
r<b
. Because by definition,
gcd
(
a, b
) divides both
a
and
b
, the above equation shows that it must also divide
r
.
Consequently,
gcd
(
a, b
) equals
gcd
(
b, r
), and because the remainder
r
of
a
divided
by
b
is denoted by
a
mod
b
, we can say
≤
=0and remainder 0
gcd
(
a, b
)=
gcd
(
b, a
mod
b
)=
gcd
(
b, R
b
(
a
))
.
This equation can be recursively applied to compute
gcd
(
a, b
). For example,
gcd
(100
,
35) can be computed as follows:
gcd
(100
,
35)
=
gcd
(35
,R
35
(100))
=
gcd
(35
,
30)
=
gcd
(30
,R
30
(35))
=
gcd
(30
,
5)
=
gcd
(5
,R
5
(30))
=
gcd
(5
,
0)
=5
.
This way of computing
gcd
(
a, b
) is at the core of the Euclidean algorithm. If
we consider the following series of
k
equations:
a
=
bq
1
+
r
1
14
The Euclidean algorithm is one of the oldest algorithms known; it appeared in Euclid's
Elements
around 300 B.C.
