notAboAlmanalAnyMore's blog

finding the factorization of an integer N in O(log2(n)), is it possible?

By notAboAlmanalAnyMore, history, 4 years ago, In English

Hello everyone, I was trying to solve CSES — Sum of Divisors and finally found a solution within a complexity of O(sqrt(N)), and it worked. However, the problem intrigued my interested so I searched about it on Google, and came across this article explaining a solution to the same problem but with a complexity of O(log2(n))! the observations mentioned in the article are exactly the same I used to build-up my solution, but I don't understand how they consider it as O(log2(n)) or if they are doing something different with the code that I don't get.

[SPOILER]
In regards of the problem, the main observation is that there are segments of numbers that within each segment, theses numbers will have the same number of occurrences in the total answer. In addition, the number of theses segments is equal to the number of factors of N. In conclusion, the problem is about finding the factorization of the number N (as I guess)

So, what is the most efficient way to find the factorization of a number N? what is the most efficient way to solve the problem? is there anything I am missing with the blog mentioned above?

Thanks in advance!

  • Vote: I like it
  • +12
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

No, you cannot factor a number in O(number length), or even in any polynomial of number length. At least, no one knows how to do that. The quickest known algorithm is general number field sieve but it has a large constant and it's still superpolynomial.

The article you linked to is wrong, their method is not $$$\mathcal{O}(\log n)$$$ but $$$\mathcal{O}(\sqrt{n})$$$. You can either use your brain to verify that or just try their algorithm on something like $$$10^{16}$$$ -- it takes it about 20 seconds.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +26 Vote: I do not like it

    Classic geeksforgeeks...

    The article is littered with examples of trivialities, but the magic line i = n / (n / (i + 1)); which the complexity depends on is just completely unexplained. (It seems to go through all numbers of the form $$$\left \lfloor \frac{n}{i} \right \rfloor$$$, which is bounded below by $$$\sqrt{n}$$$.)

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +32 Vote: I do not like it

      And don't you hate how GeeksForGeeks links come up as the first results for all the algorithm related google searches?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +31 Vote: I do not like it

        The more frustrating thing is that they try to be the C++ reference and have a (pretty useless, much worse than either of the real references) page for just about every function in C++.

        All things considered I pretty strongly suspect that they use some sketchy techniques that manipulate the Google algorithm to show them on the top.

        → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

It's not known if integer factorization is in P. Sum of divisors is a bit easier problem but I haven't heard about the polynomial algorithm that solves it (maybe they are equivalent).

→ Reply
»
4 years ago, # |
  Vote: I like it -17 Vote: I do not like it

yes but only if p=np

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Factorization is not known to be NP-complete. It may be in P even if P != NP.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      interesting

      btw how to solve this problem https://codeforces.net/contest/993/problem/E?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        idea to solve problem
        → Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

In addition, the number of theses segments is equal to the number of factors of N.

No. Take any large prime.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You are completely right! I am a bit confused, how can we prove that the complexity of the solution is O(sqrt(N)) now?

    → Reply