Cryptography Reference
In-Depth Information
10.3 Roots and Logarithms
In this section we shall develop functions for calculating the integer part of square
roots and logarithms to base 2 of
CLINT
objects. To this end we first consider
the latter of these two functions, since we will need it for the first of them: For
a natural number
a
we are seeking a number
e
for which
2
e
a<
2
e
+1
.The
≤
number
e
=
log
2
a
is the integer part of the logarithm of
a
to the base 2 and
is easily obtained from the number of relevant bits of
a
, as determined from the
following function
ld_l()
, reduced by 1. The function
ld_l()
, which is used in
many other functions of the
FLINT/C
package, disregards leading zeros and counts
only the relevant binary digits of a
CLINT
object.
number of relevant binary digits of a
CLINT
object
Function:
unsigned int ld_l (CLINT n_l);
Syntax:
Input:
n_l
(operand)
number of relevant binary digits of
n_l
.
Return:
unsigned int
ld_l (CLINT n_l)
{
unsigned int l;
USHORT test;
Step 1: Determine the number of relevant digits to the base
B
.
l = (unsigned int) DIGITS_L (n_l);
while (n_l[l] == 0 &&l>0)
{
--l;
}
if (l == 0)
{
return 0;
}
Step 2: Determine the number of relevant bits of the most-significant digit. The
macro
BASEDIV2
defines the value of a digit that has a 1 in the most-significant bit
and otherwise contains 0 (that is,
2
BITPERDGT
−
1
).
