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

Bruno Grenet 1 Joris Van Der Hoeven 2 Grégoire Lecerf 2
1 ECO - Exact Computing
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Type de document :
Communication dans un congrès
Kazuhiro Yokoyama. ISSAC: International Symposium on Symbolic and Algebraic Computation, Jul 2015, Bath, United Kingdom. ACM, 40th International Symposium on Symbolic and Algebraic Computation, pp.197-204, 2015, 〈10.1145/2755996.2756647〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01327996
Contributeur : Bruno Grenet <>
Soumis le : mardi 7 juin 2016 - 13:21:07
Dernière modification le : jeudi 24 mai 2018 - 15:59:24

Identifiants

Citation

Bruno Grenet, Joris Van Der Hoeven, Grégoire Lecerf. Randomized Root Finding over Finite FFT-fields using Tangent Graeffe Transforms. Kazuhiro Yokoyama. ISSAC: International Symposium on Symbolic and Algebraic Computation, Jul 2015, Bath, United Kingdom. ACM, 40th International Symposium on Symbolic and Algebraic Computation, pp.197-204, 2015, 〈10.1145/2755996.2756647〉. 〈lirmm-01327996〉

Partager

Métriques

Consultations de la notice

192