Mathematics of Computation

Author(s): Daniel J. Bernstein.
Journal: Math. Comp. 67 (1998), 1253-1283.
MSC (1991): Primary 11Y16; Secondary 11J86, 65G05
Retrieve article in: PDF DVI PostScript
This article is available free of charge

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

Retrieve articles in Mathematics of Computation with MSC (1991): 11Y16, 11J86, 65G05

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: 10.1090/S0025-5718-98-00952-1
PII: S 0025-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.
Copyright of article: Copyright 1997, Daniel J. Bernstein

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS