{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T03:47:23Z","timestamp":1776829643845,"version":"3.51.2"},"reference-count":31,"publisher":"American Mathematical Society (AMS)","issue":"223","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n This paper (1) gives complete details of an algorithm to compute approximate\n \n \n \n k<\/mml:mi>\n k<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n th roots; (2) uses this in an algorithm that, given an integer\n \n \n \n \n n<\/mml:mi>\n ><\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n n>1<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , either writes\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n as a perfect power or proves that\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is not a perfect power; (3) proves, using Loxton\u2019s theorem on multiple linear forms in logarithms, that this perfect-power decomposition algorithm runs in time\n \n \n \n \n (<\/mml:mo>\n log<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n n<\/mml:mi>\n \n )<\/mml:mo>\n \n 1<\/mml:mn>\n +<\/mml:mo>\n o<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n (\\log n)^{1+o(1)}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n .\n <\/p>","DOI":"10.1090\/s0025-5718-98-00952-1","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T18:14:44Z","timestamp":1027707284000},"page":"1253-1283","source":"Crossref","is-referenced-by-count":27,"title":["Detecting perfect powers in essentially linear time"],"prefix":"10.1090","volume":"67","author":[{"given":"Daniel","family":"Bernstein","sequence":"first","affiliation":[]}],"member":"14","published-online":{"date-parts":[[1998]]},"reference":[{"key":"1","series-title":"Addison-Wesley Series in Computer Science and Information Processing","volume-title":"The design and analysis of computer algorithms","author":"Aho, Alfred V.","year":"1975"},{"key":"2","unstructured":"Robert S. Anderssen and Richard P. Brent (editors), The complexity of computational problem solving, University of Queensland Press, Queensland, 1976."},{"key":"3","series-title":"Foundations of Computing Series","isbn-type":"print","volume-title":"Algorithmic number theory. Vol. 1","author":"Bach, Eric","year":"1996","ISBN":"https:\/\/id.crossref.org\/isbn\/0262024055"},{"issue":"4","key":"4","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/BF01228507","article-title":"Sieve algorithms for perfect power testing","volume":"9","author":"Bach, Eric","year":"1993","journal-title":"Algorithmica","ISSN":"https:\/\/id.crossref.org\/issn\/0178-4617","issn-type":"print"},{"key":"5","isbn-type":"print","first-page":"1","article-title":"The theory of linear forms in logarithms","author":"Baker, A.","year":"1977","ISBN":"https:\/\/id.crossref.org\/isbn\/0120743507"},{"key":"6","isbn-type":"print","volume-title":"Transcendence theory: advances and applications","year":"1977","ISBN":"https:\/\/id.crossref.org\/isbn\/0120743507"},{"key":"7","series-title":"Canadian Mathematical Society Series of Monographs and Advanced Texts","isbn-type":"print","volume-title":"Pi and the AGM","author":"Borwein, Jonathan M.","year":"1987","ISBN":"https:\/\/id.crossref.org\/isbn\/0471831387"},{"key":"8","unstructured":"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\u2013165."},{"issue":"2","key":"9","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1145\/321941.321944","article-title":"Fast multiple-precision evaluation of elementary functions","volume":"23","author":"Brent, Richard P.","year":"1976","journal-title":"J. Assoc. Comput. Mach.","ISSN":"https:\/\/id.crossref.org\/issn\/0004-5411","issn-type":"print"},{"issue":"1","key":"10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0022-314X(83)90002-1","article-title":"On a problem of Oppenheim concerning \u201cfactorisatio numerorum\u201d","volume":"17","author":"Canfield, E. R.","year":"1983","journal-title":"J. Number Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0022-314X","issn-type":"print"},{"key":"11","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02945-9","volume-title":"A course in computational algebraic number theory","volume":"138","author":"Cohen, Henri","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/3540556400"},{"key":"12","series-title":"Cambridge Studies in Advanced Mathematics","isbn-type":"print","volume-title":"Algebraic number theory","volume":"27","author":"Fr\u00f6hlich, A.","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/0521438349"},{"key":"13","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511810817","volume-title":"Matrix analysis","author":"Horn, Roger A.","year":"1985","ISBN":"https:\/\/id.crossref.org\/isbn\/0521305861"},{"key":"14","series-title":"Addison-Wesley Series in Computer Science and Information Processing","volume-title":"The art of computer programming","author":"Knuth, Donald E.","year":"1975","edition":"2"},{"key":"15","series-title":"Addison-Wesley Series in Computer Science and Information Processing","isbn-type":"print","volume-title":"The art of computer programming. Vol. 2","author":"Knuth, Donald E.","year":"1981","ISBN":"https:\/\/id.crossref.org\/isbn\/0201038226","edition":"2"},{"key":"16","series-title":"Lecture Notes in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0091534","volume-title":"The development of the number field sieve","volume":"1554","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/3540570136"},{"key":"17","series-title":"Lecture Notes in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0091534","volume-title":"The development of the number field sieve","volume":"1554","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/3540570136"},{"key":"18","unstructured":"Hendrik W. Lenstra, Jr., private communication."},{"issue":"1676","key":"19","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1098\/rsta.1993.0138","article-title":"A hyperelliptic smoothness test. I","volume":"345","author":"Lenstra, H. W., Jr.","year":"1993","journal-title":"Philos. Trans. Roy. Soc. London Ser. A","ISSN":"https:\/\/id.crossref.org\/issn\/0962-8428","issn-type":"print"},{"issue":"2","key":"20","doi-asserted-by":"publisher","first-page":"113","DOI":"10.4064\/aa-46-2-113-123","article-title":"Some problems involving powers of integers","volume":"46","author":"Loxton, J. H.","year":"1986","journal-title":"Acta Arith.","ISSN":"https:\/\/id.crossref.org\/issn\/0065-1036","issn-type":"print"},{"issue":"3","key":"21","doi-asserted-by":"publisher","first-page":"291","DOI":"10.4064\/aa-42-3-291-302","article-title":"Multiplicative dependence in number fields","volume":"42","author":"Loxton, J. H.","year":"1983","journal-title":"Acta Arith.","ISSN":"https:\/\/id.crossref.org\/issn\/0065-1036","issn-type":"print"},{"key":"22","series-title":"Cambridge Studies in Advanced Mathematics","isbn-type":"print","volume-title":"Commutative ring theory","volume":"8","author":"Matsumura, Hideyuki","year":"1986","ISBN":"https:\/\/id.crossref.org\/isbn\/0521259169"},{"key":"23","isbn-type":"print","volume-title":"Elements of algebraic topology","author":"Munkres, James R.","year":"1984","ISBN":"https:\/\/id.crossref.org\/isbn\/0201045869"},{"issue":"2","key":"24","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1109\/TASSP.1980.1163372","article-title":"Fast polynomial transform algorithms for digital convolution","volume":"28","author":"Nussbaumer, Henri J.","year":"1980","journal-title":"IEEE Trans. Acoust. Speech Signal Process.","ISSN":"https:\/\/id.crossref.org\/issn\/0096-3518","issn-type":"print"},{"key":"25","series-title":"DMV Seminar","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-8589-8","volume-title":"Computational algebraic number theory","volume":"21","author":"Pohst, Michael E.","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/3764329130"},{"key":"26","isbn-type":"print","volume-title":"Numerical recipes","author":"Press, William H.","year":"1986","ISBN":"https:\/\/id.crossref.org\/isbn\/0521308119"},{"issue":"4","key":"27","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1016\/0196-6774(83)90014-7","article-title":"Fast compact prime number sieves (among others)","volume":"4","author":"Pritchard, Paul","year":"1983","journal-title":"J. Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/0196-6774","issn-type":"print"},{"key":"28","first-page":"64","article-title":"Approximate formulas for some functions of prime numbers","volume":"6","author":"Rosser, J. Barkley","year":"1962","journal-title":"Illinois J. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0019-2082","issn-type":"print"},{"key":"29","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/bf02242355","article-title":"Schnelle Multiplikation grosser Zahlen","volume":"7","author":"Sch\u00f6nhage, A.","year":"1971","journal-title":"Computing (Arch. Elektron. Rechnen)","ISSN":"https:\/\/id.crossref.org\/issn\/0010-485X","issn-type":"print"},{"key":"30","series-title":"Graduate Texts in Mathematics, No. 7","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4684-9884-4","volume-title":"A course in arithmetic","author":"Serre, J.-P.","year":"1973"},{"key":"31","volume-title":"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","author":"Whittaker, E. T.","year":"1962"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/1998-67-223\/S0025-5718-98-00952-1\/S0025-5718-98-00952-1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/1998-67-223\/S0025-5718-98-00952-1\/S0025-5718-98-00952-1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T21:48:53Z","timestamp":1776721733000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/1998-67-223\/S0025-5718-98-00952-1\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"references-count":31,"journal-issue":{"issue":"223","published-print":{"date-parts":[[1998,7]]}},"alternative-id":["S0025-5718-98-00952-1"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-98-00952-1","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[1998]]}}}