Finding roots in with the successive resultants algorithm

Research output: Contribution to journalSpecial issuepeer-review

3 Citations (Scopus)


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 ‘large’ finite field with a ‘small’ characteristic. We introduce a new algorithm for solving this type of equations, called the successive resultants algorithm (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 Roots 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.
Original languageEnglish
Pages (from-to)203-217
JournalActa Mathematica Hungarica
Issue numberA
Publication statusPublished - 1 Aug 2014
EventAlgorithmic Number Theory Symposium 2014 (ANTS XI) - GyeongJu, Korea, Republic of
Duration: 7 Aug 201411 Aug 2014


Dive into the research topics of 'Finding roots in with the successive resultants algorithm'. Together they form a unique fingerprint.

Cite this