Optimization-factoring $\le_p$ Decision-factoring
-
16-10-2019 - |
Question
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?
Solution
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)$.
OTHER TIPS
You can use the decision version to search for the factors of $N$ by manipulating $k$. Given the input to the optimization version, you can ask if it has a prime factor less than or equal to $2$, $3$, ..., $\sim\sqrt{N}$ . Say you get your first answer at $k_{1}$, then because it didn't say yes before, $k_{1}$ must be a factor of $N$, so we can note this down, and start again from $\frac{N}{k_{1}}$.
Ideally we'd only test the primes up to $\sim\sqrt{N}$, but it doesn't matter if we test the composites as well, as we'll hit their prime factors first, so we'll never get a Yes answer for a composite.
Then for each individual search we're solving at most $\sqrt{N}$ decision problems, and at each step (until we're done) we're reducing $N$ to less than $\frac{N}{2}$, so if we can solve the decision problem in PTIME (say $O(n^{c})$ for some constant $c$), we can do the whole thing in something roughly like $O(n^{c+1/2}\log n)$.