FACTORING IN SKEW-POLYNOMIAL RINGS OVER FINITE-FIELDS

Efficient algorithms are presented for factoring polynomials in the sk ew-polynomial ring F[x; sigma], a non-commutative generalization of th e usual ring of polynomials F[x], where F is a finite field and sigma: F --> F is an automorphism (iterated Frobenius map). Applications inc lude fast functional decomposition algorithms for a class of polynomia ls in F[x] whose decompositions are ''wild'' and previously thought to be difficult to compute. (C) 1998 Academic Press.