A Generalised Successive Resultants Algorithm

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

Authors

Colleges, School and Institutes

External organisations

  • University of Bath
  • University of Oxford

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.

Bibliographic note

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

Details

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
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
CountryBelgium
CityGhent
Period13/07/1615/07/16

Keywords

  • root finding , finite fields , algorithms , elliptic curves