Cryptography Reference
In-Depth Information
The advantage of the following algorithm based on these properties is
that it uses only size comparisons, subtractions, and shifts of
CLINT
objects,
operations that do not require a great deal of computational time and for which
we use efficient functions; above all, we need no divisions. The
binary
Euclidean
algorithm for calculating the greatest common divisor can be found in almost the
identical form in [Knut], Section 4.5.2, Algorithm B, and in [Cohe], Section 1.3,
Algorithm 1.3.5.
Binary Euclidean algorithm for calculating
gcd(
a, b
)
for
a, b ≥
0
1.
If
a<b
, exchange the values of
a
and
b
.If
b
=0
, output
a
and terminate
the algorithm. Otherwise, set
k ←
0
, and as long as
a
and
b
are both even,
set
k
←
k
+1
,
a
←
a/
2
,
b
←
b/
2
. (We have exhausted property (i);
a
and
b
are now no longer both even.)
2.
As long as
a
is even, set repeatedly
a ← a/
2
until
a
is odd. Or else, if
b
is
even, set repeatedly
b
b/
2
until
b
is odd. (We have exhausted property
(ii);
a
and
b
are now both odd.)
←
3.
Set
t ←
(
a − b
)
/
2
.If
t
=0
, output
2
k
a
and terminate the algorithm. (We
have used up properties (ii), (iii), and (iv).)
4.
As long as
t
is even, set repeatedly
t ← t/
2
, until
t
is odd. If
t>
0
, set
a ← t
;
otherwise, set
b
←−
t
; and go to step 3.
This algorithm can be translated step for step into a programmed function,
where we take the suggestion from [Cohe] to execute in step 1 an additional
division with remainder and set
r
r
. We thereby
equalize any size differences between the operands
a
and
b
that could have an
adverse effect on the running time.
←
a
mod
b
,
a
←
b
,and
b
←
Function:
greatest common divisor
void gcd_l (CLINT aa_l, CLINT bb_l, CLINT cc_l);
Syntax:
aa_l, bb_l
(operands)
Input:
cc_l
(greatest common divisor)
Output:
