A new faster algorithm for factoring skew polynomials over finite fields

详细信息    查看全文

• 作者：Xavier Caruso^a ; ^{xavier.caruso@normalesup.org" class="auth_mail" title="E-mail the corresponding author} ; Jé ; ré ; my Le Borgne^b ; ^{jeremy.leborgne@ens-rennes.fr" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Skew polynomial ; Factorization ; Azumaya algebra
• 刊名：Journal of Symbolic Computation
• 出版年：2017
• 出版时间：March-April 2017
• 年：2017
• 卷：79
• 期：part_P2
• 页码：411-443
• 全文大小：682 K

文摘

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 to Giesbrecht (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.