{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,18]],"date-time":"2026-06-18T05:04:02Z","timestamp":1781759042941,"version":"3.54.5"},"reference-count":12,"publisher":"American Mathematical Society (AMS)","issue":"261","license":[{"start":{"date-parts":[[2008,5,14]],"date-time":"2008-05-14T00:00:00Z","timestamp":1210723200000},"content-version":"am","delay-in-days":366,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    Let\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"r comma s comma n\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>r<\/mml:mi>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mi>s<\/mml:mi>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">r,s,n<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    be integers satisfying\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"0 less-than-or-equal-to r greater-than s greater-than n\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mn>0<\/mml:mn>\n                            <mml:mo>\n                              \u2264\n                              \n                            <\/mml:mo>\n                            <mml:mi>r<\/mml:mi>\n                            <mml:mo>&gt;<\/mml:mo>\n                            <mml:mi>s<\/mml:mi>\n                            <mml:mo>&gt;<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">0 \\leq r &gt; s &gt; n<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    ,\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"s greater-than-or-equal-to n Superscript alpha\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>s<\/mml:mi>\n                            <mml:mo>\n                              \u2265\n                              \n                            <\/mml:mo>\n                            <mml:msup>\n                              <mml:mi>n<\/mml:mi>\n                              <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                <mml:mi>\n                                  \u03b1\n                                  \n                                <\/mml:mi>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">s \\geq n^{\\alpha }<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    ,\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"alpha greater-than 1 slash 4\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>\n                              \u03b1\n                              \n                            <\/mml:mi>\n                            <mml:mo>&gt;<\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mo>\/<\/mml:mo>\n                            <\/mml:mrow>\n                            <mml:mn>4<\/mml:mn>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">\\alpha &gt; 1\/4<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    , and let\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"gcd left-parenthesis r comma s right-parenthesis equals 1\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mo movablelimits=\"true\" form=\"prefix\">gcd<\/mml:mo>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>r<\/mml:mi>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mi>s<\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                            <mml:mo>=<\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">\\gcd (r,s)=1<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . Lenstra showed that the number of integer divisors 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                    equivalent to\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"r left-parenthesis mod s right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>r<\/mml:mi>\n                            <mml:mspace width=\"0.667em\"\/>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>mod<\/mml:mi>\n                            <mml:mspace width=\"0.333em\"\/>\n                            <mml:mi>s<\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">r \\pmod s<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    is upper bounded by\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 alpha minus 1 slash 4 right-parenthesis Superscript negative 2 Baseline 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>\n                              \u03b1\n                              \n                            <\/mml:mi>\n                            <mml:mo>\n                              \u2212\n                              \n                            <\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mo>\/<\/mml:mo>\n                            <\/mml:mrow>\n                            <mml:mn>4<\/mml:mn>\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>2<\/mml:mn>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">O((\\alpha -1\/4)^{-2})<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . We re-examine this problem, showing how to explicitly construct all such divisors, and incidentally improve this bound to\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 alpha minus 1 slash 4 right-parenthesis Superscript negative 3 slash 2 Baseline 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>\n                              \u03b1\n                              \n                            <\/mml:mi>\n                            <mml:mo>\n                              \u2212\n                              \n                            <\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mo>\/<\/mml:mo>\n                            <\/mml:mrow>\n                            <mml:mn>4<\/mml:mn>\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>3<\/mml:mn>\n                                <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                  <mml:mo>\/<\/mml:mo>\n                                <\/mml:mrow>\n                                <mml:mn>2<\/mml:mn>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">O((\\alpha -1\/4)^{-3\/2})<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    .\n                  <\/p>","DOI":"10.1090\/s0025-5718-07-02007-8","type":"journal-article","created":{"date-parts":[[2007,10,29]],"date-time":"2007-10-29T06:30:33Z","timestamp":1193639433000},"page":"531-545","source":"Crossref","is-referenced-by-count":10,"title":["Divisors in residue classes, constructively"],"prefix":"10.1090","volume":"77","author":[{"given":"Don","family":"Coppersmith","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nick","family":"Howgrave-Graham","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S.","family":"Nagaraj","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"14","published-online":{"date-parts":[[2007,5,14]]},"reference":[{"key":"1","unstructured":"D. J. Bernstein, Reducing lattice bases to find small-height values of univariate polynomials, in \u201cSurveys in algorithmic number theory\u201d, Mathematical Sciences Research Institute Publications, Vol. 44, Cambridge University Press (to appear)."},{"key":"2","isbn-type":"print","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/3-540-49649-1_3","article-title":"An attack on RSA given a small fraction of the private key bits","author":"Boneh, Dan","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/3540651098"},{"key":"3","doi-asserted-by":"publisher","first-page":"620","DOI":"10.2307\/2005583","article-title":"New primality criteria and factorizations of 2^{\ud835\udc5a}\u00b11","volume":"29","author":"Brillhart, John","year":"1975","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"4","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"},{"key":"5","first-page":"Exp. No. 16, 12","article-title":"Diviseurs appartenant \u00e0 une m\u00eame classe r\u00e9siduelle","author":"Cohen, Henri","year":"1983"},{"key":"6","isbn-type":"print","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/BFb0024458","article-title":"Finding small roots of univariate modular equations revisited","author":"Howgrave-Graham, Nicholas","year":"1997","ISBN":"https:\/\/id.crossref.org\/isbn\/3540639276"},{"key":"7","unstructured":"N. A. Howgrave-Graham, Computational mathematics inspired by RSA, Ph.D. thesis, University of Bath, UK. 1999."},{"issue":"165","key":"8","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":"9","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","article-title":"Factoring polynomials with rational coefficients","volume":"261","author":"Lenstra, A. K.","year":"1982","journal-title":"Math. Ann.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5831","issn-type":"print"},{"key":"10","isbn-type":"print","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/978-3-642-60408-9_15","article-title":"On primes recognizable in deterministic polynomial time","author":"Konyagin, Sergei","year":"1997","ISBN":"https:\/\/id.crossref.org\/isbn\/3540610324"},{"key":"11","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-9316-0","volume-title":"Prime numbers","author":"Crandall, Richard","year":"2001","ISBN":"https:\/\/id.crossref.org\/isbn\/0387947779"},{"key":"12","unstructured":"V. Shoup, NTL: A Library for doing Number Theory (version 4.0a), \\url{www.shoup.net}"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2008-77-261\/S0025-5718-07-02007-8\/S0025-5718-07-02007-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2008-77-261\/S0025-5718-07-02007-8\/S0025-5718-07-02007-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T15:10:53Z","timestamp":1776784253000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2008-77-261\/S0025-5718-07-02007-8\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,5,14]]},"references-count":12,"journal-issue":{"issue":"261","published-print":{"date-parts":[[2008,1]]}},"alternative-id":["S0025-5718-07-02007-8"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-07-02007-8","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":[[2007,5,14]]}}}