4
$\begingroup$

Our current understanding of prime factorization states that it is hard to solve. The problem asks us to find the list of prime factors for an integer. For example, 18's prime factors are 3, 3, and 2. But since 3 is repeated, we only count it once.

But what about a slightly easier problem---finding how many prime factors a number has. Is there an efficient algorithm to do such a task?

In the 18 case, we still don't double count 3. So our algorithm should output 2 (the two prime factors are 3 and 2).

$\endgroup$
3
  • 3
    $\begingroup$ You are essentially asking for the complexity of computing the prime omega function $\omega(n)$. $\endgroup$
    – Steven
    Nov 5, 2023 at 18:07
  • $\begingroup$ @Steven I edited the question to say that prime factorization is hard to solve as we currently know it $\endgroup$
    – abokifas
    Nov 5, 2023 at 18:24
  • 5
    $\begingroup$ mathoverflow.net/q/3820/37212 $\endgroup$
    – D.W.
    Nov 6, 2023 at 5:12

2 Answers 2

5
$\begingroup$

No problem involving factorization is known to be polynomial time, and these problems (formulated as decision problems in any reasonable way) are suspected to be NP-intermediate. The only problem which is known to be polynomial time is primality testing.

$\endgroup$
3
  • $\begingroup$ Thanks. Do you have a source for this consensus? $\endgroup$
    – abokifas
    Nov 5, 2023 at 22:25
  • 1
    $\begingroup$ @abokifas have you tried searching abstracts for papers about factorization problems? $\endgroup$
    – Bakuriu
    Nov 6, 2023 at 7:59
  • $\begingroup$ Well, determining whether a number has one or more than one prime factor can be done in polynomial time. So I wouldn't say no problem involving factorization is known to be polynomial time. $\endgroup$
    – Tyilo
    Nov 8, 2023 at 20:09
0
$\begingroup$

It’s easy to find small prime factors. Pollard-rho can find a factor p in $O(\sqrt p)$ which finds many prime factors. And for large n with no known small prime factors we can do a primality test which finds there is one factor only.

The problem is when n is so large that we cannot prove there are no factors up to $n^{1/3}$ so we don’t know if there are 2 or 3 prime factors.

$\endgroup$

Your Answer

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

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