References: [ Home | Author index | Key index | Search ]

Bernstein1998b

D. Berstein, "Detecting perfect powers in essentially linear time," Math. Comp., 67:223 (1998) 1253--1283.  Available from http://cr.yp.to/papers.html.  MR 98j:11121

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