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.
7
-
1$\begingroup$ So, you want a fast algorithm for the prime Omega function. $\endgroup$– lhfCommented May 9, 2019 at 2:37
-
2$\begingroup$ Consensus is that finding number of prime factors is not significantly easier than factoring. $\endgroup$– Gerry MyersonCommented May 9, 2019 at 4:03
-
$\begingroup$ Do you want repeated prime factors counted? e.g., 12 has three prime factors, two distinct. $\endgroup$– Robert SoupeCommented May 9, 2019 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 MyersonCommented May 9, 2019 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$– user645636Commented May 9, 2019 at 14:51
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
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.
