3
$\begingroup$

Problem: Input is an integer number $x$ that we know factors as $p_{i_1}\cdot p_{i_2}\ldots p_{i_n}$, where the $p_{i_j}$'s are distinct prime numbers. Output is the above factorization of $x$.

Do you know any results/references for the time complexity of this factoring problem?

Note: If the $p_{i_j}$'s are not assumed distinct, then the problem is just integer factorization. This is a very special case.

$\endgroup$
  • 2
    $\begingroup$ It's not such a special case. Factoring algorithms are often evaluated according to their handling the case of $x = pq$ where $|p| \approx |q|$. $\endgroup$ – Yuval Filmus May 2 '14 at 17:37
  • $\begingroup$ @Yuval: Factoring x=pq is even more special case than what I am asking here. I am assuming that evaluating algorithms on such integers stems from cryptography. Can you provide any results/references for the complexity of factoring x=pg? $\endgroup$ – Ioannis Souldatos May 2 '14 at 19:25
4
$\begingroup$

As far as I know, there are no non-trivial lower bounds on factoring, and in particular, no variant is conjectured to be NP-hard. (While factoring is not a decision problem per se, you can make up a corresponding decision problem that gives the $k$bit of the $\ell$th smallest factor.)

As far as algorithms go, there are a great many of them, including the following subexponential ones:

  1. Quadratic sieve: this factors an integer $n$ in time $2^{O(\sqrt{\log n\log\log n})}$. There are many variants of this algorithm resulting in different constants for the big O, and one of them (due to Dixon) provably has the stated running time.

  2. Elliptic curve method: this factors an integer $n$ with smallest prime factor $p$ in time $2^{O(\sqrt{\log p \log\log p})}$ (in general, this is the time it takes to find the factor $p$ rather than the complete factorization). No variant of this algorithm has a provable running time guarantee. The algorithm relies on the fact that random elliptic curves modulo $p$ have a certain order (number of points) distribution, and this empirically verifiable property isn't proven. (What you really need to know is the probability that the order is $\alpha$-smooth, whose conjectured behavior is satisfied for any reasonably smooth probability distribution.)

  3. Number-field sieve: this factors an integer $n$ in time $2^{O(\sqrt[3]{\log n (\log \log n)^2})}$. No variant of this algorithm has a provable running time guarantee. The algorithm relies on the probability that a random element of a number field is smooth (in terms of its norm), a property which can be empirically verified but is unproven.

In practice, one first runs simpler algorithm which are able to find small prime factors more quickly. Some of the algorithms might run into problem if all prime factors are repeated, which is ruled out by your constraints, but I can't think of any concrete example.

There is no consensus on the conjectured complexity of the problem. Recent advances in the related discrete logarithm problem suggest that factoring might be in quasipolynomial time, and some people (Charles Rackoff, for example) wouldn't even rule out a polynomial algorithm for factoring. Others would concede that the number-field sieve algorithm might not be optimal, but that factoring should require time $2^{\Omega((\log n)^c)}$ for some $c > 0$.

$\endgroup$
  • $\begingroup$ Sorry I was gone for the weekend. I understand that these are bounds for the general integer factoring problem, not for the special case. Does this mean that the special case has not been investigated on its own? $\endgroup$ – Ioannis Souldatos May 5 '14 at 12:22
  • $\begingroup$ I am a little sceptical about the elliptic curve method. If the complexity depends on the smallest prime, then instead of factoring x, consider factoring 2x and the smallest prime is equal to 2. This means a constant bound for factoring? I do not think so. $\endgroup$ – Ioannis Souldatos May 5 '14 at 12:27
  • 1
    $\begingroup$ @IoannisSouldatos Regarding your first question, your special case is assumed to be the hardest case. Regarding your second question: First, it takes time $2^{O(\sqrt{\log p\log\log p})}$ to find the first prime factor. If you try to factor $2x$ you might find the factor $2$ and you're back where you started. Second, there is some polynomial dependency on $n$, i.e., the running time is really $2^{O(\sqrt{\log p\log\log p})} (\log n)^{O(1)}$. $\endgroup$ – Yuval Filmus May 5 '14 at 13:33
  • $\begingroup$ Thank you for the answer and comments. I accepted your answer. I can not see why the special case is the hardest. Can you please explain? $\endgroup$ – Ioannis Souldatos May 5 '14 at 14:35
  • 1
    $\begingroup$ @IoannisSouldatos I'm not aware of any formal sense in which your case is the hardest, but intuitively small prime factors are easier to find, so the hardest case is two large factors of roughly the same size. If you're curious, you can check my survey cs.toronto.edu/~yuvalf/Factorization.pdf, which unfortunately doesn't list the numerous sources I had consulted. There must be many survey articles on the subject, look up integer factorization algorithms in your favorite search engine. $\endgroup$ – Yuval Filmus May 5 '14 at 14:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.