A Generalised Successive Resultants Algorithm

James H Davenport, Christophe Petit, Benjamin Pring

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

The Successive Resultants Algorithm (SRA) is a root-findingalgorithm for polynomials over GF(p^n) and was introduced at ANTS in2014. The algorithm is efficient when the characteristic p is small and n > 1. In this paper, we abstract the core SRA algorithm to arbitraryfinite fields and present three instantiations of our general algorithm,one of which is novel and makes use of a series of isogenies derived fromelliptic curves with sufficiently smooth order.
Original languageEnglish
Title of host publicationArithmetic of Finite Fields - 6th International Workshop, WAIFI 2016, Revised Selected Papers
PublisherSpringer Verlag
Pages105-124
Number of pages20
Volume10064 LNCS
ISBN (Electronic)978331955227-9
ISBN (Print)9783319552262
DOIs
Publication statusE-pub ahead of print - 9 Mar 2017
EventInternational Workshop on the Arithmetic of Finite Fields (WAIFI) 2016 - Ghent, Belgium
Duration: 13 Jun 201715 Jun 2017
http://cage.ugent.be/waifi/

Publication series

NameLectures Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer
Volume10064 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Workshop

WorkshopInternational Workshop on the Arithmetic of Finite Fields (WAIFI) 2016
Abbreviated titleWAIFI
CountryBelgium
CityGhent
Period13/06/1715/06/17
Internet address

Keywords

  • finite fields
  • root finding
  • algorithms
  • elliptic curves

ASJC Scopus subject areas

  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'A Generalised Successive Resultants Algorithm'. Together they form a unique fingerprint.

  • Cite this

    Davenport, J. H., Petit, C., & Pring, B. (2017). A Generalised Successive Resultants Algorithm. In Arithmetic of Finite Fields - 6th International Workshop, WAIFI 2016, Revised Selected Papers (Vol. 10064 LNCS, pp. 105-124). (Lectures Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10064 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-55227-9_9