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.
How hard is it to count the number of factors of an integer?
cc.complexity theory;counting complexity;nt.number theory;factoring
This isn't my answer, but Terrence Tao gave a beautiful answer to this question on MathOverflow.Here are the first few lines of his answer. To read the complete answer, follow the link.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.)