Is finding the largest prime factor of a number computationally easier than factoring the number into powers of primes?
Complexity of finding the largest prime factor of a composite number
2
$\begingroup$
prime-numbers
factoring
-
2If 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
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.