  In this paper we study the problem of efficiently factorizing polynomials in
the free noncommutative ring F<x_1,x_2,...,x_n> 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<x_1,x_2,...,x_n> 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 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.
