2
$\begingroup$

Currently, the most efficient algorithm that classical computers can use to factor large composite numbers is the General Number Field Sieve (GNFS), which runs in subexponential time. It returns a set of primes that, when multiplied, yield the composite. Is there such an algorithm that will return the number of primes that a composite number is composed of without actually factoring it, that runs in polynomial time (or better)? Assuming the convention that one is not prime, if the input is already prime, the result will be one.

$\endgroup$
  • 1
    $\begingroup$ So, you want a fast algorithm for the prime Omega function. $\endgroup$ – lhf May 9 at 2:37
  • 2
    $\begingroup$ Consensus is that finding number of prime factors is not significantly easier than factoring. $\endgroup$ – Gerry Myerson May 9 at 4:03
  • $\begingroup$ Do you want repeated prime factors counted? e.g., 12 has three prime factors, two distinct. $\endgroup$ – Robert Soupe May 9 at 4:13
  • 1
    $\begingroup$ @Robert, does it matter? Is there a significant difference in the computational complexity when you count primes with multiplicity, or when you don't? $\endgroup$ – Gerry Myerson May 9 at 12:26
  • $\begingroup$ @GerryMyerson factoring without multiplicity, is factoring the radical which for cases like $5040=2^43^25^17^1$ is $210=2^13^15^17^1$ which is 1 in 24 of the original. $\endgroup$ – Roddy MacPhee May 9 at 14:51
2
$\begingroup$

Actually, a semiprime with unknown prime factors was constructed with methods of elliptic curves.

Despite of this, in general, determining the repeated number of prime factors (often called big-omega) is not significantally easier than factoring , at least no such algorithm is currently known.

Checking for perfect powers and trial division can clarify things for small numbers, but only in very special cases, big-omega can be faster determined than the prime factorization.

$\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.