- #1
gchadwick
- 2
- 0
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.
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.