Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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 of the American Mathematical Society 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
Email: djb@pobox.com

DOI: http://dx.doi.org/10.1090/S0025-5718-98-00952-1
PII: S 0025-5718(98)00952-1
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