A new faster algorithm for factoring skew polynomials over finite fields. (March 2017)

• Record Type: Journal Article
• Authors: Caruso, Xavier; Le Borgne, Jérémy
• Is Part Of: Journal of symbolic computation. Volume 79(2017)Part 2
• Page Start: 411
• Page End: 443
• Publication Date: 2017-03
• Subjects: Skew polynomial -- Factorization -- Azumaya algebra; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2016.02.016
• Languages: English
• ISSNs: 0747-7171

Abstract

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.