𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Factoring in Skew-polynomial Rings over Finite Fields

✍ Scribed by M. Giesbrecht

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
716 KB
Volume
26
Category
Article
ISSN
0747-7171

No coin nor oath required. For personal study only.

✦ Synopsis

Efficient algorithms are presented for factoring polynomials in the skew-polynomial ring F[x; Οƒ], a non-commutative generalization of the usual ring of polynomials F[x], where F is a finite field and Οƒ: F β†’ F is an automorphism (iterated Frobenius map). Applications include fast functional decomposition algorithms for a class of polynomials in F[x] whose decompositions are "wild" and previously thought to be difficult to compute.

πŸ“œ 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