# Optimization-factoring $\le_p$ Decision-factoring

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?

• This question is a bit thin, and smacks like an exercise problem copied here. What have you tried, what are the specific problems you encountered? – Raphael Nov 26 '12 at 11:53

## 2 Answers

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)$.

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)$.

• The input $N$ is in binary so its size is $\log N$, and if you check $2,3,...\sim\sqrt{N}$ the running time can be exponential (if for example $N$ is prime). I think you should use a binary search on $k$ to get a polynomial bound on the number of queries. – Vor Nov 26 '12 at 0:46
• Yes, I forgot to mention the encoding issues, jmad seems to have covered it all in his answer. – Luke Mathieson Nov 26 '12 at 4:25