Deterministic root finding over finite fields using Graeffe transforms - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Article Dans Une Revue Applicable Algebra in Engineering, Communication and Computing Année : 2016

Deterministic root finding over finite fields using Graeffe transforms

Résumé

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.
Fichier principal
Vignette du fichier
dmodroots-5.pdf (401.7 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

lirmm-01328010 , version 1 (17-03-2024)

Identifiants

Citer

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, 2016, 27 (3), pp.237-257. ⟨10.1007/s00200-015-0280-5⟩. ⟨lirmm-01328010⟩

Relations

233 Consultations
21 Téléchargements

Altmetric

Partager

More