52
$\begingroup$

I asked a related question on this mathoverflow thread. That question was promptly answered. This is a natural followup question to that one, which I decided to repost since that question is answered.

So quoting myself from that thread:

How hard is it to compute the number of prime factors of a given integer? This can't be as hard as factoring, since you already know this value for semi-primes, and this information doesn't seem to help at all. Also, determining whether the number of prime factors is 1 or greater than 1 can be done efficiently using Primality Testing.

Improve this question
$\endgroup$
7
  • 5
    $\begingroup$ Distinct or with multiplicity? $\endgroup$
    – Qiaochu Yuan
    Commented Nov 2, 2009 at 17:28
  • 3
    $\begingroup$ Both questions are interesting to me. $\endgroup$
    – Rune
    Commented Nov 2, 2009 at 17:32
  • 1
    $\begingroup$ Determining whether the number of distinct prime factors is exactly 1 is also in P, via the easy trick of computing approximate kth roots for k < log n. $\endgroup$
    – Harrison Brown
    Commented Nov 2, 2009 at 19:10
  • 1
    $\begingroup$ Finding out whether a number has 2 versus >2 prime factors already seems inaccessible to me. $\endgroup$
    – Ilya Nikokoshev
    Commented Nov 2, 2009 at 19:41
  • 8
    $\begingroup$ I'd actually like to even see an algorithm that does the following: given a (large) integer n and promised that n has either 2 prime factors or between (ln ln n)^2 and 2(ln ln 2)^2 prime factors, it decides which in polynomial time (or even just faster than by factoring the numbers). This seems like it could be doable, since on average n would be expected to have just ln ln n prime factors, but I don't have a clue where you'd start. $\endgroup$
    – Harrison Brown
    Commented Nov 2, 2009 at 22:28

4 Answers 4

Reset to default
89
$\begingroup$

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.

The reason for this is that we expect any factoring-type algorithm that works over the integers, to also work over other number fields (ignoring for now the issue of unique factorisation, which in principle can be understood using class field theory). Thus, for instance, we should also be able to count the number of prime factors over the Gaussian integers, which would eventually reveal how many of the (rational) prime factors of the original number n were equal to 1 mod 4 or to 3 mod 4.

Using more and more number fields (but one should only need polylog(n) such fields) and using various reciprocity relations, one would get more and more congruence relations on the various prime factors, and pretty soon one should be able to use the Chinese remainder theorem to pin down the prime factors completely.

More generally, the moment one has a way of extracting even one non-trivial useful bit of information about the factors of a number, it is likely that one can vary this procedure over various number fields (or by changing other parameters, e.g. twisting everything by a Dirichlet character) and soon extract out enough bits of information to pin down the factors completely. The hard part is to first get that one useful bit...

[EDIT: The above principle seems to have one exception, namely the parity bit of various number-theoretic functions. For instance, in the (now stalled) Polymath4 project to find primes, we found a quick way to compute the parity of the prime counting function $\pi(x)$, but it has proven stubbornly difficult to perturb this parity bit computation to find other useful pieces of information about this prime counting function.]

Improve this answer
$\endgroup$
0
20
$\begingroup$

I don't have anything rigorous or backed-up, but computing the number of prime factors (mod 2) seems to be itself very difficult. The fact that current sieve-theoretic technology, in particular, can't distinguish between integers with an even number of prime factors and integers with an odd number of prime factors is a major bane of number theory. The discussion in the linked post makes me strongly doubt that there's a known efficient algorithm for this, since it would have to use methods that are very different from almost any other number-theoretic algorithm out there.

Improve this answer
$\endgroup$
1
  • $\begingroup$ However, this doesn't rule out the possibility of a clever approximation algorithm, although I don't see an obvious way to start on one. $\endgroup$
    – Harrison Brown
    Commented Nov 2, 2009 at 19:36
8
$\begingroup$

Just a few simple observations which haven't been pointed out yet. First, you can phrase the question as a decision problem: Does the integer N have greater than k prime factors (distinct or otherwise)? Then you can use binary search to efficiently find the exact number of prime factors by asking repeated questions. As you point out, this is easier than factoring. Regarding particular complexity classes, this problem is in BQP (bounded-error quantum polynomial time) since we can just use Shor's algorithm to efficiently factor the number first. It's also in the intersection of co-NP and NP, since whichever answer we get (whether it has at least k prime factors, or less than k) can be verified efficiently on a classical computer. There might be more specialized complexity classes where one could try to fit this problem... the first place to look is the Complexity Zoo.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Why do you say this is easier than factoring? Factoring is also in BQP and in the intersection of co-NP and NP, so I'm not seeing the basis for that statement. $\endgroup$
    – D.W.
    Commented Jul 31, 2015 at 6:32
  • 2
    $\begingroup$ @D.W.: he probably writes ”easier“ with the “not more difficult” meaning $\endgroup$
    – Frédéric Grosshans
    Commented Sep 17, 2015 at 16:43
4
$\begingroup$

This paper On some estimates involving the number of prime divisors of an integer might have something that helps you out.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .