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 algebraic branching program 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 the given algebraic branching program computing 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.
The main result of the previous version has been strengthened to efficient factorization of noncommutative polynomials given by ABP as input.
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.
