Cryptography Reference
In-Depth Information
Algorithm for determining the integer part
r
of the square root of a natural
number
n>
0
2
(
e
+2)
/
2
with
e
:=
log
2
n
1.
Set
x ←
.
2.
Set
y ←
(
x
+
n/x
)
/
2
.If
y<x
, set
x ← y
and repeat step 2.
3.
Output
x
and terminate the algorithm.
The proof of the correctness of this algorithm is not particularly difficult.
The value of
x
decreases monotonically, and it is an integer and always positive,
so that the algorithm certainly terminates. When this occurs, the condition
y
=
(
x
+
n/
x
)
/
2
≥x
holds, and we assume that
x ≥ r
+1
.From
x ≥ r
+1
>
√
n
it follows that
x
2
>n
,or
n − x
2
<
0
.
However,
− x
=
n
<
0
,
x
2
2
x
y − x
=
(
x
+
n/x
)
2
−
in contradiction to the condition for terminating the process. Our assertion is
therefore false, and we must have
x
=
r
. The following function, for determining
the integer part of the square root, uses integer division with remainder for the
operation
y ←
(
x
+
c/x
)
/
2
without putting the validity of the procedure at
risk.
integer part of the square root of a
CLINT
object
Function:
void iroot_l(CLINT n_l, CLINT floor_l);
Syntax:
n_l
(operand
>
0
)
Input:
Output:
floor_l
(integer square root of
n_l
)
void
iroot_l (CLINT n_l, CLINT floor_l)
{
CLINT x_l, y_l, r_l;
unsigned l;
function
ld_l()
and
operation
l
is
With
the
a
shift
set
to
the
value
,and
y_l
is set to
2
l
with the help of
setbit_l()
.
(
log
2
(
n_l
)
+2)
/
2
