Factorization of Noncommutative Polynomials

概要

論文の詳細を見る
Two factorization methods of a polynomial with noncommutative multiplication are proposed. One of the methods factorizes a noncommutative polynomial by computing coefficients of factors as factorization by constructing and solving several equations. We call this the naïve method. This is simple, but does not factorize efficiently. To do this efficiently, an alternative method. This is simple, but does not factorize efficiently. To do this efficiently, an alternative method is proposed, which is called the constant term method. This factorizes a noncommutative polynomial in one of two ways according to its constant term. If the constant term of a polynomial is zero, the polynomial is factorized by classifying its monomials based on the leftmost and rightmost variables and by linear combinations of polynomials. An irreducible factor is obtained from this factorization. If its constant term is not zero, first, the constant term is reduced to zero by linear transformations of variables and an extension of the coefficient field, and then, the polynomial is factorized in the same manner as when a constant term is zero. After that, by computing the least common multiple, an irreducible factor over the original domain is obtained from irreducible factors over the extension field. This method, however, cannot be applied to noncommutative polynomials whose constant terms cannot be reduced to zero. To factorize such noncommutative polynomials, the former method is used. It is shown that the latter method is faster than the former. In the two proposed methods, factorizations over a finite field are not used explicitly, comparing with the factorization algorithms for usual commutative polynomials.
一般社団法人情報処理学会の論文
1993-11-15

Factorization of Noncommutative Polynomials

スポンサーリンク

概要

著者

関連論文

スポンサーリンク