{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T18:52:22Z","timestamp":1776797542718,"version":"3.51.2"},"reference-count":18,"publisher":"American Mathematical Society (AMS)","issue":"296","license":[{"start":{"date-parts":[[2016,4,10]],"date-time":"2016-04-10T00:00:00Z","timestamp":1460246400000},"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                    We obtain a new bound of certain double multiplicative character sums. We use this bound together with some other previously obtained results to obtain new algorithms for finding roots of polynomials modulo a prime\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"p\">\n                        <mml:semantics>\n                          <mml:mi>p<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">p<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    .\n                  <\/p>","DOI":"10.1090\/mcom\/2946","type":"journal-article","created":{"date-parts":[[2015,4,10]],"date-time":"2015-04-10T19:00:37Z","timestamp":1428692437000},"page":"2969-2977","source":"Crossref","is-referenced-by-count":14,"title":["Character sums and deterministic polynomial root finding in finite fields"],"prefix":"10.1090","volume":"84","author":[{"given":"Jean","family":"Bourgain","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergei","family":"Konyagin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Igor","family":"Shparlinski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2015,4,10]]},"reference":[{"key":"1","doi-asserted-by":"publisher","first-page":"713","DOI":"10.2307\/2004849","article-title":"Factoring polynomials over large finite fields","volume":"24","author":"Berlekamp, E. R.","year":"1970","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"1","key":"2","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":"3","isbn-type":"print","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1007\/978-0-387-68361-4_2","article-title":"Sum-product theorems and applications","author":"Bourgain, Jean","year":"2010","ISBN":"https:\/\/id.crossref.org\/isbn\/9780387370293"},{"issue":"6","key":"4","doi-asserted-by":"publisher","first-page":"1524","DOI":"10.1137\/110850414","article-title":"On the hidden shifted power problem","volume":"41","author":"Bourgain, Jean","year":"2012","journal-title":"SIAM J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-5397","issn-type":"print"},{"key":"5","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1112\/S0025579300001157","article-title":"The distribution of quadratic residues and non-residues","volume":"4","author":"Burgess, D. A.","year":"1957","journal-title":"Mathematika","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5793","issn-type":"print"},{"key":"6","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1112\/plms\/s3-12.1.179","article-title":"On character sums and primitive roots","volume":"12","author":"Burgess, D. A.","year":"1962","journal-title":"Proc. London Math. Soc. (3)","ISSN":"https:\/\/id.crossref.org\/issn\/0024-6115","issn-type":"print"},{"issue":"3","key":"7","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1215\/00127094-2008-056","article-title":"On a question of Davenport and Lewis and new character sum bounds in finite fields","volume":"145","author":"Chang, Mei-Chu","year":"2008","journal-title":"Duke Math. J.","ISSN":"https:\/\/id.crossref.org\/issn\/0012-7094","issn-type":"print"},{"key":"8","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139856065","volume-title":"Modern computer algebra","author":"von zur Gathen, Joachim","year":"2013","ISBN":"https:\/\/id.crossref.org\/isbn\/9781107039032","edition":"3"},{"issue":"3","key":"9","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/BF01272074","article-title":"Computing Frobenius maps and factoring polynomials","volume":"2","author":"von zur Gathen, Joachim","year":"1992","journal-title":"Comput. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/1016-3328","issn-type":"print"},{"key":"10","series-title":"American Mathematical Society Colloquium Publications","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1090\/coll\/053","volume-title":"Analytic number theory","volume":"53","author":"Iwaniec, Henryk","year":"2004","ISBN":"https:\/\/id.crossref.org\/isbn\/0821836331"},{"issue":"223","key":"11","doi-asserted-by":"publisher","first-page":"1179","DOI":"10.1090\/S0025-5718-98-00944-2","article-title":"Subquadratic-time factoring of polynomials over finite fields","volume":"67","author":"Kaltofen, Erich","year":"1998","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"6","key":"12","doi-asserted-by":"publisher","first-page":"1767","DOI":"10.1137\/08073408X","article-title":"Fast polynomial factorization and modular composition","volume":"40","author":"Kedlaya, Kiran S.","year":"2011","journal-title":"SIAM J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-5397","issn-type":"print"},{"key":"13","series-title":"CBMS Regional Conference Series in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1090\/cbms\/084","volume-title":"Ten lectures on the interface between analytic number theory and harmonic analysis","volume":"84","author":"Montgomery, Hugh L.","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/0821807374"},{"key":"14","unstructured":"X. Shao, Character sums over unions of intervals, Forum Math., (to appear)."},{"issue":"5","key":"15","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/0020-0190(90)90195-4","article-title":"On the deterministic complexity of factoring polynomials over finite fields","volume":"33","author":"Shoup, Victor","year":"1990","journal-title":"Inform. Process. Lett.","ISSN":"https:\/\/id.crossref.org\/issn\/0020-0190","issn-type":"print"},{"key":"16","series-title":"Mathematics and its Applications","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-015-9239-0","volume-title":"Finite fields: theory and computation","volume":"477","author":"Shparlinski, Igor E.","year":"1999","ISBN":"https:\/\/id.crossref.org\/isbn\/0792356624"},{"issue":"273","key":"17","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1090\/S0025-5718-2010-02373-7","article-title":"Computing Hilbert class polynomials with the Chinese remainder theorem","volume":"80","author":"Sutherland, Andrew V.","year":"2011","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"18","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1112\/S1461157012001015","article-title":"Accelerating the CM method","volume":"15","author":"Sutherland, Andrew V.","year":"2012","journal-title":"LMS J. Comput. Math."}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2015-84-296\/S0025-5718-2015-02946-9\/S0025-5718-2015-02946-9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2015-84-296\/S0025-5718-2015-02946-9\/S0025-5718-2015-02946-9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T18:33:30Z","timestamp":1776796410000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2015-84-296\/S0025-5718-2015-02946-9\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,10]]},"references-count":18,"journal-issue":{"issue":"296","published-print":{"date-parts":[[2015,11]]}},"alternative-id":["S0025-5718-2015-02946-9"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/2946","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,4,10]]}}}