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
DOI: https://doi.org/10.1090/S0025-5718-98-00952-1
MathSciNet review: 1464141
Full-text PDF

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?)

  • 1. Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley, Reading, Massachusetts, 1974. MR 54:1706
  • 2. Robert S. Anderssen and Richard P. Brent (editors), The complexity of computational problem solving, University of Queensland Press, Queensland, 1976.
  • 3. Eric Bach, Jeffrey Shallit, Algorithmic number theory, MIT Press, Boston, Massachusetts, 1996. MR 97e:11157
  • 4. Eric Bach, Jonathan Sorenson, Sieve algorithms for perfect power testing, Algorithmica 9 (1993), 313-328. MR 94d:11103
  • 5. Alan Baker, The theory of linear forms in logarithms, in [6], pp. 1-27. MR 58:16543
  • 6. Alan Baker, David William Masser (editors), Transcendence theory: advances and applications, Academic Press, 1977. MR 56:15573
  • 7. Jonathan M. Borwein, Peter B. Borwein, Pi and the AGM, Wiley, New York, 1987. MR 89a:11134
  • 8. Richard P. Brent, The complexity of multiple-precision arithmetic, in [2], pp. 126-165.
  • 9. Richard P. Brent, Fast multiple-precision evaluation of elementary functions, Journal of the Association for Computing Machinery 23 (1976), 242-251. MR 52:16111
  • 10. E. Rodney Canfield, Paul Erd\H{o}s, Carl Pomerance, On a problem of Oppenheim concerning ``factorisatio numerorum'', Journal of Number Theory 17 (1983), 1-28. MR 85j:11012
  • 11. Henri Cohen, A course in computational algebraic number theory, Springer-Verlag, Berlin, 1993. MR 94i:11105
  • 12. Albrecht Fröhlich, Martin J. Taylor, Algebraic number theory, Cambridge University Press, Cambridge, 1991. MR 94d:11078
  • 13. Roger A. Horn, Charles A. Johnson, Matrix analysis, Cambridge University Press, Cambridge, 1985. MR 87e:15001
  • 14. Donald E. Knuth, The art of computer programming, volume 1: fundamental algorithms, 2nd edition, Addison-Wesley, Reading, Massachusetts, 1973. MR 51:14624
  • 15. Donald E. Knuth, The art of computer programming, volume 2: seminumerical algorithms, 2nd edition, Addison-Wesley, Reading, Massachusetts, 1981. MR 83i:68003
  • 16. Arjen K. Lenstra, Hendrik W. Lenstra, Jr. (editors), The development of the number field sieve, Lecture Notes in Mathematics 1554, Springer-Verlag, Berlin, 1993. MR 96m:11116
  • 17. Arjen K. Lenstra, Hendrik W. Lenstra, Jr., Mark S. Manasse, John M. Pollard, The number field sieve, in [16], pp. 11-40. MR 96m:11116
  • 18. Hendrik W. Lenstra, Jr., private communication.
  • 19. Hendrik W. Lenstra, Jr., Jonathan Pila, Carl Pomerance, A hyperelliptic smoothness test. I, Philosophical Transactions of the Royal Society of London, Series A 345 (1993), 397-408. MR 94m:11107
  • 20. John H. Loxton, Some problems involving powers of integers, Acta Arithmetica 46 (1986), 113-123. MR 87j:11071
  • 21. John H. Loxton, Alfred J. van der Poorten, Multiplicative dependence in number fields, Acta Arithmetica 42 (1983), 291-302. MR 86b:11052
  • 22. Hideyuki Matsumura, Commutative ring theory, Cambridge University Press, Cambridge, 1986. MR 88h:13001
  • 23. James Munkres, Elements of algebraic topology, Addison-Wesley, Reading, Massachusetts, 1984. MR 85m:55001
  • 24. Henri J. Nussbaumer, Fast polynomial transform algorithms for digital convolution, IEEE Transactions on Acoustics, Speech, and Signal Processing 28 (1980), 205-215. MR 80m:94004
  • 25. Michael E. Pohst, Computational algebraic number theory, Birkhäuser, Basel, 1993. MR 94j:11132
  • 26. William H. Press, Brian P. Flannery, Saul P. Teukolsky, William P. Vetterling, Numerical recipes: the art of scientific computing, Cambridge University Press, Cambridge, 1986. MR 87m:65001a
  • 27. Paul Pritchard, Fast compact prime number sieves (among others), J. Algorithms 4 (1983), 332-344. MR 85h:11080
  • 28. J. Barkley Rosser, Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois Journal of Mathematics 6 (1962), 64-94. MR 25:1139
  • 29. Arnold Schönhage, Volker Strassen, Schnelle Multiplikation großer Zahlen, Computing 7 (1971), 281-292. MR 45:1431
  • 30. Jean-Pierre Serre, A course in arithmetic, Springer-Verlag, New York, 1973. MR 49:8956
  • 31. E. T. Whittaker, G. N. Watson, A course of modern analysis, 4th edition, Cambridge University Press, 1927. MR 31:2375 (1962 reprint)

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: https://doi.org/10.1090/S0025-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

American Mathematical Society