## Cryptology ePrint Archive: Report 2014/506

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

Christophe Petit

Abstract: 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 simple. 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 importa

Category / Keywords: number theory

Original Publication (in the same form): To appear in the LMS Journal of Computation and Mathematics, as a special issue for ANTS (Algorithmic Number Theory Symposium) conference.