Sign up ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

[Note: n is a given integer (not the number of its digits)]

I'd like to know how O(sqrt(n)/log(n)) would compare against the computational complexity of the best available algorithms (as well as the other one available) for factoring.

Is it conceivable to think that since there are $\sqrt n/\log(\sqrt n) $ primes smaller than $\sqrt n$, in intuitive terms the above complexity could actually represent a lower limit that cannot be broken ? (This would correspond to the ideal situation where all primes were already available (precomputed) and readily accessible at no computational cost.)

After all the information about the divisibility for a given prime does not seem to suggest anything about the divisibility for any other one, and there seems to be no shared information. Or is this thought wrong ? If yes, which is, in intuitive terms clearly, a more plausible candidate for a (larger) lower bound for the factoring complexity?

share|cite|improve this question
Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the FAQ for more information on what is meant by this. We have migrated your question to Computer Science which has a broader scope. –  Kaveh Dec 16 '12 at 19:41

1 Answer 1

up vote 9 down vote accepted

No, the intuitive observation "There are about $\sqrt{n}$ prime factors to try" does not imply a lower bound on the complexity of factoring. There is absolutely no reason that a factoring algorithm must try every possible prime factor, or even that the algorithm's behavior should resemble "trying" different factors at all.

Even though precisely the same intuitive argument can be applied to checking whether a number is prime, the AKS primality-testing algorithm runs in $\log^{O(1)} n$ time.

share|cite|improve this answer
Thank you Jeff. Beautiful intuition. A quality missing in many nowadays scientists. In particular, I wished to know, setting P(n) = sqrt(n)/log(sqrt(n)) and indicating by O(B(n)) the complexity of the best available factoring method, the order of the ratio B(n) / P(n). In intuitive terms: how much better is the best method with respect to O(P(n)) ? –  Pam Dec 16 '12 at 21:02
see wiki for references for some algorithms with running time $\exp(O(\sqrt{log n \log \log n}))$: –  Sasho Nikolov Dec 16 '12 at 21:29
It's less than $O(n^{\alpha})$ for any constant $\alpha$. So yes, much better, asymptotically. BTW this is a pretty basic question, and CS@se is better suited for those –  Sasho Nikolov Dec 17 '12 at 0:42
Take $\alpha = 0.4999999999999999999999$, for example. –  JɛffE Dec 17 '12 at 4:08
$\lim_{n\to\infty} \log n/n^c = 0$ for any constant $c>0$ follows immediately from L'Hôpital's rule. –  JɛffE Dec 17 '12 at 14:56

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.