{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,25]],"date-time":"2026-01-25T12:26:58Z","timestamp":1769344018443,"version":"3.49.0"},"reference-count":21,"publisher":"Wiley","issue":"A","license":[{"start":{"date-parts":[[2014,8,1]],"date-time":"2014-08-01T00:00:00Z","timestamp":1406851200000},"content-version":"unspecified","delay-in-days":212,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["LMS J. Comput. Math."],"published-print":{"date-parts":[[2014]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The problem of solving polynomial equations over finite fields has many applications in cryptography and coding theory. In this paper, we consider polynomial equations over a \u2018large\u2019 finite field with a \u2018small\u2019 characteristic. We introduce a new algorithm for solving this type of equations, called the<jats:italic>successive resultants algorithm<\/jats:italic>(SRA). SRA is radically different from previous algorithms for this problem, yet it is conceptually simple. A straightforward implementation using Magma was able to beat the built-in<jats:italic>Roots<\/jats:italic>function for some parameters. These preliminary results encourage a more detailed study of SRA and its applications. Moreover, we point out that an extension of SRA to the multivariate case would have an important impact on the practical security of the elliptic curve discrete logarithm problem in the small characteristic case.<\/jats:p><jats:p><jats:uri xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:type=\"simple\" xlink:href=\"http:\/\/journals.cambridge.org\/sup_S1461157014000138sup001\">Supplementary\u00a0materials\u00a0are\u00a0available\u00a0with\u00a0this\u00a0article.<\/jats:uri><\/jats:p>","DOI":"10.1112\/s1461157014000138","type":"journal-article","created":{"date-parts":[[2014,8,5]],"date-time":"2014-08-05T10:34:15Z","timestamp":1407234855000},"page":"203-217","source":"Crossref","is-referenced-by-count":3,"title":["Finding roots in with the successive resultants algorithm"],"prefix":"10.1112","volume":"17","author":[{"given":"Christophe","family":"Petit","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2014,8,1]]},"reference":[{"key":"S1461157014000138_r20","volume-title":"Handbook of Magma functions","author":"Bosma","year":"2013"},{"key":"S1461157014000138_r4","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1981-0606517-5"},{"key":"S1461157014000138_r8","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-98-00944-2"},{"key":"S1461157014000138_r10","doi-asserted-by":"publisher","DOI":"10.1137\/0221018"},{"key":"S1461157014000138_r9","doi-asserted-by":"publisher","DOI":"10.1137\/08073408X"},{"key":"S1461157014000138_r6","unstructured":"6. J.-C. Faug\u00e8re , L. Perret , C. Petit and R. Gu\u00e9na\u00ebl , \u2018New subexponential algorithms for factoring in $SL(2,2^n)$ \u2019, Cryptology ePrint Archive, Report 2011\/598, 2011. http:\/\/eprint.iacr.org\/."},{"key":"S1461157014000138_r12","doi-asserted-by":"publisher","DOI":"10.1137\/0209024"},{"key":"S1461157014000138_r16","doi-asserted-by":"publisher","DOI":"10.1109\/18.32139"},{"key":"S1461157014000138_r2","volume-title":"Algebraic coding theory","author":"Berlekamp","year":"1984"},{"key":"S1461157014000138_r21","doi-asserted-by":"crossref","first-page":"887","DOI":"10.1145\/2213977.2214056","volume-title":"Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, STOC\u00a0\u201912","author":"Williams","year":"2012"},{"key":"S1461157014000138_r13","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289520"},{"key":"S1461157014000138_r7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29011-4_4"},{"key":"S1461157014000138_r14","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289470"},{"key":"S1461157014000138_r1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1970-0276200-X"},{"key":"S1461157014000138_r5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29011-4_30"},{"key":"S1461157014000138_r15","unstructured":"15. K. Thull and C. Yap , A unified approach to HGCD algorithms for polynomials and integers. Manuscript. Available from http:\/\/cs.nyu.edu\/cs\/faculty\/yap\/allpapers.html\/, 1990."},{"key":"S1461157014000138_r18","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1999.1002"},{"key":"S1461157014000138_r17","volume-title":"Modern computer algebra, 2nd edn","author":"von\u00a0zur Gathen","year":"2003"},{"key":"S1461157014000138_r19","doi-asserted-by":"publisher","DOI":"10.1007\/BF01272074"},{"key":"S1461157014000138_r11","first-page":"451","volume-title":"Asiacrypt","author":"Petit","year":"2012"},{"key":"S1461157014000138_r3","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(67)91016-9"}],"container-title":["LMS Journal of Computation and Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1461157014000138","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,13]],"date-time":"2022-04-13T16:59:59Z","timestamp":1649869199000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1461157014000138\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"references-count":21,"journal-issue":{"issue":"A","published-print":{"date-parts":[[2014]]}},"alternative-id":["S1461157014000138"],"URL":"https:\/\/doi.org\/10.1112\/s1461157014000138","relation":{},"ISSN":["1461-1570"],"issn-type":[{"value":"1461-1570","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}