In this paper we study the problem of efficiently factorizingpolynomials in the free noncommutative ring \(\mathbb{F}<{x_1,x_2,\ldots,x_n}>\) of polynomials in noncommutingvariables \(x_1,x_2,\ldots,x_n\) over the field \(\mathbb{F}\) . We obtainthe following result: Given a noncommutative algebraic branching program of size \(s\) computing a noncommutative polynomial \(f\in\mathbb{F}<{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 linearization of polynomials. We then factorize thelinear matrix \(L\) and recover the factorization of \(f\) . We use basicelements from Cohn's theory of free ideals rings combined withRonyai's randomized polynomial-time algorithm for computing anontrivial common invariant subspace of a collection of matrices overfinite fields.
