Cryptography Reference
In-Depth Information
gcd(
r
0
,
r
1
)=gcd(
r
0
−
r
1
,
r
1
)
,
where we assume that
r
0
>
r
1
, and that both numbers are positive integers. This
property can easily be proven: Let gcd(
r
0
,
r
1
)=
g
. Since
g
divides both
r
0
and
r
1
,
we can write
r
0
=
g
y
, where
x
>
y
, and
x
and
y
are coprime integers,
i.e., they do not have common factors. Moreover, it is easy to show that (
x
·
x
and
r
1
=
g
·
−
y
) and
y
are also coprime. It follows from here that:
gcd(
r
0
−
r
1
,
r
1
)=gcd(
g
·
(
x
−
y
)
,
g
·
y
)=
g
.
Let's verify this property with the numbers from the previous example:
Example 6.2.
Again, let
r
0
= 84 and
r
1
= 30. We now look at the gcd of (
r
0
−
r
1
)
and
r
1
:
r
0
−
r
1
= 54 = 2
·
3
·
3
·
3
r
1
= 30 = 2
·
3
·
5
The largest common factor still is 2
·
3 = 6 = gcd(30
,
54)=gcd(30
,
84).
It also follows immediately that we can apply the process iteratively:
gcd(
r
0
,
r
1
)=gcd(
r
0
−
r
1
,
r
1
)=gcd(
r
0
−
2
r
1
,
r
1
)=
···
−
mr
1
,
r
1
)
= gcd(
r
0
as long as (
r
0
mr
1
)
>
0. The algorithm uses the fewest number of steps if we
choose the maximum value for
m
. This is the case if we compute:
−
gcd(
r
0
,
r
1
)=gcd(
r
0
mod
r
1
,
r
1
)
.
Since the first term (
r
0
mod
r
1
) is smaller than the second term
r
1
, we usually swap
them:
gcd(
r
0
,
r
1
)=gcd(
r
1
,
r
0
mod
r
1
)
.
The core observation from this process is that we can
reduce the problem of
finding the gcd of two given numbers to that of the gcd of two smaller numbers.
This process can be applied recursively until we obtain finally gcd(
r
l
,
0)=
r
l
. Since
each iteration preserves the gcd of the previous iteration step, it turns out that this
final gcd is the gcd of the original problem, i.e.,
gcd(
r
0
,
r
1
)=
···
= gcd(
r
l
,
0)=
r
l
.
We first show some examples for finding the gcd using the Euclidean algorithm and
then discuss the algorithm a bit more formally.
Example 6.3.
Let
r
0
= 27 and
r
1
= 21. Fig. 6.6 gives us some feeling for the al-
gorithm by showing how the lengths of the parameters shrink in every iteration.
The shaded parts in the iteration are the new remainders
r
2
= 6 (first iteration), and
r
3
= 3 (second iteration) which form the input terms for the next iterations. Note