Deterministic root finding over finite fields using 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 : We design new deterministic algorithms, based on Graeffe transforms, to compute all the roots of a polynomial which splits over a finite field Fq. Our algorithms were designed to be particularly efficient in the case when the cardinality q−1 of the multiplicative group of Fq is smooth. Such fields are often used in practice because they support fast discrete Fourier transforms. We also present a new nearly optimal algorithm for computing characteristic polynomials of multiplication endomorphisms in finite field extensions. This algorithm allows for the efficient computation of Graeffe transforms of arbitrary orders.
Type de document :
Article dans une revue
Applicable Algebra in Engineering, Communication and Computing, Springer Verlag, 2016, 27 (3), pp.237-257. 〈10.1007/s00200-015-0280-5〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01328010
Contributeur : Bruno Grenet <>
Soumis le : mardi 7 juin 2016 - 13:36:11
Dernière modification le : mercredi 25 avril 2018 - 10:45:21

Lien texte intégral

Identifiants

Relations

Citation

Bruno Grenet, Joris Van Der Hoeven, Grégoire Lecerf. Deterministic root finding over finite fields using Graeffe transforms. Applicable Algebra in Engineering, Communication and Computing, Springer Verlag, 2016, 27 (3), pp.237-257. 〈10.1007/s00200-015-0280-5〉. 〈lirmm-01328010〉

Partager

Métriques

Consultations de la notice

123