Cryptography Reference
In-Depth Information
Euclidean algorithm for calculating
gcd(
a, b
)
for
a, b
≥
0
1.
If
b
=0
, output
a
and terminate the algorithm.
2.
Set
r
←
a
mod
b
,
a
←
b
,
b
←
r
, and go to step 1.
For natural numbers
a
1
,a
2
the calculation of the greatest common divisor
according to the Euclidean algorithm goes as follows:
a
1
=
a
2
q
1
+
a
3
,
0
≤ a
3
<a
2
,
a
2
=
a
3
q
2
+
a
4
,
0
≤
a
4
<a
3
,
a
3
=
a
4
q
3
+
a
5
,
0
≤ a
5
<a
4
,
.
a
m
−
2
=
a
m
−
1
q
m
−
2
+
a
m
,
0
≤
a
m
<a
m
−
1
,
a
m
−
1
=
a
m
q
m
−
1
.
Result:
gcd(
a
1
,a
2
)=
a
m
.
We compute as an example
gcd(723
,
288)
:
723 = 288
·
2 + 147
,
288 = 147
·
1 + 141
,
147 = 141
·
1+6
,
141=6
23+3
,
6=3
·
2
.
·
Result:
gcd(723
,
288) = 3
.
This procedure works very well for calculating the greatest common divisor
or for letting a computer program do the work. The corresponding program is
short, quick, and, due to its brevity, provides few opportunities for error.
A consideration of the following properties of integers and of the greatest
common divisor indicates—at least theoretically—possibilities for improvement
for programming this procedure:
a
and
b
are even
⇒
gcd(
a, b
) = gcd(
a/
2
,b/
2)
·
2
.
(i)
a
is even and
b
is odd
⇒
gcd(
a, b
) = gcd(
a/
2
,b
)
.
(ii)
(10.2)
gcd(
a, b
) = gcd(
a − b, b
)
.
(iii)
a
and
b
are odd
⇒ a − b
is even and
|a − b| <
max(
a, b
)
.
(iv)
