{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T03:37:02Z","timestamp":1776829022696,"version":"3.51.2"},"reference-count":16,"publisher":"American Mathematical Society (AMS)","issue":"223","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    In this paper an unconditional probabilistic algorithm to compute the class number of a real quadratic field\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"double-struck upper Q left-parenthesis StartRoot d EndRoot right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mi mathvariant=\"double-struck\">Q<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:msqrt>\n                              <mml:mi>d<\/mml:mi>\n                            <\/mml:msqrt>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">\\mathbb {Q}(\\sqrt {d})<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    is presented, which computes the class number in expected time\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper O left-parenthesis d Superscript 1 slash 5 plus epsilon Baseline right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mi>d<\/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>5<\/mml:mn>\n                                <mml:mo>+<\/mml:mo>\n                                <mml:mi>\n                                  \u03f5\n                                  \n                                <\/mml:mi>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">O(d^{1\/5+\\epsilon })<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . The algorithm is a random version of Shanks\u2019 algorithm. One of the main steps in algorithms to compute the class number is the approximation of\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper L left-parenthesis 1 comma chi right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>L<\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mi>\n                              \u03c7\n                              \n                            <\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">L(1, \\chi )<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . Previous algorithms with the above running time\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper O left-parenthesis d Superscript 1 slash 5 plus epsilon Baseline right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mi>d<\/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>5<\/mml:mn>\n                                <mml:mo>+<\/mml:mo>\n                                <mml:mi>\n                                  \u03f5\n                                  \n                                <\/mml:mi>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">O(d^{1\/5+\\epsilon })<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    , obtain an approximation for\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper L left-parenthesis 1 comma chi right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>L<\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mi>\n                              \u03c7\n                              \n                            <\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">L(1, \\chi )<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    by assuming an appropriate extension of the Riemann Hypothesis. Our algorithm finds an appoximation for\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper L left-parenthesis 1 comma chi right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>L<\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mi>\n                              \u03c7\n                              \n                            <\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">L(1, \\chi )<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    without assuming the Riemann Hypothesis, by using a new technique that we call the \u2018Random Summation Technique\u2019. As a result, we are able to compute the regulator deterministically in expected time\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper O left-parenthesis d Superscript 1 slash 5 plus epsilon Baseline right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mi>d<\/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>5<\/mml:mn>\n                                <mml:mo>+<\/mml:mo>\n                                <mml:mi>\n                                  \u03f5\n                                  \n                                <\/mml:mi>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">O(d^{1\/5+\\epsilon })<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . However, our estimate of\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper O left-parenthesis d Superscript 1 slash 5 plus epsilon Baseline right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mi>d<\/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>5<\/mml:mn>\n                                <mml:mo>+<\/mml:mo>\n                                <mml:mi>\n                                  \u03f5\n                                  \n                                <\/mml:mi>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">O(d^{1\/5+\\epsilon })<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    on the running time of our algorithm to compute the class number is not effective.\n                  <\/p>","DOI":"10.1090\/s0025-5718-98-00965-x","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T18:14:28Z","timestamp":1027707268000},"page":"1285-1308","source":"Crossref","is-referenced-by-count":2,"title":["Computations of class numbers of real quadratic fields"],"prefix":"10.1090","volume":"67","author":[{"given":"Anitha","family":"Srinivasan","sequence":"first","affiliation":[]}],"member":"14","published-online":{"date-parts":[[1998]]},"reference":[{"issue":"2","key":"1","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"},{"key":"2","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4542-1","volume-title":"Binary quadratic forms","author":"Buell, Duncan A.","year":"1989","ISBN":"https:\/\/id.crossref.org\/isbn\/0387970371"},{"key":"3","series-title":"Dover Books on Advanced Mathematics","isbn-type":"print","volume-title":"Advanced number theory","author":"Cohn, Harvey","year":"1980","ISBN":"https:\/\/id.crossref.org\/isbn\/048664023X"},{"key":"4","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-5927-3","volume-title":"Multiplicative number theory","volume":"74","author":"Davenport, Harold","year":"1980","ISBN":"https:\/\/id.crossref.org\/isbn\/0387905332","edition":"2"},{"issue":"5","key":"5","doi-asserted-by":"publisher","first-page":"468","DOI":"10.2307\/2324300","article-title":"A quicker convergence to Euler\u2019s constant","volume":"100","author":"DeTemple, Duane W.","year":"1993","journal-title":"Amer. Math. Monthly","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9890","issn-type":"print"},{"key":"6","isbn-type":"print","volume-title":"An introduction to the theory of numbers","author":"Hardy, G. H.","year":"1979","ISBN":"https:\/\/id.crossref.org\/isbn\/0198531702","edition":"5"},{"key":"7","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-68130-1","volume-title":"Introduction to number theory","author":"Hua, Loo Keng","year":"1982","ISBN":"https:\/\/id.crossref.org\/isbn\/3540108181"},{"key":"8","isbn-type":"print","first-page":"123","article-title":"On the calculation of regulators and class numbers of quadratic fields","author":"Lenstra, H. W., Jr.","year":"1982","ISBN":"https:\/\/id.crossref.org\/isbn\/0521285135"},{"issue":"3","key":"9","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":"10","first-page":"259","article-title":"Computation of the class number of a real quadratic field","volume":"41","author":"Mollin, R. A.","year":"1992","journal-title":"Utilitas Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0315-3681","issn-type":"print"},{"key":"11","series-title":"Springer Series in Statistics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-5246-7","volume-title":"Applied statistics","author":"Sachs, Lothar","year":"1984","ISBN":"https:\/\/id.crossref.org\/isbn\/0387909761","edition":"2"},{"key":"12","isbn-type":"print","first-page":"213","article-title":"Class numbers and units","author":"Zantema, H.","year":"1982","ISBN":"https:\/\/id.crossref.org\/isbn\/9061962498"},{"issue":"6","key":"13","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1016\/S0747-7171(08)80160-5","article-title":"On the worst case of three algorithms for computing the Jacobi symbol","volume":"10","author":"Shallit, Jeffrey","year":"1990","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"14","first-page":"415","article-title":"Class number, a theory of factorization, and genera","author":"Shanks, Daniel","year":"1971"},{"key":"15","first-page":"217","article-title":"The infrastructure of a real quadratic field and its applications","author":"Shanks, Daniel","year":"1972"},{"key":"16","first-page":"285","article-title":"Sur les inverses des \u00e9l\u00e9ments d\u00e9rivables dans un anneau abstrait","volume":"209","author":"Hebroni, P.","year":"1939","journal-title":"C. R. Acad. Sci. Paris","ISSN":"https:\/\/id.crossref.org\/issn\/0001-4036","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/1998-67-223\/S0025-5718-98-00965-X\/S0025-5718-98-00965-X.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/1998-67-223\/S0025-5718-98-00965-X\/S0025-5718-98-00965-X.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T21:48:54Z","timestamp":1776721734000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/1998-67-223\/S0025-5718-98-00965-X\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"references-count":16,"journal-issue":{"issue":"223","published-print":{"date-parts":[[1998,7]]}},"alternative-id":["S0025-5718-98-00965-X"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-98-00965-x","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]]}}}