16

Factoring: Gven an integer N, find integers 1 < a, b < N such that N = ab if they exist, otherwise say N is prime.

I know that primality testing is in P, but why not factoring?

Here is my algorithm:

For each a = 1 ... sqrt(N)
    if(N % a == 0)
        b = N/a
        add (a,b) to the result
    Endif
EndFor

This runs in O(sqrt(N)).

Nayana
  • 1,513
  • 3
  • 24
  • 39
  • 7
    The size of the input is the number of bits required to represent it, not the value of the input. – Mankarse Nov 19 '13 at 14:31
  • 2
    [obligatory Wikipedia reference](http://en.wikipedia.org/wiki/Integer_factorization#Difficulty_and_complexity) – Geobits Nov 19 '13 at 14:34
  • 1
    If you're *really* asking why cryptology works and stuff like RSA is so hard to break, you're missing the fact that it's a **modulo** factorization. – Leeor Nov 19 '13 at 14:48
  • 1
    The polynomial time primality testing algorithm is nothing like this algorithm, btw. – Teepeemm Nov 19 '13 at 15:40
  • @phoeagon Wouldn't it be amazing if there were a 6 liner posted on SO that solved P vs NP? – Hank Igoe Jan 07 '21 at 05:19

1 Answers1

21

The input size of a single numeric value, is measured by the length of its binary representation. To be precise, the size of an input numeric value n is proportional to log_2(n). Therefore your algorithm runs in expotential time.

For instance, suppose we are factoring a number N with your algorithm. If N is prime, you have to test at least sqrt(N) factors. (Or alternatively you can compute a prime number table for this but it is still not linear).

Anyway, you test for sqrt(N) times. But the size of the problem is defined as S=log2(N). So we have N=2^S. Therefore it's a sqrt(2^S)=2^(S/2) which is expotential.

phoeagon
  • 2,080
  • 17
  • 20
  • 1
    I am sorry, I still don' understand why it's exponential time. So, for input size N, it's actually 2^N, you mean? – Nayana Nov 19 '13 at 14:37
  • 2
    @Nayana The algorithm runs in O(sqrt(2^n)) = about O(1.414^n), where n is the number of bits required to store the input number N (i.e. n = log2(N)). – interjay Nov 19 '13 at 14:40
  • @nayana updated my answer. sorry for taking so loooong though. – phoeagon Nov 19 '13 at 14:46
  • @AbhishekBansal Saying that a linear time algorithm is also exponential is simply a contradiction. I don't know why you think that is true. – interjay Nov 19 '13 at 14:49
  • @phoeagon I think I understand what you mean. Thank your very much for clarification. – Nayana Nov 19 '13 at 14:50
  • 1
    @interjay Ok got it! The input size is very small and Hence the seemingly normal time also becomes exponential compared to the size of the problem :) – Abhishek Bansal Nov 19 '13 at 14:50
  • 1
    @phoeagon I think what Abhishek Bansal said previously kinda make sense too. Let's say we pass an array and try to find a specific number in the array. The running of a problem is obviously O(N), but the size of the problem is again S=log2(N), because it's measured by the length of its binary representation? This interpretation makes every polynomial time algorithm exponential... – Nayana Nov 19 '13 at 15:21
  • 1
    @Nayana I understand. The problem is, this measure of input size is artificial and somehow arbitrary. You have to obey it to make yourself understood. – phoeagon Nov 19 '13 at 15:59
  • 2
    @Nayana or try to think it this way. A problem with a single numeric value as input is likely a mathematical problem and therefore it is expected to manipulate gigantic figures. Besides, if we take into account the `O(logV)` part of an array of values smaller than `V`, then we have to do a substitution. The inverse function of `O(NlogN)` is not trivial and likely cause confusion. Furthermore, between `N` & `NlogN` really is a small difference, but among `1`, `logN` and `N` it is not. – phoeagon Nov 19 '13 at 16:05