Deterministic root finding over finite fields using Graeffe transforms - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Applicable Algebra in Engineering, Communication and Computing Year : 2016

Deterministic root finding over finite fields using Graeffe transforms

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.
Fichier principal
Vignette du fichier
dmodroots-5.pdf (401.7 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

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

Identifiers

Cite

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

200 View
5 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More