𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Factoring Polynomials Over Finite Fields: A Survey

✍ Scribed by Joachim von zur Gathen; Daniel Panario

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
452 KB
Volume
31
Category
Article
ISSN
0747-7171

No coin nor oath required. For personal study only.

✦ Synopsis

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.

πŸ“œ SIMILAR VOLUMES

Factoring Polynomials over Special Finit
Factoring Polynomials over Special Finite Fields
✍ Eric Bach; Joachim von zur Gathen; Hendrik W. Lenstra Jr. πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 227 KB

We exhibit a deterministic algorithm for factoring polynomials in one variable over "nite "elds. It is e$cient only if a positive integer k is known for which I (p) is built up from small prime factors; here I denotes the kth cyclotomic polynomial, and p is the characteristic of the "eld. In the cas

Factoring Polynomials Over Local Fields
Factoring Polynomials Over Local Fields
✍ Sebastian Pauli πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 361 KB

We describe an efficient new algorithm for factoring a polynomial Ξ¦(x) over a field k that is complete with respect to a discrete prime divisor. For every irreducible factor Ο•(x) of Ξ¦(x) this algorithm returns an integral basis for k[x]/Ο•(x)k[x] over k.

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).

A Class of Polynomials over Finite Field
A Class of Polynomials over Finite Fields
✍ Arnaldo Garcia; Henning Stichtenoth πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 129 KB

Generalizing the norm and trace mappings for % O P /% O , we introduce an interesting class of polynomials over "nite "elds and study their properties. These polynomials are then used to construct curves over "nite "elds with many rational points.