Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata
Contributor : Bruno Grenet <>
Submitted on : Tuesday, June 7, 2016 - 1:36:11 PM
Last modification on : Wednesday, November 18, 2020 - 10:32:05 PM

Links full text





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⟩



Record views