most recent 30 from http://mathoverflow.net 2013-05-19T08:37:01Z http://mathoverflow.net/feeds/question/3820 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/3820/how-hard-is-it-to-compute-the-number-of-prime-factors-of-a-given-integer Rune 2009-11-02T17:25:18Z 2010-12-28T01:08:47Z

<p>I asked a related question <a href="http://mathoverflow.net/questions/3274/how-hard-is-it-to-compute-the-euler-totient-function" rel="nofollow">on this mathoverflow thread</a>. That question was promptly answered. This is a natural followup question to that one, which I decided to repost since that question is answered.</p> <p>So quoting myself from that thread:</p> <blockquote> <p>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.</p> </blockquote>

http://mathoverflow.net/questions/3820/how-hard-is-it-to-compute-the-number-of-prime-factors-of-a-given-integer/3842#3842 Harrison Brown 2009-11-02T19:35:02Z 2009-11-02T19:35:02Z

<p>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 <a href="http://terrytao.wordpress.com/2007/06/05/open-question-the-parity-problem-in-sieve-theory/" rel="nofollow">major bane of number theory</a>. 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.</p>

http://mathoverflow.net/questions/3820/how-hard-is-it-to-compute-the-number-of-prime-factors-of-a-given-integer/4337#4337 paarshad 2009-11-06T05:23:00Z 2009-11-06T05:23:00Z

<p>This paper <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa49/aa4913.pdf" rel="nofollow">On some estimates involving the number of prime divisors of an integer</a> might have something that helps you out.</p>

http://mathoverflow.net/questions/3820/how-hard-is-it-to-compute-the-number-of-prime-factors-of-a-given-integer/10037#10037 Steve Flammia 2009-12-29T15:15:11Z 2009-12-29T15:15:11Z

<p>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 <a href="http://en.wikipedia.org/wiki/BQP" rel="nofollow">BQP</a> (bounded-error quantum polynomial time) since we can just use <a href="http://en.wikipedia.org/wiki/Shor%27s%5Falgorithm" rel="nofollow">Shor's algorithm</a> to efficiently factor the number first. It's also in the intersection of <a href="http://en.wikipedia.org/wiki/Co-NP" rel="nofollow">co-NP</a> and <a href="http://en.wikipedia.org/wiki/NP%5F%28complexity%29" rel="nofollow">NP</a>, 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 <a href="http://qwiki.stanford.edu/wiki/Complexity%5FZoo" rel="nofollow">Complexity Zoo</a>.</p>

http://mathoverflow.net/questions/3820/how-hard-is-it-to-compute-the-number-of-prime-factors-of-a-given-integer/10062#10062 Terry Tao 2009-12-29T20:30:07Z 2009-12-29T20:43:12Z

<p>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.</p> <p>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.</p> <p>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.</p> <p>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...</p> <p>[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.]</p>