Deterministic root finding over finite fields using Graeffe transforms (Q300881)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Deterministic root finding over finite fields using Graeffe transforms |
scientific article |
Statements
Deterministic root finding over finite fields using Graeffe transforms (English)
0 references
29 June 2016
0 references
Let us consider the finite field \(\mathbb{F}_q\) with \(q=p^k\) elements where \(p\) is a prime number and \(k\geq 1\). Suppose that \(f\in \mathbb{F}_q[x]\) is a polynomial such that all its irreducible factors are linear with multiplicity one. In the paper under review, the authors propose new deterministic algorithms, based on Graeffe transforms for computing all roots of \(f\). Furthermore, they present a new algorithm for computing characteristic polynomial of multiplication endomorphisms in finite field extensions.
0 references
polynomial root finding
0 references
finite field
0 references
Graeffe transform
0 references
deterministic algorithm
0 references
0 references