{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T15:16:31Z","timestamp":1776870991668,"version":"3.51.2"},"reference-count":7,"publisher":"American Mathematical Society (AMS)","issue":"257","license":[{"start":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T00:00:00Z","timestamp":1189728000000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    This paper presents an algorithm that, given an integer\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"n greater-than 1\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>&gt;<\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">n&gt;1<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    , finds the largest integer\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"k\">\n                        <mml:semantics>\n                          <mml:mi>k<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">k<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    such that\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"n\">\n                        <mml:semantics>\n                          <mml:mi>n<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">n<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    is a\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"k\">\n                        <mml:semantics>\n                          <mml:mi>k<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">k<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    th power. A previous algorithm by the first author took time\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"b Superscript 1 plus o left-parenthesis 1 right-parenthesis\">\n                        <mml:semantics>\n                          <mml:msup>\n                            <mml:mi>b<\/mml:mi>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mn>1<\/mml:mn>\n                              <mml:mo>+<\/mml:mo>\n                              <mml:mi>o<\/mml:mi>\n                              <mml:mo stretchy=\"false\">(<\/mml:mo>\n                              <mml:mn>1<\/mml:mn>\n                              <mml:mo stretchy=\"false\">)<\/mml:mo>\n                            <\/mml:mrow>\n                          <\/mml:msup>\n                          <mml:annotation encoding=\"application\/x-tex\">b^{1+o(1)}<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    where\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"b equals log base 10 n\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>b<\/mml:mi>\n                            <mml:mo>=<\/mml:mo>\n                            <mml:mi>lg<\/mml:mi>\n                            <mml:mo>\n                              \u2061\n                              \n                            <\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">b=\\lg n<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    ; more precisely, time\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"b exp left-parenthesis upper O left-parenthesis StartRoot log base 10 b log base 10 log base 10 b EndRoot right-parenthesis right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>b<\/mml:mi>\n                            <mml:mi>exp<\/mml:mi>\n                            <mml:mo>\n                              \u2061\n                              \n                            <\/mml:mo>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:msqrt>\n                              <mml:mi>lg<\/mml:mi>\n                              <mml:mo>\n                                \u2061\n                                \n                              <\/mml:mo>\n                              <mml:mi>b<\/mml:mi>\n                              <mml:mi>lg<\/mml:mi>\n                              <mml:mo>\n                                \u2061\n                                \n                              <\/mml:mo>\n                              <mml:mi>lg<\/mml:mi>\n                              <mml:mo>\n                                \u2061\n                                \n                              <\/mml:mo>\n                              <mml:mi>b<\/mml:mi>\n                            <\/mml:msqrt>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">b \\exp (O(\\sqrt {\\lg b\\lg \\lg b}))<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    ; conjecturally, time\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"b left-parenthesis log base 10 b right-parenthesis Superscript upper O left-parenthesis 1 right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>b<\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>lg<\/mml:mi>\n                            <mml:mo>\n                              \u2061\n                              \n                            <\/mml:mo>\n                            <mml:mi>b<\/mml:mi>\n                            <mml:msup>\n                              <mml:mo stretchy=\"false\">)<\/mml:mo>\n                              <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                <mml:mi>O<\/mml:mi>\n                                <mml:mo stretchy=\"false\">(<\/mml:mo>\n                                <mml:mn>1<\/mml:mn>\n                                <mml:mo stretchy=\"false\">)<\/mml:mo>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">b (\\lg b)^{O(1)}<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . The new algorithm takes time\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"b left-parenthesis log base 10 b right-parenthesis Superscript upper O left-parenthesis 1 right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>b<\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>lg<\/mml:mi>\n                            <mml:mo>\n                              \u2061\n                              \n                            <\/mml:mo>\n                            <mml:mi>b<\/mml:mi>\n                            <mml:msup>\n                              <mml:mo stretchy=\"false\">)<\/mml:mo>\n                              <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                <mml:mi>O<\/mml:mi>\n                                <mml:mo stretchy=\"false\">(<\/mml:mo>\n                                <mml:mn>1<\/mml:mn>\n                                <mml:mo stretchy=\"false\">)<\/mml:mo>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">b(\\lg b)^{O(1)}<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . It relies on relatively complicated subroutines\u2014specifically, on the first author\u2019s fast algorithm to factor integers into coprimes\u2014but it allows a proof of the\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"b left-parenthesis log base 10 b right-parenthesis Superscript upper O left-parenthesis 1 right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>b<\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>lg<\/mml:mi>\n                            <mml:mo>\n                              \u2061\n                              \n                            <\/mml:mo>\n                            <mml:mi>b<\/mml:mi>\n                            <mml:msup>\n                              <mml:mo stretchy=\"false\">)<\/mml:mo>\n                              <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                <mml:mi>O<\/mml:mi>\n                                <mml:mo stretchy=\"false\">(<\/mml:mo>\n                                <mml:mn>1<\/mml:mn>\n                                <mml:mo stretchy=\"false\">)<\/mml:mo>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">b(\\lg b)^{O(1)}<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    bound without much background; the previous proof of\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"b Superscript 1 plus o left-parenthesis 1 right-parenthesis\">\n                        <mml:semantics>\n                          <mml:msup>\n                            <mml:mi>b<\/mml:mi>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mn>1<\/mml:mn>\n                              <mml:mo>+<\/mml:mo>\n                              <mml:mi>o<\/mml:mi>\n                              <mml:mo stretchy=\"false\">(<\/mml:mo>\n                              <mml:mn>1<\/mml:mn>\n                              <mml:mo stretchy=\"false\">)<\/mml:mo>\n                            <\/mml:mrow>\n                          <\/mml:msup>\n                          <mml:annotation encoding=\"application\/x-tex\">b^{1+o(1)}<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    relied on transcendental number theory. The computation of\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"k\">\n                        <mml:semantics>\n                          <mml:mi>k<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">k<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    is the first step, and occasionally the bottleneck, in many number-theoretic algorithms: the Agrawal-Kayal-Saxena primality test, for example, and the number-field sieve for integer factorization.\n                  <\/p>","DOI":"10.1090\/s0025-5718-06-01837-0","type":"journal-article","created":{"date-parts":[[2006,11,1]],"date-time":"2006-11-01T16:50:02Z","timestamp":1162399802000},"page":"385-388","source":"Crossref","is-referenced-by-count":12,"title":["Detecting perfect powers by factoring into coprimes"],"prefix":"10.1090","volume":"76","author":[{"given":"Daniel","family":"Bernstein","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"suffix":"Jr.","given":"Hendrik","family":"Lenstra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jonathan","family":"Pila","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2006,9,14]]},"reference":[{"issue":"2","key":"1","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1006\/jagm.1993.1038","article-title":"Factor refinement","volume":"15","author":"Bach, Eric","year":"1993","journal-title":"J. Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/0196-6774","issn-type":"print"},{"issue":"2","key":"2","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1006\/jagm.1993.1038","article-title":"Factor refinement","volume":"15","author":"Bach, Eric","year":"1993","journal-title":"J. Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/0196-6774","issn-type":"print"},{"issue":"4","key":"3","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"},{"issue":"223","key":"4","doi-asserted-by":"publisher","first-page":"1253","DOI":"10.1090\/S0025-5718-98-00952-1","article-title":"Detecting perfect powers in essentially linear time","volume":"67","author":"Bernstein, Daniel J.","year":"1998","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"1","key":"5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jalgor.2004.04.009","article-title":"Factoring into coprimes in essentially linear time","volume":"54","author":"Bernstein, Daniel J.","year":"2005","journal-title":"J. Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/0196-6774","issn-type":"print"},{"key":"6","unstructured":"Daniel J. Bernstein, Fast multiplication and its applications, to appear in Buhler-Stevenhagen Algorithmic number theory book. URL: \\url{http:\/\/cr.yp.to\/papers.html#multapps}. ID 8758803e61822d485d54251b27b1a20d."},{"key":"7","isbn-type":"print","volume-title":"Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms","year":"1990","ISBN":"https:\/\/id.crossref.org\/isbn\/0898712513"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2007-76-257\/S0025-5718-06-01837-0\/S0025-5718-06-01837-0.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2007-76-257\/S0025-5718-06-01837-0\/S0025-5718-06-01837-0.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T14:46:33Z","timestamp":1776782793000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2007-76-257\/S0025-5718-06-01837-0\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,9,14]]},"references-count":7,"journal-issue":{"issue":"257","published-print":{"date-parts":[[2007,1]]}},"alternative-id":["S0025-5718-06-01837-0"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-06-01837-0","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":[[2006,9,14]]}}}