Cryptography Reference
In-Depth Information
test = n_l[l];
l <<= LDBITPERDGT;
while ((test & BASEDIV2) == 0)
{
test <<= 1;
--l;
}
return l;
}
We then calculate the integer part of the square root of a natural number
based on the classical method of Newton (also known as the Newton-Raphson
method), which is used for determining the zeros of a function by successive ap-
proximation: We assume that a function
f
(
x
)
is twice continuously differentiable
on an interval
[
a, b
]
, that the first derivative
f
(
x
)
is positive on
[
a, b
]
, and that we
have
f
(
x
)
·
f
(
x
)
f
(
x
)
2
max
[
a,b
]
<
1
.
Then if
x
n
∈
[
a, b
]
is an approximation for a number
r
with
f
(
r
)=0
,then
x
n
+1
:=
x
n
f
(
x
n
)
/f
(
x
n
)
is a better approximation of
r
. The sequence
defined in this way converges to the zero
r
of
f
(cf. [Endl], Section 7.3).
If we set
f
(
x
):=
x
2
−
− c
with
c>
0
, then
f
(
x
)
for
x>
0
satisfies the above
conditions for the convergence of the Newton method, and with
x
n
+
f
(
x
n
)
=
1
f
(
x
n
)
c
x
n
x
n
+1
:=
x
n
−
2
we obtain a sequence that converges to
√
c
. Due to its favorable convergence
behavior Newton's method is an efficient procedure for approximating square
roots of rational numbers.
Since for our purposes we are interested in only the integer part
r
of
√
c
,
for which
r
2
≤ c<
(
r
+1)
2
holds, where
c
itself is assumed to be a natural
number, we can limit ourselves to computing the integer parts of t
h
e elements of
the sequence of approximations. We begin with a number
x
1
>
√
c
and continue
until we obtain a value greater than or equal to its predecessor, at which point the
predecessor is the d
e
sired value. It is naturally a good idea to begin with a number
that is as close to
√
c
as possible. For a
CLINT
object with value
c
and
e
:=
log
2
c
we have that
2
(
e
+2)
/
2
is always greater than
√
c
, and furthermore, we can
easily calculate it with the function
ld_l()
. The algorithm goes as follows.
