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-finding algorithm for polynomials over Fpn and was introduced at ANTS in 2014. The algorithm is efficient when the characteristic p is small and n > 1. In this paper, we abstract the core SRA algorithm to arbitrary finite fields and present three instantiations of our general algorithm, one of which is novel and makes use of a series of isogenies derived from elliptic curves with sufficiently smooth order.
Original languageEnglish
Title of host publicationArithmetic of Finite Fields
Subtitle of host publication6th International Workshop, WAIFI 2016, Ghent, Belgium, July 13-15, 2016, Revised Selected Papers
EditorsSylvain Duquesne, Svetla Petkova-Nikova
PublisherSpringer
Pages105-124
ISBN (Electronic)978-3-319-55227-9
ISBN (Print)978-3-319-55226-2
DOIs
Publication statusPublished - 9 Mar 2017
Event6th International Workshop on Arithmetic of Finite Fields, WAIFI 2016 - Ghent, Belgium
Duration: 13 Jul 201615 Jul 2016

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume10064
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference6th International Workshop on Arithmetic of Finite Fields, WAIFI 2016
Country/TerritoryBelgium
CityGhent
Period13/07/1615/07/16

Bibliographical note

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-55227-9_9

Keywords

  • root finding
  • finite fields
  • algorithms
  • elliptic curves

Fingerprint

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

Cite this