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.

Date: received 4 Jun 2014

Contact author: christophe petit at uclouvain be

Available format(s): PDF | BibTeX Citation

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

Version: 20140626:212416 (All versions of this report)

Short URL: ia.cr/2014/506

Discussion forum: Show discussion | Start new discussion