30
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Kaveh Aug 19 '11 at 8:43
  • 1
    $\begingroup$ 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). $\endgroup$ – Kaveh Aug 19 '11 at 8:54
  • 1
    $\begingroup$ 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. $\endgroup$ – Derrick Stolee Aug 19 '11 at 15:36
  • 1
    $\begingroup$ 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. $\endgroup$ – Kaveh Aug 19 '11 at 18:15
  • 1
    $\begingroup$ @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). $\endgroup$ – Kaveh Aug 20 '11 at 22:16
16
$\begingroup$

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

$\endgroup$
  • 5
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Aug 11 '12 at 3:16
  • $\begingroup$ But this is not a formal reduction.... $\endgroup$ – arnab Aug 11 '12 at 4:05
  • 1
    $\begingroup$ @arnab: No, it is not. That is why he wrote “then one would likely be able to quickly factor n completely.” $\endgroup$ – Tsuyoshi Ito Aug 11 '12 at 12:59
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.