Detecting perfect powers in essentially linear time

Bernstein, Daniel

doi:10.1090/S0025-5718-98-00952-1

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Browser Compatibility Info Help
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)}$ .

1. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing; Addison-Wesley Series in Computer Science and Information Processing. MR 0413592 (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 and Jeffrey Shallit, Algorithmic number theory. Vol. 1, Foundations of Computing Series, MIT Press, Cambridge, MA, 1996. Efficient algorithms. MR 1406794 (97e:11157)
4. Eric Bach and Jonathan Sorenson, Sieve algorithms for perfect power testing, Algorithmica 9 (1993), no. 4, 313–328. MR 1208565 (94d:11103), http://dx.doi.org/10.1007/BF01228507
5. A. Baker, The theory of linear forms in logarithms, Transcendence theory: advances and applications (Proc. Conf., Univ. Cambridge, Cambridge, 1976), Academic Press, London, 1977, pp. 1–27. MR 0498417 (58 #16543)
6. Alan Baker and David William Masser (eds.), Transcendence theory: advances and applications, Academic Press [Harcourt Brace Jovanovich Publishers], London, 1977. MR 0457365 (56 #15573)
7. Jonathan M. Borwein and Peter B. Borwein, Pi and the AGM, Canadian Mathematical Society Series of Monographs and Advanced Texts, John Wiley & Sons Inc., New York, 1987. A study in analytic number theory and computational complexity; A Wiley-Interscience Publication. MR 877728 (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, J. Assoc. Comput. Mach. 23 (1976), no. 2, 242–251. MR 0395314 (52 #16111)
10. E. R. Canfield, Paul Erdős, and Carl Pomerance, On a problem of Oppenheim concerning “factorisatio numerorum”, J. Number Theory 17 (1983), no. 1, 1–28. MR 712964 (85j:11012), http://dx.doi.org/10.1016/0022-314X(83)90002-1
11. Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206 (94i:11105)
12. A. Fröhlich and M. J. Taylor, Algebraic number theory, Cambridge Studies in Advanced Mathematics, vol. 27, Cambridge University Press, Cambridge, 1993. MR 1215934 (94d:11078)
13. Roger A. Horn and Charles R. Johnson, Matrix analysis, Cambridge University Press, Cambridge, 1985. MR 832183 (87e:15001)
14. Donald E. Knuth, The art of computer programming, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR 0378456 (51 #14624)
15. Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR 633878 (83i:68003)
16. A. K. Lenstra and H. W. Lenstra Jr. (eds.), The development of the number field sieve, Lecture Notes in Mathematics, vol. 1554, Springer-Verlag, Berlin, 1993. MR 1321216 (96m:11116)
17. A. K. Lenstra and H. W. Lenstra Jr. (eds.), The development of the number field sieve, Lecture Notes in Mathematics, vol. 1554, Springer-Verlag, Berlin, 1993. MR 1321216 (96m:11116)
18. Hendrik W. Lenstra, Jr., private communication.
19. H. W. Lenstra Jr., J. Pila, and Carl Pomerance, A hyperelliptic smoothness test. I, Philos. Trans. Roy. Soc. London Ser. A 345 (1993), no. 1676, 397–408. MR 1253501 (94m:11107), http://dx.doi.org/10.1098/rsta.1993.0138
20. J. H. Loxton, Some problems involving powers of integers, Acta Arith. 46 (1986), no. 2, 113–123. MR 842939 (87j:11071)
21. J. H. Loxton and A. J. van der Poorten, Multiplicative dependence in number fields, Acta Arith. 42 (1983), no. 3, 291–302. MR 729738 (86b:11052)
22. Hideyuki Matsumura, Commutative ring theory, Cambridge Studies in Advanced Mathematics, vol. 8, Cambridge University Press, Cambridge, 1986. Translated from the Japanese by M. Reid. MR 879273 (88h:13001)
23. James R. Munkres, Elements of algebraic topology, Addison-Wesley Publishing Company, Menlo Park, CA, 1984. MR 755006 (85m:55001)
24. Henri J. Nussbaumer, Fast polynomial transform algorithms for digital convolution, IEEE Trans. Acoust. Speech Signal Process. 28 (1980), no. 2, 205–215. MR 563380 (80m:94004), http://dx.doi.org/10.1109/TASSP.1980.1163372
25. Michael E. Pohst, Computational algebraic number theory, DMV Seminar, vol. 21, Birkhäuser Verlag, Basel, 1993. MR 1243639 (94j:11132)
26. William H. Press, Brian P. Flannery, Saul A. Teukolsky, and William T. Vetterling, Numerical recipes, Cambridge University Press, Cambridge, 1986. The art of scientific computing. MR 833288 (87m:65001a)
27. Paul Pritchard, Fast compact prime number sieves (among others), J. Algorithms 4 (1983), no. 4, 332–344. MR 729229 (85h:11080), http://dx.doi.org/10.1016/0196-6774(83)90014-7
28. J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94. MR 0137689 (25 #1139)
29. A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292 (German, with English summary). MR 0292344 (45 #1431)
30. J.-P. Serre, A course in arithmetic, Springer-Verlag, New York, 1973. Translated from the French; Graduate Texts in Mathematics, No. 7. MR 0344216 (49 #8956)
31. E. T. Whittaker and G. N. Watson, A course of modern analysis. An introduction to the general theory of infinite processes and of analytic functions: with an account of the principal transcendental functions, Fourth edition. Reprinted, Cambridge University Press, New York, 1962. MR 0178117 (31 #2375)

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|