Detecting perfect powers by factoring into coprimes

Abstract:

This paper presents an algorithm that, given an integer $n>1$, finds the largest integer $k$ such that $n$ is a $k$th power. A previous algorithm by the first author took time $b^{1+o(1)}$ where $b=\lg n$; more precisely, time $b \exp (O(\sqrt {\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.