✦ LIBER ✦

Factoring Polynomials over Special Finite Fields

✍ Scribed by Eric Bach; Joachim von zur Gathen; Hendrik W. Lenstra Jr.

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 227 KB
Volume: 7
Category: Article
ISSN: 1071-5797
DOI: 10.1006/ffta.2000.0306

No coin nor oath required. For personal study only.

✦ Synopsis

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 case k"1, when I (p)"p!1, such an algorithm was known, and its analysis required the generalized Riemann hypothesis. Our algorithm depends on a similar, but weaker, assumption; speci"cally, the algorithm requires the availability of an irreducible polynomial of degree r over Z/pZ for each prime number r for which I (p) has a prime factor l with l,1 mod r. An auxiliary procedure is devoted to the construction of roots of unity by means of Gauss sums. We do not claim that our algorithm has any practical value.

📜 SIMILAR VOLUMES

Factoring Dickson Polynomials over Finit

Factoring Dickson Polynomials over Finite Fields

✍ Manjul Bhargava; Michael E. Zieve 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 105 KB

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.

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.

Enumeration of Special Sets of Polynomia

Enumeration of Special Sets of Polynomials over Finite Fields

✍ Astrid Reifegerste 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 379 KB

In this paper we consider squarefree polynomials over finite fields whose gcd with their reciprocal and Frobenius conjugate polynomial is trivial, respectively. Our focus is on the enumeration of these special sets of polynomials, in particular, we give the number of squarefree palindromes. These in

On the Value Sets of Special Polynomials

On the Value Sets of Special Polynomials over Finite Fields

✍ Abramo Hefez 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 225 KB

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