Cheap and Secure Web Hosting Provider : See Now

# [Solved]: Optimization-factoring $\le_p$ Decision-factoring

, ,
Problem Detail:

Optimization factoring:
Input: $N\in \mathbb{N}$
Output: All prime factors of $N$

Decision factoring:
Input: $N, k\in \mathbb{N}$
Output: True iff $N$ has a prime factor of at most $k$

How can I solve the optimization problem in polynomial time if the decision problem is polynomially solvable?

You need to get an algorithm polynomial in $n$ where $n = \log N$ is the size of your input, i.e. the binary representation of $N$ (naive factorization algorithms are $O(N^2)$ which is of course exponential).

Given dec(k, x) solving the decision factoring problem, let's write a procedure to find the smallest prime divisor of $x$ using a dichotomy to keep logarithmic the number of steps.

sp(x):   min = 2   max = x - 1   while (max >= 1 + min):     k = floor ((min + max) / 2)     if dec(k, x):       max = k     else:       min = k + 1   if x % (min + 1) == 0:     return (min + 1)   else if x % min == 0:     return min   else:     return 1 

The procedure above calls dec $O(\log x)$ times and find the smallest prime number that divides $x$, or 1 if it does not exist. Now we can easily define the following factoring function:

factor(x):   p = sp(x)   if (p == 1):     print x   else:     print p     factor(x / p) 

Factor is called less than $\log x$ times (since $p ≥ 2$) so the number of calls to dec is bounded by $\log^2 x$ times on values less than $x$. If the complexity of dec is polynomial, let's say bounded by an increasing $P(n)$, then the complexity of factor is still polynomial, bounded by $n^2P(n)$.