Factoring in skew-polynomial rings over finite fields
type: Item
instance of: scholarly article
title: Factoring in skew-polynomial rings over finite fields
zbMATH Open document ID: 0941.68160
published in: Journal of Symbolic Computation
publication date: 2000-06-27T00:00:00Z
review text: The author considers two factorization problems in skew-polynomial rings \(\mathbb F[x;\sigma]\) where \(\mathbb F\) is a finite field, \(\sigma : \mathbb F \to \mathbb F\) is a field automorphism and multiplication is defined by \(xa = \sigma(a)x\) for all \(a \in \mathbb F\). The first problem is the problem of complete factorization in \(\mathbb F[x;\sigma]\), that is to write a non-constant \(f \in \mathbb F[x;\sigma]\) as a product of irreducible elements of \(\mathbb F[x;\sigma]\). The second problem is the bi-factorization problem, namely to determine for a given non-constant \(f \in \mathbb F[x;\sigma]\) and a given natural number \(s\) if there exist elements \(g\), \(h \in \mathbb F[x;\sigma]\) such that \(f = gh\) and \(\deg(h) = s\) and to compute such polynomials \(g\) and \(h\) in case of existence. The complete factorization problem is reduced to the problem of determining whether a finite-dimensional associative algebra \(\mathfrak{A}\) possesses non-trivial zero-divisors, and if so, finding non-zero \(x,y \in \mathfrak{A}\) such that \(xy = 0\). Here the author describes a new fast algorithm. The bi-factorization problem is reduced to the complete factorization problem. Detailed descriptions of all algorithms and estimations of their complexity are given. The results on factorizations in a ring \(\mathbb F[x;\sigma]\) are applied on functional decompositions of a special class of (ordinary) polynomials \(f \in \mathbb F[x]\) possessing ``wild'' decompositions.
Mathematics Subject Classification ID: 16Z05
Mathematics Subject Classification ID: 16S36
Mathematics Subject Classification ID: 68W30
zbMATH DE Number: 1216480
zbMATH Keywords: skew-polynomial rings
zbMATH Keywords: factorization
zbMATH Keywords: functional decomposition
author: Mark Giesbrecht
reviewed by: Friedrich Schwarz
MaRDI profile type: Publication
OpenAlex ID: W1990226699
DOI: 10.1006/JSCO.1998.0224
description: scientific article; zbMATH DE number 1216480