Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Detecting perfect powers
in essentially linear time

Author: Daniel J. Bernstein
Journal: Math. Comp. 67 (1998), 1253-1283
MSC (1991): Primary 11Y16; Secondary 11J86, 65G05
MathSciNet review: 1464141
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: This paper (1) gives complete details of an algorithm to compute approximate $k$th 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)}$.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (1991): 11Y16, 11J86, 65G05

Retrieve articles in all journals with MSC (1991): 11Y16, 11J86, 65G05

Additional Information

Daniel J. Bernstein
Affiliation: Department of Mathematics, University of California, Berkeley, California 94720
Address at time of publication: Department of Mathematics, Statistics, and Computer Science, The University of Illinois at Chicago, Chicago, Illinois 60607–7045

Received by editor(s): October 11, 1995
Received by editor(s) in revised form: April 10, 1997
Additional Notes: This paper was included in the author’s thesis at the University of California at Berkeley. The author was supported in part by a National Science Foundation Graduate Fellowship.
Article copyright: © Copyright 1997 Daniel J. Bernstein