{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,29]],"date-time":"2026-07-29T03:03:21Z","timestamp":1785294201292,"version":"3.55.0"},"reference-count":32,"publisher":"American Mathematical Society (AMS)","issue":"275","license":[{"start":{"date-parts":[[2012,1,3]],"date-time":"2012-01-03T00:00:00Z","timestamp":1325548800000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n We present a novel idea to compute square roots over finite fields, without being given any quadratic nonresidue, and without assuming any unproven hypothesis. The algorithm is deterministic and the proof is elementary. In some cases, the square root algorithm runs in\n \n \n \n \n \n \n O<\/mml:mi>\n \n ~\n \n <\/mml:mo>\n <\/mml:mover>\n <\/mml:mrow>\n (<\/mml:mo>\n \n log<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n \n \u2061\n \n <\/mml:mo>\n q<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \\tilde {O}(\\log ^2 q)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n bit operations over finite fields with\n \n \n \n q<\/mml:mi>\n q<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n elements. As an application, we construct a deterministic primality-proving algorithm, which runs in\n \n \n \n \n \n \n O<\/mml:mi>\n \n ~\n \n <\/mml:mo>\n <\/mml:mover>\n <\/mml:mrow>\n (<\/mml:mo>\n \n log<\/mml:mi>\n 3<\/mml:mn>\n <\/mml:msup>\n \n \u2061\n \n <\/mml:mo>\n N<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \\tilde {O}(\\log ^3 N)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n for some integers\n \n \n \n N<\/mml:mi>\n N<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n .\n <\/p>","DOI":"10.1090\/s0025-5718-2011-02419-1","type":"journal-article","created":{"date-parts":[[2011,1,3]],"date-time":"2011-01-03T13:18:38Z","timestamp":1294060718000},"page":"1797-1811","source":"Crossref","is-referenced-by-count":8,"title":["On taking square roots without quadratic nonresidues over finite fields"],"prefix":"10.1090","volume":"80","author":[{"given":"Tsz-Wo","family":"Sze","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"14","published-online":{"date-parts":[[2011,1,3]]},"reference":[{"key":"1","first-page":"175","article-title":"On taking roots in finite fields","author":"Adleman, Leonard","year":"1977"},{"issue":"2","key":"2","doi-asserted-by":"publisher","first-page":"781","DOI":"10.4007\/annals.2004.160.781","article-title":"PRIMES is in P","volume":"160","author":"Agrawal, Manindra","year":"2004","journal-title":"Ann. of Math. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0003-486X","issn-type":"print"},{"key":"3","doi-asserted-by":"publisher","first-page":"65","DOI":"10.2307\/1969420","article-title":"The least quadratic non residue","volume":"55","author":"Ankeny, N. C.","year":"1952","journal-title":"Ann. of Math. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0003-486X","issn-type":"print"},{"issue":"6","key":"4","doi-asserted-by":"publisher","first-page":"1494","DOI":"10.1109\/18.59955","article-title":"A note on square roots in finite fields","volume":"36","author":"Bach, Eric","year":"1990","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"issue":"2","key":"5","doi-asserted-by":"publisher","first-page":"807","DOI":"10.1109\/18.749034","article-title":"Note on taking square-roots modulo \ud835\udc41","volume":"45","author":"Bach, Eric","year":"1999","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"issue":"2","key":"6","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s10623-005-4017-5","article-title":"Efficient computation of roots in finite fields","volume":"39","author":"Barreto, Paulo S. L. M.","year":"2006","journal-title":"Des. Codes Cryptogr.","ISSN":"https:\/\/id.crossref.org\/issn\/0925-1022","issn-type":"print"},{"key":"7","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"},{"key":"8","unstructured":"Daniel J. Bernstein, Faster square roots in annoying finite fields, 2001, preprint (http:\/\/cr.yp.to\/papers\/sqroot.pdf)."},{"issue":"215","key":"9","doi-asserted-by":"publisher","first-page":"1311","DOI":"10.1090\/S0025-5718-96-00751-X","article-title":"Constructing nonresidues in finite fields and the extended Riemann hypothesis","volume":"65","author":"Buchmann, Johannes","year":"1996","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"10","unstructured":"Michele Cipolla, Un metodo per la risoluzione della congruenza di secondo grado, Napoli Rend. 9 (1903), 154\u2013163."},{"key":"11","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02945-9","volume-title":"A course in computational algebraic number theory","volume":"138","author":"Cohen, Henri","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/3540556400"},{"key":"12","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":"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"},{"key":"14","unstructured":"Hendrik W. Lenstra Jr. and Carl Pomerance, Primality testing with Gaussian periods, 2009, preprint (http:\/\/math.dartmouth.edu\/~carlp\/aks102309.pdf)."},{"key":"15","volume-title":"The art of computer programming. Vol. 2: Seminumerical algorithms","author":"Knuth, Donald E.","year":"1969"},{"key":"16","first-page":"117","article-title":"Computer technology applied to the theory of numbers","author":"Lehmer, D. H.","year":"1969"},{"key":"17","first-page":"234","article-title":"Riemann\u2019s hypothesis and tests for primality","author":"Miller, Gary L.","year":"1975"},{"key":"18","isbn-type":"print","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/10722028_27","article-title":"On probable prime testing and the computation of square roots mod \ud835\udc5b","author":"M\u00fcller, Siguna","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/3540676953"},{"issue":"3","key":"19","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1023\/B:DESI.0000015890.44831.e2","article-title":"On the computation of square roots in finite fields","volume":"31","author":"M\u00fcller, Siguna","year":"2004","journal-title":"Des. Codes Cryptogr.","ISSN":"https:\/\/id.crossref.org\/issn\/0925-1022","issn-type":"print"},{"issue":"2","key":"20","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1137\/0209024","article-title":"Probabilistic algorithms in finite fields","volume":"9","author":"Rabin, Michael O.","year":"1980","journal-title":"SIAM J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-5397","issn-type":"print"},{"issue":"6","key":"21","doi-asserted-by":"publisher","first-page":"846","DOI":"10.1109\/TIT.1986.1057236","article-title":"A simple and fast probabilistic algorithm for computing square roots modulo a prime number","volume":"32","author":"Peralta, Ren\u00e9 C.","year":"1986","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"key":"22","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/bf02242355","article-title":"Schnelle Multiplikation grosser Zahlen","volume":"7","author":"Sch\u00f6nhage, A.","year":"1971","journal-title":"Computing (Arch. Elektron. Rechnen)","ISSN":"https:\/\/id.crossref.org\/issn\/0010-485X","issn-type":"print"},{"issue":"170","key":"23","doi-asserted-by":"publisher","first-page":"483","DOI":"10.2307\/2007968","article-title":"Elliptic curves over finite fields and the computation of square roots mod \ud835\udc5d","volume":"44","author":"Schoof, Ren\u00e9","year":"1985","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"24","first-page":"51","article-title":"Five number-theoretic algorithms","author":"Shanks, Daniel","year":"1973"},{"key":"25","unstructured":"Andrew V. Sutherland, Structure computation and discrete logarithms in finite abelian \ud835\udc5d-groups, 2009, preprint (http:\/\/arxiv.org\/abs\/0809.3413)."},{"key":"26","unstructured":"Tsz-Wo Sze, On solving univariate polynomial equations over finite fields and some related problems, Ph.D. thesis, University of Maryland, 2007."},{"key":"27","unstructured":"\\bysame, Deterministic primality proving on Proth numbers, 2010, preprint (http:\/\/arxiv.org\/abs\/0812.2596)."},{"key":"28","unstructured":"Alberto Tonelli, Bemerkung \u00fcber die Aufl\u00f6sung quadratischer Congruenzen, Nachrichten der Akademie der Wissenschaften in G\u00f6ttingen (1891), 344\u2013346."},{"issue":"5","key":"29","doi-asserted-by":"publisher","first-page":"443","DOI":"10.2307\/2974905","article-title":"Square roots mod \ud835\udc5d","volume":"101","author":"Turner, Stephen M.","year":"1994","journal-title":"Amer. Math. Monthly","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9890","issn-type":"print"},{"key":"30","isbn-type":"print","volume-title":"Modern computer algebra","author":"von zur Gathen, Joachim","year":"2003","ISBN":"https:\/\/id.crossref.org\/isbn\/0521826462","edition":"2"},{"key":"31","series-title":"Discrete Mathematics and its Applications (Boca Raton)","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1201\/9781420071474","volume-title":"Elliptic curves","author":"Washington, Lawrence C.","year":"2008","ISBN":"https:\/\/id.crossref.org\/isbn\/9781420071467","edition":"2"},{"key":"32","series-title":"Canadian Mathematical Society Series of Monographs and Advanced Texts","isbn-type":"print","volume-title":"\\'{E}douard Lucas and primality testing","volume":"22","author":"Williams, Hugh C.","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/0471148520"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2011-80-275\/S0025-5718-2011-02419-1\/S0025-5718-2011-02419-1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2011-80-275\/S0025-5718-2011-02419-1\/S0025-5718-2011-02419-1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T16:53:26Z","timestamp":1776790406000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2011-80-275\/S0025-5718-2011-02419-1\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1,3]]},"references-count":32,"journal-issue":{"issue":"275","published-print":{"date-parts":[[2011,7]]}},"alternative-id":["S0025-5718-2011-02419-1"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-2011-02419-1","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":[[2011,1,3]]}}}