Optimization-factoring $\le_p$ Decision-factoring

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?

Answer 1

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

Answer 2

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