1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Prime Factorization Time Complexity

  1. May 21, 2006 #1
    While I know the time complexity for all known prime factorization algorithms is exponential, I can't seem to get this results for a very simple algorithm.

    First assume we're doing this with numbers that are simply the product of two primes (the kind you get when working with RSA and others) a very simple way to do it is to simple divide the number you're trying to factorize, n by every number between 2 and sqrt(n) and seeing which two leave no remainder. If we then say that the division has a time complexity of o(a) where a is the number of digits we can work out the time complexity of factorization by a simple sum, log(n) + log(n) + log(n) + ... + log(n) (where log(n) will be the number of digits in n) the sum will have sqrt(n) terms in giving sqrt(n) log(n) however that is clearly the wrong result, so can anyone tell me where I'm going wrong? I'm sure it's something obvious I just can't see it.
  2. jcsd
  3. May 21, 2006 #2
    Are you sure about that? If you're correct then I have the same stumbling block as you, because even an algorithm that tests all numbers 1 to N would only have a run time of NlogN
  4. May 21, 2006 #3


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    That is an exponential algorithm: the complexity of number theoretic algorithms is usually described in terms of the size of the representation of the numbers involved, rather than the size of the numbers themselves.

    It takes n = lg N bits to store the number N, and so this algorithm runs in time:

    [tex]O(2^{\mathop{\text{lg}} N} \mathop{\text{lg}} N)
    = O(2^n n)[/tex]

    and is thus exponential.

    That said, prime factorization is known to be subexponential: The number field sieve is an L(1/3) algorithm. See Wikipedia's or Mathworld's page for reference.
    Last edited: May 21, 2006
  5. May 21, 2006 #4
    Ahh that makes sense, I knew it was something obvious, thanks :)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook