# Berlekamp’s Q-matrix algorithm

Let *f(x) =* П(=1 *fi ( ^{x})* be a monic polynomial in F

_{4}[x] of degree n having distinct irreducible factors

*f,(x),*1 <

*i < t.*Berlekamp’s Q-matrix algorithm (Algorithm 3.111) for factoring

*f(x)*is based on the following facts. The set of polynomials

is a vector space of dimension *t* over F_{4}. *В* consists of precisely those vectors in the null space of the matrix Q - *I _{n},* where Q is the n x n matrix with (г, j)-entry

*q*specified by

_{t}j

and where *I _{n}* is the

*n*x

*n*identity matrix. A basis

*В*= (vi(x),U2(x),... ,u

_{4}(x)} for

*В*can thus be found by standard techniques from linear algebra. Finally, for each pair of distinct factors

*f,(x)*and

*j)(x)*of

*f(x)*there exists some

*vk{x)*6

*В*and some

*a*e F

_{4 }such that

*fi(x)*divides

*vk(x)*-

*a*but

*fj(x)*does not divide

*vk(x)*- o; these two factors can thus be split by computing gcd(/(x),

*vk{x) - a).*In Algorithm 3.111, a vector

*w =*(wo,W!,... ,

*w*i) is identified with the polynomial

_{n}~*w(x) = Y^’t=o*

^{w}i^{x}‘■**3.111 Algorithm **Berlekamp’s Q-matrix algorithm for factoring polynomials over finite fields

INPUT: a square-free monic polynomial *f(x)* of degree *n* in FJx],

OUTPUT: the factorization of *f(x)* into monic irreducible polynomials.

1. For each *i,* 0 < *i* < *n —* 1, compute the polynomial

Note that each *qij* is an element of F_{(/}.

- 2. Form the
*n*x*n*matrix Q whose (г, j)-entry is*qy.* - 3. Determine a basis
*V**1**.V**2*,...*,v*for the null space of the matrix (Q -_{t}*I*where_{n}),*I*is the_{n }*n*x*n*identity matrix. The number of irreducible factors of*f(x)*is precisely*t.* - 4. Set
*F*is the set of factors of *f(x)*found so far; their product is equal

to *f(x).)*

- 5. For
*i*from 1 to*t*do the folio whig: - 5.1 For each polynomial
*h(x) e F*such that deg*h(x) >*1 do the following: compute gcd(/t(.r),*Vi(x) - a)*for each*a*e F_{(;}, and replace*h(x)*in*F*by all those polynomials in the gcd computations whose degrees are > 1. - 6. Retum(the polynomials in
*F*are the irreducible factors of*f(x)).* - 3.112
**Fact**The running time of Algorithm 3.111 for factoring a square-free polynomial of degree*n*over Fis_{q}*0(n*^{3}+*tqn*^{2}) F_{(},-operations, where*t*is the number of irreducible factors of*f(x).*Tlie method is efficient only when*q*is small.