A Generalised Successive Resultants Algorithm

James H Davenport; Christophe Petit; Benjamin Pring

doi:10.1007/978-3-319-55227-9_9

A Generalised Successive Resultants Algorithm

James H Davenport, Christophe Petit, Benjamin Pring

University of Oxford

Research output: Chapter or section in a book/report/conference proceeding › Chapter in a published conference proceeding

1 Citation (SciVal)

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 language	English
Title of host publication	Arithmetic of Finite Fields - 6th International Workshop, WAIFI 2016, Revised Selected Papers
Publisher	Springer Verlag
Pages	105-124
Number of pages	20
Volume	10064 LNCS
ISBN (Electronic)	978331955227-9
ISBN (Print)	9783319552262
DOIs	https://doi.org/10.1007/978-3-319-55227-9_9
Publication status	E-pub ahead of print - 9 Mar 2017
Event	International Workshop on the Arithmetic of Finite Fields (WAIFI) 2016 - Ghent, Belgium Duration: 13 Jun 2017 → 15 Jun 2017 http://cage.ugent.be/waifi/

Publication series

Name	Lectures Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher	Springer
Volume	10064 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Workshop

Workshop	International Workshop on the Arithmetic of Finite Fields (WAIFI) 2016
Abbreviated title	WAIFI
Country/Territory	Belgium
City	Ghent
Period	13/06/17 → 15/06/17
Internet address	http://cage.ugent.be/waifi/

Keywords

finite fields
root finding
algorithms
elliptic curves

ASJC Scopus subject areas

Computational Theory and Mathematics

Access to Document

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

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. Advance online publication. 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 or section in a book/report/conference proceeding › Chapter in a published conference proceeding

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)). Epub 2017 Mar 9. doi: 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 = mar,

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",

note = "International Workshop on the Arithmetic of Finite Fields (WAIFI) 2016, WAIFI ; Conference date: 13-06-2017 Through 15-06-2017",

url = "http://cage.ugent.be/waifi/",

}

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 - Chapter in a published conference proceeding

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

T2 - International Workshop on the Arithmetic of Finite Fields (WAIFI) 2016

Y2 - 13 June 2017 through 15 June 2017

ER -

A Generalised Successive Resultants Algorithm

Abstract

Publication series

Workshop

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this