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

DOI:
https://doi.org/10.1090/S0025-5718-06-01837-0

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 , finds the largest integer such that is a th power. A previous algorithm by the first author took time where ; more precisely, time ; conjecturally, time . The new algorithm takes time . 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 bound without much background; the previous proof of relied on transcendental number theory.

The computation of 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.

**1.**Eric Bach, James Dirscoll, Jeffrey Shallit,*Factor refinement*, in [7] (1990), 201-211; see also newer version [2]. URL:`http://cr.yp.to/bib/entries.html#1990/bach-cba`. MR**1231441 (94m:11148)****2.**Eric Bach, James Driscoll, Jeffrey Shallit,*Factor refinement*, Journal of Algorithms**15**(1993), 199-222; see also older version [1]. ISSN 0196-6774. URL:`http://cr.yp.to/bib/entries.html#1993/bach-cba`. MR**1231441 (94m:11148)****3.**Eric Bach, Jonathan Sorenson,*Sieve algorithms for perfect power testing*, Algorithmica**9**(1993), 313-328. ISSN 0178-4617. MR**1208565 (94d:11103)****4.**Daniel J. Bernstein,*Detecting perfect powers in essentially linear time*, Mathematics of Computation**67**(1998), 1253-1283. ISSN 0025-5718. URL:`http://cr.yp.to/papers.html`. MR**1464141 (98j:11121)****5.**Daniel J. Bernstein,*Factoring into coprimes in essentially linear time*, Journal of Algorithms**54**(2005), 1-30. ISSN 0196-6774. URL:`http://cr.yp.to/papers.html#dcba`. ID f32943f0bb67a9317d4021513f9eee5a. MR**2108417****6.**Daniel J. Bernstein,*Fast multiplication and its applications*, to appear in Buhler-Stevenhagen*Algorithmic number theory*book. URL:`http://cr.yp.to/papers.html#multapps`. ID 8758803e61822d485d54251b27b1a20d.**7.**David S. Johnson (editor),*Proceedings of the first annual ACM-SIAM symposium on discrete algorithms, January - San Francisco, California*, Society for Industrial and Applied Mathematics, Philadelphia, 1990. ISBN 0-89871-251-3. MR**1089882 (91i:68006)**

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

Email:
djb@cr.yp.to

**Hendrik W. Lenstra Jr.**

Affiliation:
Mathematisch Instituut, Universiteit Leiden, Postbus 9512, 2300 RA Leiden, The Netherlands

Email:
hwl@math.leidenuniv.nl

**Jonathan Pila**

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

Email:
j.pila@bristol.ac.uk

DOI:
https://doi.org/10.1090/S0025-5718-06-01837-0

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