{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:14:18Z","timestamp":1750306458944,"version":"3.41.0"},"reference-count":9,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,11,24]],"date-time":"2015-11-24T00:00:00Z","timestamp":1448323200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Commun. Comput. Algebra"],"published-print":{"date-parts":[[2015,11,24]]},"abstract":"<jats:p>Finding roots of polynomials with coefficients in a finite field is a special instance of the polynomial factorization problem. The most well known algorithm for factoring and root-finding is the Cantor-Zassenhaus algorithm. It is a Las Vegas algorithm with running time polynomial in both the polynomial degree and the field size. Its running time is quasi-optimal for the special case of root-finding.<\/jats:p>\n          <jats:p>No deterministic polynomial time algorithm for these problems is known in general, however several deterministic algorithms are known for special instances, most notably when the characteristic of the finite field is small.<\/jats:p>\n          <jats:p>The goal of this poster is to review the best deterministic algorithms for root-finding, in a systematic way. We present, in a unified way, four algorithms:<\/jats:p>\n          <jats:p>\u2022 Berlekamp's Trace Algorithm [2] (BTA),<\/jats:p>\n          <jats:p>\u2022 Moenk's Subgroup Refinement Method [7] (SRM),<\/jats:p>\n          <jats:p>\u2022 Menezes, van Oorschot and Vanstone's Affine Refinement Method [5, 10] (ARM), and<\/jats:p>\n          <jats:p>\u2022 Petit's Successive Resultants Algorithm [8] (SRA).<\/jats:p>\n          <jats:p>It is the first time that these algorithms are presented together in a comprehensive way, and that they are rigorously analysed, implemented and compared to each other.<\/jats:p>\n          <jats:p>In doing so, we obtain several new results:<\/jats:p>\n          <jats:p>\u2022 We significantly improve the complexity ARM, matching that of BTA and SRA.<\/jats:p>\n          <jats:p>\u2022 We highlight a profound duality relationship between ARM and SRA.<\/jats:p>\n          <jats:p>\u2022 We show how to combine ARM with SRM to obtain a new algorithm, which always performs better, and of which ARM and SRM are special instances. The new algorithm considerably extends the range of finite fields for which deterministic polynomial time root-finding is possible.<\/jats:p>\n          <jats:p>\u2022 We present several practical and asymptotic improvements to special instances of the algorithms.<\/jats:p>\n          <jats:p>Part of these results were submitted in response to the call for papers of ISSAC '15, but were rejected. This poster corrects some minor imperfections, improves the asymptotic complexities of some algorithms, and presents a new algorithm not previously known.<\/jats:p>","DOI":"10.1145\/2850449.2850457","type":"journal-article","created":{"date-parts":[[2015,11,30]],"date-time":"2015-11-30T19:03:44Z","timestamp":1448910224000},"page":"87-89","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Deterministic root finding in finite fields"],"prefix":"10.1145","volume":"49","author":[{"given":"Luca","family":"De Feo","sequence":"first","affiliation":[{"name":"Universit\u00e9 de Versailles"}]},{"given":"Christophe","family":"Petit","sequence":"additional","affiliation":[{"name":"University College London"}]},{"given":"Micha\u00ebl","family":"Quisquater","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Versailles"}]}],"member":"320","published-online":{"date-parts":[[2015,11,24]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Algebraic Coding Theory","author":"Berlekamp E.","year":"1984","unstructured":"E. Berlekamp . Algebraic Coding Theory . Aegan Park Press , 1984 . E. Berlekamp. Algebraic Coding Theory. Aegan Park Press, 1984."},{"key":"e_1_2_1_2_1","first-page":"713","volume":"24","author":"Berlekamp E. R.","year":"1970","unstructured":"E. R. Berlekamp . Factoring Polynomials over Large Finite Fields. Math. Comp. , 24 : 713 -- 735 , 1970 . E. R. Berlekamp. Factoring Polynomials over Large Finite Fields. Math. Comp., 24:713--735, 1970.","journal-title":"Large Finite Fields. Math. Comp."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1981-0606517-5"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"A.\n      Menezes P. C.\n      van Oorschot and \n      S. A.\n      Vanstone\n  . \n  Some Computational Aspects of Root Finding in GF(qm)\n  . In P. M. Gianni editor ISSAC volume \n  358\n   of \n  Lecture Notes in Computer Science pages \n  259\n  --\n  270\n  . \n  Springer 1988\n  .   A. Menezes P. C. van Oorschot and S. A. Vanstone. Some Computational Aspects of Root Finding in GF( q m ). In P. M. Gianni editor ISSAC volume 358 of Lecture Notes in Computer Science pages 259--270. Springer 1988.","DOI":"10.1007\/3-540-51084-2_24"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221018"},{"key":"e_1_2_1_7_1","volume-title":"Jan.","author":"Moenck R. T.","year":"1977","unstructured":"R. T. Moenck . On the Efficiency of Algorithms for Polynomial factoring. 31(137):235--250 , Jan. 1977 . R. T. Moenck. On the Efficiency of Algorithms for Polynomial factoring. 31(137):235--250, Jan. 1977."},{"key":"e_1_2_1_8_1","first-page":"8","author":"Petit C.","year":"2014","unstructured":"C. Petit . Finding Roots in GF(pn) with the Successive Resultant Algorithm. LMS Journal of Computation and Mathematics , 8 2014 . (to appear). C. Petit. Finding Roots in GF(pn) with the Successive Resultant Algorithm. LMS Journal of Computation and Mathematics, 8 2014. (to appear).","journal-title":"Successive Resultant Algorithm. LMS Journal of Computation and Mathematics"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/120694.120697"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.32139"}],"container-title":["ACM Communications in Computer Algebra"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2850449.2850457","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2850449.2850457","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:43:27Z","timestamp":1750225407000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2850449.2850457"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,24]]},"references-count":9,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,11,24]]}},"alternative-id":["10.1145\/2850449.2850457"],"URL":"https:\/\/doi.org\/10.1145\/2850449.2850457","relation":{},"ISSN":["1932-2240"],"issn-type":[{"type":"print","value":"1932-2240"}],"subject":[],"published":{"date-parts":[[2015,11,24]]},"assertion":[{"value":"2015-11-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}