Cryptography Reference
In-Depth Information
The factorization problem can be reduced to the corresponding search problem
in the sense that there is a polynomial-time algorithm to transform an algorithm
to solve the second problem into an algorithm to solve the first. In order to obtain
the factorization of n we would repeatedly call the search algorithm to find factors
of n until obtaining all the factors, i.e., the search algorithm would act as a sub-
routine of the factoring algorithm. The important thing is that, since clearly the
number of prime factors of n is O
, the search algorithm must be called a
number of times which is polynomial in the size of n (and the factoring algorithm
also has to do the corresponding divisions by the factors found). This means that
solving the factorization problem is no harder than solving the search problem, up
to a polynomial-time amount of computation. As we shall see, the numbers for
which the factorization problem has cryptologic interest are the product of just two
primes and, in this case, the factorization algorithm has the same running time as the
search algorithm.
Since the definitions of
(
len
(
n
))
refer to decision problems, we will now
consider the integer factorization decision problem (see, e.g., [119]) which asks,
given positive integers n
P
and
NP
,
k with k
<
n , if there exists a factor a of n such that 2
a
k . Again, we can see that the search factorization problem (and hence also the
factorization problem) is reducible in polynomial time to the corresponding decision
problem. In this case, the reduction process consists of applying a binary search
to pinpoint a nontrivial factor (actually the smallest one) by calling the algorithm
solving the decision problem O
,so
that 2 l is the smallest power of 2 which is greater than n . We first call the decision
problem algorithm with k
(
len
(
n
))
times. Indeed, suppose that l
=
len
(
n
)
2 l 1
=
1. If the answer is 'no', i.e., if n does not have
nontrivial factors
k , then we know that n is prime and we are done, otherwise we
call the decision algorithm again with k
2 l 2
=
1. If the answer is 'yes' then we
know that n has a factor whose binary length is
<
l
1 whereas if the answer is
'no', then it has a factor of length l
1. Thus we have determined the bit d l 2 of the
binary expansion d l 2 d l 3 ...
d 1 d 0 of the factor, which is 0 in the first case and 1
in the second. We continue calling the decision problem, each time halving the size
of the interval where the nontrivial factor of n must lie by taking the midpoint of
the previous interval as the value of k , so that the factor is in the lower half interval
if the answer is 'yes' and in the upper half if the answer is 'no'. Thus the next
bit, d l 3 , is determined by calling the decision algorithm again with k
2 l 3
1
(in case the previous application of the algorithm gave a 'yes' answer) and with
k
=
2 l 2
2 l 3
=
+
1 (in case the previous answer was 'no'). Again, a 'yes' answer
means that d l 3 =
1 and, after calling the algorithm
l times, we will have computed the binary expansion of the smallest nontrivial factor
of n (in case n is not prime).
Observe that the first call to the decision algorithm (with k
0 and a 'no' answer that d l 3 =
2 l 1
1) is only
to determine whether n is prime or not, and in this case one would rather apply a
primality test which is usually much faster than a factoring algorithm: before trying
to factor a number one should already know that the number is not prime. Finally,
note that, since the factorization search algorithm requires O
=
(
len
(
n
))
calls to the
 
Search WWH ::




Custom Search