Cryptography Reference
In-Depth Information
It is beyond the scope of this topic to give all applications of Newton's method for fast
arithmetic. Instead, we briefly mention some complexity results.
First, one can use Newton's method to compute rational approximations to 1
/a
∈ Q
of
the form
b/
2
e
. The complexity to get an approximation such that
<
1
/
2
m
is
O
(
M
(
m
)) bit operations. For details see Section 3.5 of [
497
] (especially Exercise 3.35),
Chapter 9 of [
220
] or, for a slightly different formulation, Section 9.2.2 of [
150
]. For
applications of this idea to efficient modular arithmetic see Section
2.5
or Section 10.5
of [
16
]; an important result is that one can compute
a
(mod
b
), where
a
and
b
are
m
-bit
integers, in
O
(
M
(
m
)) bit operations.
Another application is to compute integer roots of polynomials
F
(
x
)
b/
2
e
|
1
/a
−
|
∈ Z
[
x
]. One uses
∈ R
Newton's method to find an approximation to a root
x
, and then rounds to the nearest
integer. As a special case, integer square roots of
m
-bit numbers can be computed in
O
(
M
(
m
)) bit operations. Similarly, other roots (such as cube roots) can be computed in
polynomial-time. It follows that one can test, in polynomial-time, whether an integer is a
perfect power
(i.e., whether the integer is
a
m
for some
a,m
∈ N
,
m>
1).
p
e
where
p
is prime and
e
Exercise 2.2.7
Show that if
N
=
≥
1 then one can factor
N
in
polynomial-time.
2.3 Euclid's algorithm
For
a,b
∈ N
, Euclid's algorithm computes
d
=
gcd(
a,b
). A simple way to express Euclid's
algorithm is by the recursive formula
gcd(
a,
0)
a
gcd(
b,a
(mod
b
))
=
gcd(
a,b
)
=
if
b
=
0
.
The traditional approach is to work with positive integers
a
and
b
throughout the algorithm
and to choose
a
(mod
b
)tobeintheset
{
0
,
1
,...,b
−
1
}
. In practice, the algorithm can
be used with
a,b
∈ Z
and it runs faster if we choose remainders in the range
{−|
b
|
/
2
+
1
,...,
−
1
,
0
,
1
,...,
|
b
|
/
2
}
. However, for some applications (especially, those related
to
diophantine
approximation)
the
version
with
positive
remainders
is
the
desired
choice.
In practice, we often want to compute integers (
s,t
) such that
d
bt
, in which
case we use the extended Euclidean algorithm (due to Lagrange). This is presented in
Algorithm
1
, where the integers
r
i
,s
i
,t
i
always satisfy
r
i
=
=
as
+
s
i
a
+
t
i
b
.
Theorem 2.3.1
The complexity of Euclid's algorithm is O
(log(
a
) log(
b
))
bit operations.
Proof
Each iteration of Euclid's algorithm involves computing the quotient and remainder
of division of
r
i
−
2
by
r
i
−
1
where we may assume
|
r
i
−
2
|
>
|
r
i
−
1
|
(except maybe for
i
=
1).
