# How hard is it to count the number of factors of an integer?

Given an integer $N$ of length $n$ bits, how hard is it to output the number of prime factors (or alternatively number of factors) of $N$?

If we knew the prime factorization of $N$, then this would be easy. However, if we knew the number of prime factors, or the number of general factors, it is not clear how we'd find the actual prime factorization.

Is this problem studied? Are there known algorithms that solve this question without finding the prime factorization?

This question is motivated by curiosity and partially by a math.SE question.

• If the number of prime factors is large, that would imply that N has a small factor which can be found easily. On the other hand, if the number of prime factors of N is small, say 2, then it is similar to the problem of factoring a product of two primes, and knowing that the number of factors is 2 doesn't seem to help. See this question by Omid about their average hardness. – Kaveh Aug 19 '11 at 8:43
• One more thing, since division is in uniform $\mathsf{TC^0}$, the problem of counting all factors (not just prime factors) is in $\mathsf{\#TC^0}$ and therefore is also in $\mathsf{P}$ (and is probably also complete for $\mathsf{\#TC^0}$ under $\mathsf{AC^0}$ reductions). – Kaveh Aug 19 '11 at 8:54
• Kaveh, if you could expand your above comment into an answer, that would be great. I don't exactly see how division in $\text{TC}^0$ gets you to counting factors in $\#\text{TC}^0$ without also implying that factoring is in $\text{TC}^0$. This misunderstanding is likely due to my own failures but a more detailed answer would help. – Derrick Stolee Aug 19 '11 at 15:36
• known AFAIK! and this is too easy. But I don't see where the argument breaks. ps: I guess I know see, my definition of $\mathsf{\#TC^0}$ is no good (it is the same as $\mathsf{\#P}$) and that is the problem. – Kaveh Aug 19 '11 at 18:15
• @Artem, $\mathsf{\#L}$ is defined as the number of accepting paths of an $\mathsf{NL}$ machine, and an $\mathsf{NL}$ machine can use only logarithmic (in $|y|$) amount of space for guessing $x$. We are guessing too many bits if we use the definition I wrote, an $\mathsf{AC^0}$ computation with polynomially many guesses would capture $\mathsf{NP}$, similarly counting the number of $x$s of polynomial size that an $\mathsf{AC^0}$ machine accepts on them will give $\mathsf{\#P}$ (guess the computation also and verify that is really an accepting computation). – Kaveh Aug 20 '11 at 22:16

This isn't my answer, but Terrence Tao gave a beautiful answer to this question on MathOverflow.

As others have stated, counting the factors would most likely require factoring n. However, trial division can bound the number of factors. You know, for instance, that $N$ has at most $n$ factors, since no factor can be less than 2. By testing if $N$ is divisible by 2, you also know that $N$ has at most $\log_3(N)$ factors, etc. The downside is that each reduction in size is progressively harder - you have to test up to $N^{1/p}$ to rule out $N$ containing more than $p$ factors.