{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T14:01:55Z","timestamp":1776866515952,"version":"3.51.2"},"reference-count":13,"publisher":"American Mathematical Society (AMS)","issue":"300","license":[{"start":{"date-parts":[[2016,10,20]],"date-time":"2016-10-20T00:00:00Z","timestamp":1476921600000},"content-version":"am","delay-in-days":366,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1406190"],"award-info":[{"award-number":["DMS-1406190"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    A deterministic algorithm for factoring\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                    using\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"n Superscript 1 slash 3 plus o left-parenthesis 1 right-parenthesis\">\n                        <mml:semantics>\n                          <mml:msup>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mn>1<\/mml:mn>\n                              <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                <mml:mo>\/<\/mml:mo>\n                              <\/mml:mrow>\n                              <mml:mn>3<\/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\">n^{1\/3+o(1)}<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    bit operations is presented. The algorithm tests the divisibility of\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                    by all the integers in a short interval at once rather than integer by integer as in trial division. The algorithm is implemented.\n                  <\/p>","DOI":"10.1090\/mcom3037","type":"journal-article","created":{"date-parts":[[2015,2,11]],"date-time":"2015-02-11T13:10:22Z","timestamp":1423660222000},"page":"2065-2069","source":"Crossref","is-referenced-by-count":5,"title":["A deterministic algorithm for integer factorization"],"prefix":"10.1090","volume":"85","author":[{"given":"Ghaith","family":"Hiary","sequence":"first","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2015,10,20]]},"reference":[{"issue":"6","key":"1","doi-asserted-by":"publisher","first-page":"1777","DOI":"10.1137\/S0097539704443793","article-title":"Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator","volume":"36","author":"Bostan, Alin","year":"2007","journal-title":"SIAM J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-5397","issn-type":"print"},{"key":"2","isbn-type":"print","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1007\/3-540-68339-9_16","article-title":"Finding a small root of a bivariate integer equation; factoring with high bits known","author":"Coppersmith, Don","year":"1996","ISBN":"https:\/\/id.crossref.org\/isbn\/354061186X"},{"issue":"285","key":"3","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1090\/S0025-5718-2013-02707-X","article-title":"Faster deterministic integer factorization","volume":"83","author":"Costa, Edgar","year":"2014","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"4","isbn-type":"print","volume-title":"Prime numbers","author":"Crandall, Richard","year":"2005","ISBN":"https:\/\/id.crossref.org\/isbn\/9780387252827","edition":"2"},{"key":"5","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511818097","volume-title":"The higher arithmetic","author":"Davenport, H.","year":"2008","ISBN":"https:\/\/id.crossref.org\/isbn\/9780521722360","edition":"8"},{"key":"6","doi-asserted-by":"publisher","first-page":"637","DOI":"10.2307\/2005940","article-title":"Factoring large integers","volume":"28","author":"Lehman, R. Sherman","year":"1974","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"165","key":"7","doi-asserted-by":"publisher","first-page":"331","DOI":"10.2307\/2007582","article-title":"Divisors in residue classes","volume":"42","author":"Lenstra, H. W., Jr.","year":"1984","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"4","key":"8","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1112\/blms\/28.4.351","article-title":"Turning Euler\u2019s factoring method into a factoring algorithm","volume":"28","author":"McKee, James","year":"1996","journal-title":"Bull. London Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0024-6093","issn-type":"print"},{"key":"9","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1017\/s0305004100049252","article-title":"Theorems on factorization and primality testing","volume":"76","author":"Pollard, J. M.","year":"1974","journal-title":"Proc. Cambridge Philos. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0008-1981","issn-type":"print"},{"key":"10","isbn-type":"print","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/3-540-39805-8_3","article-title":"Efficient factoring based on partial information","author":"Rivest, Ronald L.","year":"1986","ISBN":"https:\/\/id.crossref.org\/isbn\/3540164685"},{"key":"11","first-page":"Paper No. A12, 20","article-title":"The distribution of solutions to \ud835\udc65\ud835\udc66=\ud835\udc5b (mod \ud835\udc4e) with an application to factoring integers","volume":"13","author":"Rubinstein, Michael O.","year":"2013","journal-title":"Integers"},{"issue":"1","key":"12","first-page":"1","article-title":"Einige Resultate \u00fcber Berechnungskomplexit\u00e4t","volume":"78","author":"Strassen, Volker","year":"1976","journal-title":"Jber. Deutsch. Math.-Verein.","ISSN":"https:\/\/id.crossref.org\/issn\/0012-0456","issn-type":"print"},{"key":"13","series-title":"Translations of Mathematical Monographs","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1090\/mmono\/232","volume-title":"Number-theoretic algorithms in cryptography","volume":"232","author":"Vasilenko, O. N.","year":"2007","ISBN":"https:\/\/id.crossref.org\/isbn\/9780821840900"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2016-85-300\/S0025-5718-2015-03037-3\/S0025-5718-2015-03037-3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2016-85-300\/S0025-5718-2015-03037-3\/S0025-5718-2015-03037-3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T18:49:57Z","timestamp":1776797397000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2016-85-300\/S0025-5718-2015-03037-3\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,10,20]]},"references-count":13,"journal-issue":{"issue":"300","published-print":{"date-parts":[[2016,7]]}},"alternative-id":["S0025-5718-2015-03037-3"],"URL":"https:\/\/doi.org\/10.1090\/mcom3037","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":[[2015,10,20]]}}}