Detecting perfect powers by factoring into coprimes

This paper presents an algorithm that, given an integer n > 1, finds the largest integer k such that n is a kth power. A previous algorithm by the first author took time b(1+o)(1) where b = lg n; more precisely, time b exp(O(root lg b lg lg b)); conjecturally, time b(lg b)(O( 1)). The new algorithm takes time b(lg b)(O( 1)). It relies on relatively complicated subroutines-specifically, on the first author's fast algorithm to factor integers into coprimes-but it allows a proof of the b(lg b)(O( 1)) bound without much background; the previous proof of b(1+o(1)) relied on transcendental number theory. The computation of k is the first step, and occasionally the bottleneck, in many number-theoretic algorithms: the Agrawal-Kayal-Saxena primality test, for example, and the number-field sieve for integer factorization.