Computational complexities in factoring

[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?

• 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

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.
• see wiki for references for some algorithms with running time $\exp(O(\sqrt{log n \log \log n}))$: en.wikipedia.org/wiki/Integer_factorization#General-purpose – 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. – Jeffε 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. – Jeffε Dec 17 '12 at 14:56