A Generalised Successive Resultants Algorithm

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

Fingerprint

Polynomials

Keywords

  • finite fields
  • root finding
  • algorithms
  • elliptic curves

ASJC Scopus subject areas

  • Computational Theory and Mathematics

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

A Generalised Successive Resultants Algorithm. / Davenport, James H; Petit, Christophe; Pring, Benjamin.

Arithmetic of Finite Fields - 6th International Workshop, WAIFI 2016, Revised Selected Papers. Vol. 10064 LNCS Springer Verlag, 2017. p. 105-124 (Lectures Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10064 LNCS).

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

Davenport, JH, 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, Lectures Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10064 LNCS, Springer Verlag, pp. 105-124, International Workshop on the Arithmetic of Finite Fields (WAIFI) 2016, Ghent, Belgium, 13/06/17. https://doi.org/10.1007/978-3-319-55227-9_9
Davenport JH, Petit C, Pring B. A Generalised Successive Resultants Algorithm. In Arithmetic of Finite Fields - 6th International Workshop, WAIFI 2016, Revised Selected Papers. Vol. 10064 LNCS. Springer Verlag. 2017. p. 105-124. (Lectures Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-55227-9_9
Davenport, James H ; Petit, Christophe ; Pring, Benjamin. / A Generalised Successive Resultants Algorithm. Arithmetic of Finite Fields - 6th International Workshop, WAIFI 2016, Revised Selected Papers. Vol. 10064 LNCS Springer Verlag, 2017. pp. 105-124 (Lectures Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{227ddd3489704f7aa1db7e6ec1e91e2f,
title = "A Generalised Successive Resultants Algorithm",
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.",
keywords = "finite fields, root finding, algorithms, elliptic curves",
author = "Davenport, {James H} and Christophe Petit and Benjamin Pring",
year = "2017",
month = "3",
day = "9",
doi = "10.1007/978-3-319-55227-9_9",
language = "English",
isbn = "9783319552262",
volume = "10064 LNCS",
series = "Lectures Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "105--124",
booktitle = "Arithmetic of Finite Fields - 6th International Workshop, WAIFI 2016, Revised Selected Papers",
address = "Germany",

}

TY - GEN

T1 - A Generalised Successive Resultants Algorithm

AU - Davenport, James H

AU - Petit, Christophe

AU - Pring, Benjamin

PY - 2017/3/9

Y1 - 2017/3/9

N2 - 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.

AB - 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.

KW - finite fields

KW - root finding

KW - algorithms

KW - elliptic curves

UR - http://www.scopus.com/inward/record.url?scp=85015202771&partnerID=8YFLogxK

UR - https://doi.org/10.1007/978-3-319-55227-9_9

U2 - 10.1007/978-3-319-55227-9_9

DO - 10.1007/978-3-319-55227-9_9

M3 - Conference contribution

SN - 9783319552262

VL - 10064 LNCS

T3 - Lectures Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 105

EP - 124

BT - Arithmetic of Finite Fields - 6th International Workshop, WAIFI 2016, Revised Selected Papers

PB - Springer Verlag

ER -