๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

On square-free factorization of multivariate polynomials over a finite field

โœ Scribed by Laurent Bernardin

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
625 KB
Volume
187
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

โœฆ Synopsis

In this paper we present a new deterministic algorithm for computing the square-free decomposition of multivariate polynomials with coefficients from a finite field.

Our algorithm is based on Yun's square-free factorization algorithm for characteristic 0. The new algorithm is more efficient than existing, deterministic algorithms based on Musser's squarefree algorithm.

We will show that the modular approach presented by Yun has no significant performance advantage over our algorithm. The new algorithm is also simpler to implement and it can rely on any existing GCD algorithm without having to worry about choosing "good" evaluation points.

To demonstrate this, we present some timings using implementations in Maple , where the new algorithm is used for Release 4 onwards, and Axiom (Jenks and Sutor, 1992) which is the only system known to the author to use an implementation of Yun's modular algorithm mentioned above.

๐Ÿ“œ SIMILAR VOLUMES

Factoring Polynomials Over Finite Fields
Factoring Polynomials Over Finite Fields: A Survey
โœ Joachim von zur Gathen; Daniel Panario ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 452 KB

This survey reviews several algorithms for the factorization of univariate polynomials over finite fields. We emphasize the main ideas of the methods and provide an up-to-date bibliography of the problem.

Counting irreducible factors of polynomi
Counting irreducible factors of polynomials over a finite field
โœ Arnold Knopfmacher; John Knopfmacher ๐Ÿ“‚ Article ๐Ÿ“… 1993 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 728 KB

Counting irreducible factors of polynomials over a finite field, Discrete Mathematics, 112 (1993) 103-l 18. Let F,[X] denote a polynomial ring in an indeterminate X over a finite field IF,. Exact formulae are derived for (i) the number of polynomials of degree n in F,[X] with a specified number of i

The Factorization of Dickson Polynomials
The Factorization of Dickson Polynomials over Finite Fields
โœ Wun-Seng Chou ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 257 KB

Let T n (x, a) สฆ GF(q)[x] be a Dickson polynomial over the finite field GF(q) of either the first kind or the second kind of degree n in the indeterminate x and with parameter a. We give a complete description of the factorization of T n (x, a) over GF(q).