Detecting perfect powers by factoring into coprimes
HTML articles powered by AMS MathViewer
- by Daniel J. Bernstein, Hendrik W. Lenstra Jr. and Jonathan Pila PDF
- Math. Comp. 76 (2007), 385-388
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
- Eric Bach, James Driscoll, and Jeffrey Shallit, Factor refinement, J. Algorithms 15 (1993), no. 2, 199–222. MR 1231441, DOI 10.1006/jagm.1993.1038
- Eric Bach, James Driscoll, and Jeffrey Shallit, Factor refinement, J. Algorithms 15 (1993), no. 2, 199–222. MR 1231441, DOI 10.1006/jagm.1993.1038
- Eric Bach and Jonathan Sorenson, Sieve algorithms for perfect power testing, Algorithmica 9 (1993), no. 4, 313–328. MR 1208565, DOI 10.1007/BF01228507
- Daniel J. Bernstein, Detecting perfect powers in essentially linear time, Math. Comp. 67 (1998), no. 223, 1253–1283. MR 1464141, DOI 10.1090/S0025-5718-98-00952-1
- Daniel J. Bernstein, Factoring into coprimes in essentially linear time, J. Algorithms 54 (2005), no. 1, 1–30. MR 2108417, DOI 10.1016/j.jalgor.2004.04.009
- 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.
- Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1990. Held in San Francisco, California, January 22–24, 1990. MR 1089882
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
- 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.
- © Copyright 2006 by the authors
- Journal: Math. Comp. 76 (2007), 385-388
- MSC (2000): Primary 11Y16
- DOI: https://doi.org/10.1090/S0025-5718-06-01837-0
- MathSciNet review: 2261027