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.

Improve this question
$\endgroup$
7
  • 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, 2011 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, 2011 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, 2011 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, 2011 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, 2011 at 22:16

2 Answers 2

Reset to default
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.)

Improve this answer
$\endgroup$
3
  • 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, 2012 at 3:16
  • $\begingroup$ But this is not a formal reduction.... $\endgroup$
    – arnab
    Aug 11, 2012 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, 2012 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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