Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Detecting perfect powers by factoring into coprimes

Authors: Daniel J. Bernstein, Hendrik W. Lenstra Jr. and Jonathan Pila
Journal: Math. Comp. 76 (2007), 385-388
MSC (2000): Primary 11Y16
Published electronically: September 14, 2006
MathSciNet review: 2261027
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: This paper presents an algorithm that, given an integer $ n>1$, finds the largest integer $ k$ such that $ n$ is a $ k$th power. A previous algorithm by the first author took time $ b^{1+o(1)}$ where $ b=\lg n$; more precisely, time $ b \exp(O(\sqrt{\lg b\lg\lg b}))$; conjecturally, time $ b (\lg b)^{O(1)}$. The new algorithm takes time $ b(\lg b)^{O(1)}$. It relies on relatively complicated subroutines--specifically, on the first author's fast algorithm to factor integers into coprimes--but it allows a proof of the $ b(\lg b)^{O(1)}$ bound without much background; the previous proof of $ b^{1+o(1)}$ relied on transcendental number theory.

The computation of $ k$ is the first step, and occasionally the bottleneck, in many number-theoretic algorithms: the Agrawal-Kayal-Saxena primality test, for example, and the number-field sieve for integer factorization.

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

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y16

Retrieve articles in all journals with MSC (2000): 11Y16

Additional Information

Daniel J. Bernstein
Affiliation: Department of Mathematics, Statistics, and Computer Science (M/C 249), The University of Illinois at Chicago, Chicago, Illinois 60607–7045

Hendrik W. Lenstra Jr.
Affiliation: Mathematisch Instituut, Universiteit Leiden, Postbus 9512, 2300 RA Leiden, The Netherlands

Jonathan Pila
Affiliation: School of Mathematics, University of Bristol, Bristol, BS8 1TW, United Kingdom

Received by editor(s): July 2, 2004
Received by editor(s) in revised form: May 10, 2005
Published electronically: September 14, 2006
Additional Notes: Initial work: Lenstra was supported by the National Science Foundation under grant DMS–9224205. Subsequent work: Bernstein was supported by the National Science Foundation under grant DMS–0140542. The authors thank the University of California at Berkeley and the Fields Institute for Research in Mathematical Sciences.
Article copyright: © Copyright 2006 by the authors