 Berlekamp’s Q-matrix algorithm

Let f(x) = П(=1 fi (x) be a monic polynomial in F4[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 F4. В consists of precisely those vectors in the null space of the matrix Q - In, where Q is the n x n matrix with (г, j)-entry qtj specified by and where In is the n x n identity matrix. A basis В = (vi(x),U2(x),... ,u4(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 F4 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!,... , wn~i) is identified with the polynomial w(x) = Y^’t=o wix‘■

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 V1.V2,... ,vt for the null space of the matrix (Q - In), where In is the 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 Fq is 0(n3 + tqn2) F(,-operations, where t is the number of irreducible factors of f(x). Tlie method is efficient only when q is small.