2
$\begingroup$

Is finding the largest prime factor of a number computationally easier than factoring the number into powers of primes?

  • 2
    If the largest prime factor can be found in polynomial time, then applying the same algorithm a linear number of times produces a complete prime factorization, still in polynomial time. So, no, it's not easier.2012-09-25

2 Answers 2

1

no, see

https://mathoverflow.net/questions/104043/saying-things-rapidly-about-integer-factorisations

0

Of course it is easier, since factoring a number into prime powers gives you the largest prime factor for free. In general, it's only a tiny bit easier. There will be extreme examples, like $4^k-1 = (2^k-1)(2^k+1)$, where it might be much easier to prove that one of the numbers is a prime and therefore the largest prime factor, than to factor the other number further.