{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T20:50:46Z","timestamp":1776804646939,"version":"3.51.2"},"reference-count":28,"publisher":"American Mathematical Society (AMS)","issue":"316","license":[{"start":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T00:00:00Z","timestamp":1559088000000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1402268"],"award-info":[{"award-number":["DMS-1402268"]}],"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                    The\n                    <italic>Gauss\u2013Legendre three-square theorem<\/italic>\n                    asserts that the positive integers\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                    expressible as a sum of three integer squares are precisely those not of the form\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"4 Superscript k Baseline left-parenthesis 8 m plus 7 right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:msup>\n                              <mml:mn>4<\/mml:mn>\n                              <mml:mi>k<\/mml:mi>\n                            <\/mml:msup>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mn>8<\/mml:mn>\n                            <mml:mi>m<\/mml:mi>\n                            <mml:mo>+<\/mml:mo>\n                            <mml:mn>7<\/mml:mn>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">4^k(8m+7)<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    for any nonnegative integers\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"k comma m\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>k<\/mml:mi>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mi>m<\/mml:mi>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">k,m<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . In 1850, Dirichlet gave a beautifully simple proof of this result using only basic facts about ternary quadratic forms. We explain how to turn Dirichlet\u2019s proof into an algorithm; if one assumes the Extended Riemann Hypothesis (ERH), there is a random algorithm for expressing\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"n equals x squared plus y squared plus z squared\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>=<\/mml:mo>\n                            <mml:msup>\n                              <mml:mi>x<\/mml:mi>\n                              <mml:mn>2<\/mml:mn>\n                            <\/mml:msup>\n                            <mml:mo>+<\/mml:mo>\n                            <mml:msup>\n                              <mml:mi>y<\/mml:mi>\n                              <mml:mn>2<\/mml:mn>\n                            <\/mml:msup>\n                            <mml:mo>+<\/mml:mo>\n                            <mml:msup>\n                              <mml:mi>z<\/mml:mi>\n                              <mml:mn>2<\/mml:mn>\n                            <\/mml:msup>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">n=x^2+y^2+z^2<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    , where the expected number of bit operations is\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper O left-parenthesis left-parenthesis log base 10 n right-parenthesis squared left-parenthesis log base 10 log base 10 n right-parenthesis Superscript negative 1 Baseline dot upper M left-parenthesis log base 10 n right-parenthesis right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\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>n<\/mml:mi>\n                            <mml:msup>\n                              <mml:mo stretchy=\"false\">)<\/mml:mo>\n                              <mml:mn>2<\/mml:mn>\n                            <\/mml:msup>\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>lg<\/mml:mi>\n                            <mml:mo>\n                              \u2061\n                              \n                            <\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:msup>\n                              <mml:mo stretchy=\"false\">)<\/mml:mo>\n                              <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                <mml:mo>\n                                  \u2212\n                                  \n                                <\/mml:mo>\n                                <mml:mn>1<\/mml:mn>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                            <mml:mo>\n                              \u22c5\n                              \n                            <\/mml:mo>\n                            <mml:mi>M<\/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>n<\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">O((\\lg n)^2 (\\lg \\lg n)^{-1} \\cdot M(\\lg n))<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . Here,\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper M left-parenthesis r right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>M<\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>r<\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">M(r)<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    stands in for the bit complexity of multiplying two\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"r\">\n                        <mml:semantics>\n                          <mml:mi>r<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">r<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    -bit integers. A random algorithm for this problem of similar complexity was proposed by Rabin and Shallit in 1986; however, their analysis depended on both the ERH and on certain conjectures of Hardy\u2013Littlewood type.\n                  <\/p>","DOI":"10.1090\/mcom\/3349","type":"journal-article","created":{"date-parts":[[2018,1,10]],"date-time":"2018-01-10T10:02:45Z","timestamp":1515578565000},"page":"1007-1019","source":"Crossref","is-referenced-by-count":7,"title":["Dirichlet\u2019s proof of the three-square theorem: An algorithmic perspective"],"prefix":"10.1090","volume":"88","author":[{"given":"Paul","family":"Pollack","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Schorn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2018,5,29]]},"reference":[{"issue":"8","key":"1","doi-asserted-by":"publisher","first-page":"2081","DOI":"10.1142\/S1793042116501256","article-title":"A generalization of a method of Mordell to ternary quadratic forms","volume":"12","author":"Blackwell, Sarah","year":"2016","journal-title":"Int. J. Number Theory","ISSN":"https:\/\/id.crossref.org\/issn\/1793-0421","issn-type":"print"},{"issue":"203","key":"2","doi-asserted-by":"publisher","first-page":"69","DOI":"10.2307\/2152936","article-title":"Statistical evidence for small generating sets","volume":"61","author":"Bach, Eric","year":"1993","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"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":"216","key":"4","doi-asserted-by":"publisher","first-page":"1717","DOI":"10.1090\/S0025-5718-96-00763-6","article-title":"Explicit bounds for primes in residue classes","volume":"65","author":"Bach, Eric","year":"1996","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"2","key":"5","doi-asserted-by":"publisher","first-page":"283","DOI":"10.5802\/jtnb.170","article-title":"On the computation of quadratic 2-class groups","volume":"8","author":"Bosma, Wieb","year":"1996","journal-title":"J. Th\\'{e}or. Nombres Bordeaux","ISSN":"https:\/\/id.crossref.org\/issn\/1246-7405","issn-type":"print"},{"key":"6","series-title":"Cambridge Monographs on Applied and Computational Mathematics","isbn-type":"print","volume-title":"Modern computer arithmetic","volume":"18","author":"Brent, Richard P.","year":"2011","ISBN":"https:\/\/id.crossref.org\/isbn\/9780521194693"},{"issue":"1-4","key":"7","doi-asserted-by":"publisher","first-page":"333","DOI":"10.2307\/1968378","article-title":"Ternary quadratic forms and congruences","volume":"28","author":"Dickson, L. E.","year":"1926","journal-title":"Ann. of Math. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0003-486X","issn-type":"print"},{"issue":"1","key":"8","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1090\/S0002-9904-1927-04312-9","article-title":"Integers represented by positive ternary quadratic forms","volume":"33","author":"Dickson, L. E.","year":"1927","journal-title":"Bull. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9904","issn-type":"print"},{"issue":"1","key":"9","doi-asserted-by":"publisher","first-page":"39","DOI":"10.2307\/2370770","article-title":"Quaternary Quadratic Forms Representing all Integers","volume":"49","author":"Dickson, L. E.","year":"1927","journal-title":"Amer. J. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9327","issn-type":"print"},{"key":"10","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1515\/crll.1850.40.228","article-title":"\u00dcber die Zerlegbarkeit der Zahlen in drei Quadrate","volume":"40","author":"Lejeune Dirichlet, G.","year":"1850","journal-title":"J. Reine Angew. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0075-4102","issn-type":"print"},{"key":"11","isbn-type":"print","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/3-540-44670-2_4","article-title":"Fast reduction of ternary quadratic forms","author":"Eisenbrand, Friedrich","year":"2001","ISBN":"https:\/\/id.crossref.org\/isbn\/3540424881"},{"key":"12","series-title":"A Wiley-Interscience Publication","isbn-type":"print","volume-title":"Introduction to number theory","author":"Flath, Daniel E.","year":"1989","ISBN":"https:\/\/id.crossref.org\/isbn\/047160836X"},{"key":"13","isbn-type":"print","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1145\/1250790.1250800","article-title":"Faster integer multiplication","author":"F\u00fcrer, Martin","year":"2007","ISBN":"https:\/\/id.crossref.org\/isbn\/9781595936318"},{"issue":"3","key":"14","doi-asserted-by":"publisher","first-page":"979","DOI":"10.1137\/070711761","article-title":"Faster integer multiplication","volume":"39","author":"F\u00fcrer, Martin","year":"2009","journal-title":"SIAM J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-5397","issn-type":"print"},{"key":"15","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4939-7560-0","volume-title":"Disquisitiones arithmeticae","author":"Gauss, Carl Friedrich","year":"1986","ISBN":"https:\/\/id.crossref.org\/isbn\/0387962549"},{"issue":"3","key":"16","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1017\/S0305004100054657","article-title":"Almost-primes in arithmetic progressions and short intervals","volume":"83","author":"Heath-Brown, D. R.","year":"1978","journal-title":"Math. Proc. Cambridge Philos. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0305-0041","issn-type":"print"},{"key":"17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jco.2016.03.001","article-title":"Even faster integer multiplication","volume":"36","author":"Harvey, David","year":"2016","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"1","key":"18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02403921","article-title":"Some problems of \u2018Partitio numerorum\u2019; III: On the expression of a number as a sum of primes","volume":"44","author":"Hardy, G. H.","year":"1923","journal-title":"Acta Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0001-5962","issn-type":"print"},{"issue":"1","key":"19","doi-asserted-by":"publisher","first-page":"111","DOI":"10.2307\/1989461","article-title":"The regularity of a genus of positive ternary quadratic forms","volume":"33","author":"Jones, Burton W.","year":"1931","journal-title":"Trans. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9947","issn-type":"print"},{"issue":"2","key":"20","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1016\/0196-6774(80)90021-8","article-title":"Worst-case complexity bounds for algorithms in the theory of integral quadratic forms","volume":"1","author":"Lagarias, J. C.","year":"1980","journal-title":"J. Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/0196-6774","issn-type":"print"},{"issue":"2","key":"21","doi-asserted-by":"publisher","first-page":"485","DOI":"10.2307\/1998017","article-title":"On the computational complexity of determining the solvability or unsolvability of the equation \ud835\udc4b\u00b2-\ud835\udc37\ud835\udc4c\u00b2=-1","volume":"260","author":"Lagarias, J. C.","year":"1980","journal-title":"Trans. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9947","issn-type":"print"},{"key":"22","volume-title":"Elementary number theory","author":"Landau, Edmund","year":"1958"},{"issue":"295","key":"23","doi-asserted-by":"publisher","first-page":"2391","DOI":"10.1090\/S0025-5718-2015-02925-1","article-title":"Conditional bounds for the least quadratic non-residue and related problems","volume":"84","author":"Lamzouri, Youness","year":"2015","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"3","key":"24","doi-asserted-by":"publisher","first-page":"483","DOI":"10.2307\/2152702","article-title":"A rigorous time bound for factoring integers","volume":"5","author":"Lenstra, H. W., Jr.","year":"1992","journal-title":"J. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0894-0347","issn-type":"print"},{"key":"25","unstructured":"[PARI] PARI\/GP, version 2.9.2. \\url{http:\/\/pari.math.u-bordeaux.fr\/}, Bordeaux, 2017."},{"issue":"3","key":"26","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1093\/qmath\/hax001","article-title":"A lower bound for the least prime in an arithmetic progression","volume":"68","author":"Li, Junxian","year":"2017","journal-title":"Q. J. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0033-5606","issn-type":"print"},{"key":"27","unstructured":"[PTn] P. Pollack and E. Trevi\u00f1o, Finding the four squares in Lagrange\u2019s theorem, Integers 18A (2018), 16 pages (electronic)."},{"key":"28","doi-asserted-by":"publisher","first-page":"S239--S256","DOI":"10.1002\/cpa.3160390713","article-title":"Randomized algorithms in number theory","volume":"39","author":"Rabin, Michael O.","year":"1986","journal-title":"Comm. Pure Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0010-3640","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2019-88-316\/S0025-5718-2018-03349-X\/mcom3349_AM.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"http:\/\/www.ams.org\/mcom\/2019-88-316\/S0025-5718-2018-03349-X\/S0025-5718-2018-03349-X.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2019-88-316\/S0025-5718-2018-03349-X\/S0025-5718-2018-03349-X.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T19:59:42Z","timestamp":1776801582000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2019-88-316\/S0025-5718-2018-03349-X\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,29]]},"references-count":28,"journal-issue":{"issue":"316","published-print":{"date-parts":[[2019,3]]}},"alternative-id":["S0025-5718-2018-03349-X"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3349","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":[[2018,5,29]]}}}