You are looking at a specific version 20140626:212416 of this paper. See the latest version.

Paper 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

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

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. To appear in the LMS Journal of Computation and Mathematics, as a special issue for ANTS (Algorithmic Number Theory Symposium) conference.
Keywords
number theory
Contact author(s)
christophe petit @ uclouvain be
History
2014-06-26: received
Short URL
https://ia.cr/2014/506
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.