Detecting perfect powers in essentially linear time
Daniel J. Bernstein · Mathematics of Computation · 1998
This paper (1) gives complete details of an algorithm to compute approximate k k th roots; (2) uses this in an algorithm that, given an integer n > 1 n>1 , either writes n n as a perfect power or proves that n n is not a perfect power; (3) proves, using Loxton’s theorem on multiple linear forms in logarithms, that this perfect-power decomposition algorithm runs in time ( log n ) 1 + o ( 1 ) (\log n)^{1+o(1)} .