Detecting perfect powers in essentially linear time

Bernstein, Daniel

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

Detecting perfect powers in essentially linear time
HTML articles powered by AMS MathViewer

by Daniel J. Bernstein PDF

Math. Comp. 67 (1998), 1253-1283

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

Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing. MR 0413592
Robert S. Anderssen and Richard P. Brent (editors), The complexity of computational problem solving, University of Queensland Press, Queensland, 1976.
Eric Bach and Jeffrey Shallit, Algorithmic number theory. Vol. 1, Foundations of Computing Series, MIT Press, Cambridge, MA, 1996. Efficient algorithms. MR 1406794
Eric Bach and Jonathan Sorenson, Sieve algorithms for perfect power testing, Algorithmica 9 (1993), no. 4, 313–328. MR 1208565, DOI 10.1007/BF01228507
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
Alan Baker and David William Masser (eds.), Transcendence theory: advances and applications, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1977. MR 0457365
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
Richard P. Brent, The complexity of multiple-precision arithmetic, in [Robert S. Anderssen and Richard P. Brent (editors), The complexity of computational problem solving, University of Queensland Press, Queensland, 1976], pp. 126–165.
Richard P. Brent, Fast multiple-precision evaluation of elementary functions, J. Assoc. Comput. Mach. 23 (1976), no. 2, 242–251. MR 395314, DOI 10.1145/321941.321944
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, DOI 10.1016/0022-314X(83)90002-1
Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
A. Fröhlich and M. J. Taylor, Algebraic number theory, Cambridge Studies in Advanced Mathematics, vol. 27, Cambridge University Press, Cambridge, 1993. MR 1215934
Roger A. Horn and Charles R. Johnson, Matrix analysis, Cambridge University Press, Cambridge, 1985. MR 832183, DOI 10.1017/CBO9780511810817
Donald E. Knuth, The art of computer programming, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms. MR 0378456
Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
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, DOI 10.1007/BFb0091534
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, DOI 10.1007/BFb0091534
Hendrik W. Lenstra, Jr., private communication.
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, DOI 10.1098/rsta.1993.0138
J. H. Loxton, Some problems involving powers of integers, Acta Arith. 46 (1986), no. 2, 113–123. MR 842939, DOI 10.4064/aa-46-2-113-123
J. H. Loxton and A. J. van der Poorten, Multiplicative dependence in number fields, Acta Arith. 42 (1983), no. 3, 291–302. MR 729738, DOI 10.4064/aa-42-3-291-302
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
James R. Munkres, Elements of algebraic topology, Addison-Wesley Publishing Company, Menlo Park, CA, 1984. MR 755006
Henri J. Nussbaumer, Fast polynomial transform algorithms for digital convolution, IEEE Trans. Acoust. Speech Signal Process. 28 (1980), no. 2, 205–215. MR 563380, DOI 10.1109/TASSP.1980.1163372
Michael E. Pohst, Computational algebraic number theory, DMV Seminar, vol. 21, Birkhäuser Verlag, Basel, 1993. MR 1243639, DOI 10.1007/978-3-0348-8589-8
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
Paul Pritchard, Fast compact prime number sieves (among others), J. Algorithms 4 (1983), no. 4, 332–344. MR 729229, DOI 10.1016/0196-6774(83)90014-7
J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94. MR 137689
A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292 (German, with English summary). MR 292344, DOI 10.1007/bf02242355
J.-P. Serre, A course in arithmetic, Graduate Texts in Mathematics, No. 7, Springer-Verlag, New York-Heidelberg, 1973. Translated from the French. MR 0344216, DOI 10.1007/978-1-4684-9884-4
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, Cambridge University Press, New York, 1962. Fourth edition. Reprinted. MR 0178117