Deterministic root finding over finite fields using Graeffe transforms

We design new deterministic algorithms, based on Graeffe transforms, to compute all the roots of a polynomial which splits over a finite field F q . Our algorithms were designed to be particularly efficient in the case when the cardinality q - 1 of the multiplicative group of F q is smooth. Such fie...

Full description

Saved in:
Bibliographic Details
Published in:Applicable algebra in engineering, communication and computing communication and computing, 2016-06, Vol.27 (3), p.237-257
Main Authors: Grenet, Bruno, van der Hoeven, Joris, Lecerf, Grégoire
Format: Article
Language:English
Subjects:
Artificial Intelligence
Computer Hardware
Computer Science
Original Paper
Symbolic and Algebraic Manipulation
Symbolic Computation
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We design new deterministic algorithms, based on Graeffe transforms, to compute all the roots of a polynomial which splits over a finite field F q . Our algorithms were designed to be particularly efficient in the case when the cardinality q - 1 of the multiplicative group of F q 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.
ISSN:0938-1279
1432-0622
DOI:10.1007/s00200-015-0280-5