16
$\begingroup$

I read somewhere that the most efficient algorithm found can compute the factors in $O(\exp((64/9 \cdot b)^{1/3} \cdot (\log b)^{2/3})$ time, but the code I wrote is $O(n)$ or possibly $O(n \log n)$ depending on how fast division and modulus are. I'm pretty sure I've misunderstood something somewhere, but I'm not sure where. Here's what I wrote in pseudo code form.

function factor(number) -> list
    factors = new list
    if number < 0
        factors.append(-1)
        number = -number
    i = 2
    while i <= number
        while number % i == 0
            factors.append(i)
            number /= i
        i++
    return factors
$\endgroup$
  • 3
    $\begingroup$ Google "pseudo polynomial". $\endgroup$ – Raphael Dec 5 '15 at 9:26
  • $\begingroup$ That algorithm is actually very slow - if number is a prime number the loop while iterate (number) times. There is a very simple argument that allows you getting away with sqrt (number) iterations. $\endgroup$ – gnasher729 Dec 5 '15 at 16:18
26
$\begingroup$

You are confusing the number $n$ with the number of bits needed to represent $n$. Here $b = $ the number of bits needed to represent $n$ (so $b \approx \lg n$). This makes a huge difference. A $O(n)$-time algorithm is a $O(2^b)$-time algorithm -- exponential in the number of bits. In comparison, the "efficient" algorithm you found has a running time that is subexponential in $b$.

Example: Consider $n = 2,000,000$ (2 million). Then $b=21$ bits are enough to represent the number $n$. So, an algorithm that is $O(2^{b^{1/3}})$ will be much faster than an algorithm that is $O(2^b)$. An $O(n)$ algorithm falls into the latter category, i.e., very slow.

See https://en.wikipedia.org/wiki/Integer_factorization

$\endgroup$
  • 1
    $\begingroup$ I knew it was something simple like that. $\endgroup$ – EnderShadow Dec 5 '15 at 5:57
  • 3
    $\begingroup$ @EnderShadow: Also, the kind of numbers whose factoring is considered hard using currently available hardware, and used e.g. in RSA encryption, have $b > 1{,}000$ (i.e. $n > 2^{1{,}000}$) or so. As an exercise, assuming that you computer can run your $O(n)$ algorithm at, say, one billion iterations per second, calculate how many years it would take to factor $n \approx 2^{1{,}000}$. (If your initial reaction is "that can't be right!", you've probably calculated it correctly.) $\endgroup$ – Ilmari Karonen Dec 5 '15 at 12:51
1
$\begingroup$

you have roughly two questions here, a general and a specific one about your code. the specific one is handled in the other answer. the general question in the title about the complexity of factoring is very deep. unfortunately there is not strong scientific evidence that factoring is outside of P other than (the mostly circumstantial) "lots of experts have tried and failed" and some experts conjecture it is inside P; its regarded as one of the foremost (and very hard to resolve) open problems of complexity theory. after decades of "heavy attack" the best algorithms are exponential. factoring complexity is one of the "few exceptional problems" that is known to lie "between" P and NP complete but has not been classified as either so far.

as is pointed out, the complexity was not much of an issue until it became used ("roughly") in the RSA cryptosystems in the mid 1980s where cryptographic security depends on the assumption. (two other "not-exactly-encouraging" related datapoints: Shors algorithm for P-time quantum factoring and primality testing was proven to be in P in the early 2000s in the famous/ celebrated AKS algorithm.) a possible positive outcome would be that its in quasipolynomial time, which is weaker than NP complete (assuming P≠NP and NP complete has an exponential time lower bound) but still technically "hard".

have not found a great survey on this key subj so far. however see also

$\endgroup$
  • $\begingroup$ another possible somewhat seemingly "edge-case" scenario is that factoring could be in P but there is still no feasible algorithm. aka galactic algorithms $\endgroup$ – vzn Dec 6 '15 at 19:33
  • $\begingroup$ It should be mentioned that RSA is about factoring the product of two large primes (where someone knows the primes and just multiplied them, and someone else is given the product and is supposed to find the primes). It is conceivable that there might be an algorithm that can factor products of two large primes, but not products of more than two large primes. Just as factoring numbers that are large primes (but not known beforehand to be large primes) can be done in polynomial time. $\endgroup$ – gnasher729 Apr 8 '17 at 14:33

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.