2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ this is an offshoot of the 3rd problem on ProjectEuler. $\endgroup$
    – ajay
    Sep 25 '12 at 5:56
  • 2
    $\begingroup$ 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. $\endgroup$
    – mjqxxxx
    Sep 25 '12 at 6:03
1
$\begingroup$

no, see

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

$\endgroup$
0
$\begingroup$

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.

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