Randomized Root Finding over Finite FFT-fields using Tangent Graeffe Transforms - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2015

Randomized Root Finding over Finite FFT-fields using Tangent Graeffe Transforms

Abstract

Consider a finite field Fq whose multiplicative group has smooth cardinality. We study the problem of computing all roots of a polynomial that splits over Fq, which was one of the bottlenecks for fast sparse interpolation in practice. We revisit and slightly improve existing algorithms and then present new randomized ones based on the Graeffe transform. We report on our implementation in the MATHEMAGIX computer algebra system, confirming that our ideas gain by a factor ten at least in practice, for sufficiently large inputs.
No file

Dates and versions

lirmm-01327996 , version 1 (07-06-2016)

Identifiers

Cite

Bruno Grenet, Joris van der Hoeven, Grégoire Lecerf. Randomized Root Finding over Finite FFT-fields using Tangent Graeffe Transforms. ISSAC 2015 - 40th International Symposium on Symbolic and Algebraic Computation, Steve Linton, Jul 2015, Bath, United Kingdom. pp.197-204, ⟨10.1145/2755996.2756647⟩. ⟨lirmm-01327996⟩
181 View
0 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More