# 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. 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). 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. 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. 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). Aug 20 '11 at 22:16

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

There is a folklore observation that if one was able to quickly count the number of prime factors of an integer n, then one would likely be able to quickly factor n completely. So the counting-prime-factors problem is believed to have comparable difficulty to factoring itself.

(I wasn't sure whether this should be an answer or a comment. But it is really an answer, although it isn't written by me. I've made the answer Community Wiki so that it may be upvoted or accepted without unnecessarily giving me reputation.)

• In my opinion, a pointer to an answer like this deserves reputation points (so it should not be community wiki), but I understand that different people have different views. Aug 11 '12 at 3:16
• But this is not a formal reduction.... Aug 11 '12 at 4:05
• @arnab: No, it is not. That is why he wrote “then one would likely be able to quickly factor n completely.” Aug 11 '12 at 12:59

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.