A new faster algorithm for factoring skew polynomials over finite fields. (March 2017) - Caruso, Xavier; Le Borgne, Jérémy
Abstract: In this paper, we provide an algorithm for the factorization of skew polynomials over finite fields. It is faster than the previously known algorithm, which was due toGiesbrecht (1998) . There are two main improvements. The first one is obtained through a careful study of the structure of the quotients of a skew polynomial ring, using theoretical results relating skew polynomial rings and Azumaya algebras. The second improvement is provided by giving faster sub-algorithms for the arithmetic in skew polynomial rings, such as multiplication, division, and extended Euclidean division.