Cryptography Reference
In-Depth Information
Step 4: Depending on the sign of
t_l
,wehave
t_l
allocated to
a_l
or
b_l
.
while (ISEVEN_L (t_l))
{
shr_l (t_l);
}
if (-1 == sign_of_t)
{
cpy_l (b_l, t_l);
}
else
{
cpy_l (a_l, t_l);
}
}
while (1);
}
Although the operations used are all linear in the number of digits of the
operands, tests show that the simple two-line greatest common divisor on page
168 is hardly slower as a FLINT/C function than this variant. Somewhat surprised
at this, we ascribe this situation, for lack of better explanation, to the efficiency of
our division routine, as well as to the fact that the latter version of the algorithm
requires a somewhat more complex structure.
The calculation of the greatest common divisor for more than two arguments
can be carried out with multiple applications of the function
gcd_l()
, since as we
showed above in (10.1)(iii) the general case can be reduced recursively to the case
with two arguments:
gcd (
n
1
,...,n
r
) = gcd (
n
1
,
gcd (
n
2
,...,n
r
))
.
(10.3)
With the help of the greatest common divisor it is easy to determine the
least
common multiple
(lcm) of two
CLINT
objects
a_l
and
b_l
. The least common
multiple of integers
n
1
,...,n
r
, all nonzero, is defined as the smallest element
of the set
m
n
i
divides
m, i
=1
,...,r
. Since it contains at least the
+
∈
N
|
product
i
=1
|n
i
|
, this set is nonempty. For two arguments
a, b ∈
Z
the least
common multiple can be computed as the absolute value of their product divided
by the greatest common divisor:
lcm(
a, b
)
·
gcd(
a, b
)=
|ab|.
(10.4)
We shall use this relation for the calculation of the least common multiple of
a_l
and
b_l
.
