Revision #3 Authors: Vikraman Arvind, Pushkar Joglekar

Accepted on: 27th February 2022 20:16

Downloads: 226

Keywords:

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.

Revision #2 Authors: Vikraman Arvind, Pushkar Joglekar

Accepted on: 20th February 2022 21:38

Downloads: 184

Keywords:

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.

Revision #1 Authors: Vikraman Arvind, Pushkar Joglekar

Accepted on: 19th February 2022 12:53

Downloads: 217

Keywords:

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.

TR22-022 Authors: Vikraman Arvind, Pushkar Joglekar

Publication: 19th February 2022 07:28

Downloads: 283

Keywords:

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.