Efficient algorithms are presented for factoring polynomials in the skew-polynomial ring K[x; σ], a non-commutative generalization of the usual ring of polynomials K[x], where K is a finite field and σ: K → K is an automorphism. Applications include fast functional decomposition algorithms for a class of polynomials in K[x] whose decompositions are “wild” and previously thought to be difficult to compute. Also presented is a fast probabilistic algorithm for finding zero divisors in any finite associative algebra over K.