Finding Roots in GF(p^n) with the Successive Resultant Algorithm

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 emph{Successive Resultants Algorithm} (SRA) in the sequel. SRA is radically different from previous algorithms for this problem, yet it is conceptually as simple and it often has a similar asymptotic complexity. Moreover, a straightforward implementation using Magma was able to beat the built-in function emph{Roots} 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 small characteristic.