In this paper we study the problem of efficiently factorizing polynomials in the free noncommutative ring F of polynomials in noncommuting variables x_1,x_2,…,x_n over the field F. We obtain the following result:
Given a noncommutative arithmetic formula of size s computing a noncommutative polynomial f in F as input, where F=F_q is a finite field, we give a randomized algorithm that runs in time polynomial in s, n and log q that computes a factorization of the polynomial f as a product f=f_1f_2… f_r, where each f_i is an irreducible polynomial that is output as a noncommutative algebraic branching program.
The algorithm works by first transforming f into a linear matrix L using Higman's linearization of polynomials. We then factorize the linear matrix L and recover the factorization of the polynomial f. We use basic elements from Cohn's theory of free ideals rings combined with Ronyai's randomized polynomial-time algorithm for computing invariant subspaces of a collection of matrices over finite fields.
Added a discussion on factorization of polynomials over small finite fields.
In this paper we study the problem of efficiently factorizing polynomials in the free noncommutative ring $\mathbb{F}\langle x_1,x_2,\ldots, x_n\rangle $ of polynomials in noncommuting variables $x_1,x_2,\ldots,x_n$ over the field $\mathbb{F}$. We obtain the following result:
Given a noncommutative arithmetic formula of size $s$ computing a noncommutative polynomial
$f\in\mathbb{F}\langle x_1,x_2,\ldots,x_n \rangle$ as input, where $\mathbb{F}=\mathbb{F}_q$ is a finite field, we give a randomized algorithm that runs in time polynomial in $s$, $n$ and $\log_2q$ that computes a factorization of $f$ as a
product $f=f_1f_2\cdots f_r$, where each $f_i$ is an irreducible polynomial that is output as a noncommutative algebraic branching program.
The algorithm works by first transforming $f$ into a linear matrix $L$ using Higman's linearization of polynomials. We then factorize the linear matrix $L$ and recover the factorization of $f$. We use basic elements from Cohn's theory of free ideals rings combined with Ronyai's randomized polynomial-time algorithm for computing invariant subspaces of a collection of matrices over
finite fields.
Corrected a typographical error in Lemma 4.8, where the relation $Cv=0$ was missing.
In this paper we study the problem of efficiently factorizing polynomials in the free noncommutative ring $\mathbb{F}\angle{x_1,x_2,\ldots,x_n}$ of polynomials in noncommuting variables $x_1,x_2,\ldots,x_n$ over the field $\mathbb{F}$. We obtain the following result:
Given a noncommutative arithmetic formula of size $s$ computing a noncommutative polynomial $f\in\mathbb{F}\angle{x_1,x_2,\ldots,x_n}$ as input, where $\mathbb{F}=\mathbb{F}_q$ is a finite field, we give a randomized algorithm that runs in time polynomial in $s, n$ and $\log_2q$ that computes a factorization of $f$ as a product $f=f_1f_2\cdots f_r$, where each $f_i$ is an irreducible polynomial that is output as a noncommutative algebraic branching program.
The algorithm works by first transforming $f$ into a linear matrix $L$ using Higman's linearization of polynomials. We then factorize the linear matrix $L$ and recover the factorization of $f$. We use basic elements from Cohn's theory of free ideals rings combined with Ronyai's randomized polynomial-time algorithm for computing invariant subspaces of a collection of matrices over finite fields.
used Tex formatting in the abstract.
In this paper we study the problem of efficiently factorizing polynomials in the free noncommutative ring F of polynomials in noncommuting variables x_1,x_2,…,x_n over the field F. We obtain the following result:
Given a noncommutative arithmetic formula of size s computing a noncommutative polynomial f in F as input, where F=F_q is a finite field, we give a randomized algorithm that runs in time polynomial in s, n and log q that computes a factorization of the polynomial f as a product f=f_1f_2… f_r, where each f_i is an irreducible polynomial that is output as a noncommutative algebraic branching program.
The algorithm works by first transforming f into a linear matrix L using Higman's linearization of polynomials. We then factorize the linear matrix L and recover the factorization of the polynomial f. We use basic elements from Cohn's theory of free ideals rings combined with Ronyai's randomized polynomial-time algorithm for computing invariant subspaces of a collection of matrices over finite fields.
