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
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
- 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.
- © Copyright 1997 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