Cryptography Reference
In-Depth Information
l = (ld_l (n_l) + 1) >> 1;
SETZERO_L (y_l);
setbit_l (y_l, l);
do
{
cpy_l (x_l, y_l);
Steps 2 and 3. Newton approximation and checking for termination.
div_l (n_l, x_l, y_l, r_l);
add_l (y_l, x_l, y_l);
shr_l (y_l);
}
while (LT_L (y_l, x_l));
cpy_l (floor_l, x_l);
}
A generalization of the procedure makes possible the calculation of the
integer part of the
b
th root of
n
, i.e.,
n
1
/b
, for
b >
1
(see [CrPa], page 3):
Algorithm for calculating the integer part of a
b
th root
1.
Set
x ←
2
ld_l
(
n
)
/b
.
2.
Set
y ←
(
b −
1)
x
+
n/x
b
−
1
/b
. If
y < x
, set
x ← y
and repeat
step 2.
3.
Output
x
as result and terminate the algorithm.
The implementation of the algorithm uses exponentiation modulo
N
max
for
the integer power in
x
b
−
1
in step 2:
integer part of the
b
th root of a
CLINT
object
n_l
Function:
int
introot_l(CLINT n_l, USHORT b, CLINT floor_l);
Syntax:
n_l, b
(operands,
b
>
0
)
Input:
floor_l
(integer part of the
b
th root of
n_l
)
Output:
