A generalized successive resultant algorithm

Conference item

The Successive Resultants Algorithm (SRA) is a root-finding algorithm for polynomials over Fpn and was introduced at ANTS in 2014 [19]. The algorithm was designed to be 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.

Authors: Petit, C; Davenport, J; Pring, B

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: International Workshop on the Arithmetic of Finite Fields
• Host title: Workshop on the Arithmetic of Finite Fields
• Journal: Workshop on the Arithmetic of Finite Fields
• Publication date: 2017-03-01
• Acceptance date: 2016-06-11
• DOI: 10.1007/978-3-319-55227-9_9
• Keywords: finite fields; algorithms; elliptic curves; root finding