World's most popular travel blog for travel bloggers.

# [Solved]: Complexity of factoring products of distinct prime numbers

, ,
Problem Detail:

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.

#### Answered By : Yuval Filmus

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