<p>No, the intuitive observation "There are about $\sqrt{n}$ prime factors to try" does <em>not</em> 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.</p>

<p>Even though <em>precisely</em> the same intuitive argument can be applied to checking whether a number is prime, the <a href="http://en.wikipedia.org/wiki/AKS_primality_test">AKS primality-testing algorithm</a> runs in $\log^{O(1)} n$ time.</p>

CC BY-SA 3.0
2012-12-16T21:02:50.203Z
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
CC BY-SA 3.0
2012-12-16T21:29:10.717Z
see wiki for references for some algorithms with running time $\exp(O(\sqrt{log n \log \log n}))$: http://en.wikipedia.org/wiki/Integer_factorization#General-purpose
Sasho Nikolov
CC BY-SA 3.0
2012-12-16T21:39:01.210Z
Is that much better than O(sqrt(n)/log(sqrt(n))) ? How much better exactly? (Remember that with n I am denoting the number itself, not the number of digits)
Pam
CC BY-SA 3.0
2012-12-17T00:42:06.043Z
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](http://cs.stackexchange.com) is better suited for those
Sasho Nikolov
CC BY-SA 3.0
2012-12-17T01:19:23.417Z
Thank you, I see, but does actually exists a constant \alpha such that O(sqrt(n)/log(sqrt(n))) is asymptotically greater than O(n^{\alpha}). What value of \alpha is that (it seems that \alpha = 1/2 would not be small enough) ?
Pam
CC BY-SA 3.0
2012-12-17T04:08:00.517Z
Take $\alpha = 0.4999999999999999999999$, for example.
Jeffε
CC BY-SA 3.0
2012-12-17T13:26:04.870Z
Thank you. I get it. For a last doubt, is there any reference for a simple proof of "It's less than $O(n^\alpha)$ for any constant $\alpha$"
Pam
CC BY-SA 3.0
2012-12-17T14:56:01.760Z
$\lim_{n\to\infty} \log n/n^c = 0$ for any constant $c>0$ follows immediately from L'Hôpital's rule.
Jeffε
CC BY-SA 3.0
2012-12-17T16:21:28.487Z
Yes, thank you. Actually I was referring to your sentence about $\exp(O(\sqrt{log n \log \log n}))$ being less than $O(n^{\alpha})$ (or do you mean that $exp()$ and $O()$ can be interchanged and a similar argument applies ?)
Pam
CC BY-SA 3.0
2012-12-18T08:42:02.157Z
they cannot be interchanged, but $n^\alpha = \exp(\alpha \log n)$. take the limit of $\exp(C \sqrt{\log n \log \log n} - \alpha \log n)$ as $n \to \infty$ for any constants $C$ and $\alpha$.
Sasho Nikolov
CC BY-SA 3.0
2012-12-16T16:56:08.623Z
2012-12-16T16:56:08.623Z
Jeffε
<p>[Note: n is a given integer (not the number of its digits)]</p>

<p>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.</p>

<p>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.)</p>

<p>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?</p>

CC BY-SA 3.0
2012-12-16T19:41:26.820Z
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 [cs.se] which has a broader scope.
Kaveh
<complexity-classes><cr.crypto-security><factoring><primes>
Computational complexities in factoring
Pam
# Computational complexities in factoring

(Asked by: username_0 on 2012-12-16)

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

**Tags:** complexity-classes, cr.crypto-security, factoring, primes
> **Comments:**
> **username_1**: 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 [cs.se] which has a broader scope.  

---

## 1 answers

### Answer by username_2 on 2012-12-16. Score: 9 | Accepted answer

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](http://en.wikipedia.org/wiki/AKS_primality_test) runs in $\log^{O(1)} n$ time.

> **Comments:**
> **username_0**: 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)) ?  
> **username_3**: see wiki for references for some algorithms with running time $\exp(O(\sqrt{log n \log \log n}))$: http://en.wikipedia.org/wiki/Integer_factorization#General-purpose  
> **username_0**: Is that much better than O(sqrt(n)/log(sqrt(n))) ? How much better exactly? (Remember that with n I am denoting the number itself, not the number of digits)  
> **username_3**: 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](http://cs.stackexchange.com) is better suited for those  
> **username_0**: Thank you, I see, but does actually exists a constant \alpha such that O(sqrt(n)/log(sqrt(n))) is asymptotically greater than O(n^{\alpha}). What value of \alpha is that (it seems that \alpha = 1/2 would not be small enough) ?  
> **username_2**: Take $\alpha = 0.4999999999999999999999$, for example.  
> **username_0**: Thank you. I get it. For a last doubt, is there any reference for a simple proof of "It's less than $O(n^\alpha)$ for any constant $\alpha$"  
> **username_2**: $\lim_{n\to\infty} \log n/n^c = 0$ for any constant $c>0$ follows immediately from L'Hôpital's rule.  
> **username_0**: Yes, thank you. Actually I was referring to your sentence about $\exp(O(\sqrt{log n \log \log n}))$ being less than $O(n^{\alpha})$ (or do you mean that $exp()$ and $O()$ can be interchanged and a similar argument applies ?)  
> **username_3**: they cannot be interchanged, but $n^\alpha = \exp(\alpha \log n)$. take the limit of $\exp(C \sqrt{\log n \log \log n} - \alpha \log n)$ as $n \to \infty$ for any constants $C$ and $\alpha$.  

---

