Detecting perfect powers in essentially linear time

This paper (1) gives complete details of an algorithm to compute approximate th roots; (2) uses this in an algorithm that, given an integer , either writes as a perfect power or proves that 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 (logn)1+0(1).