Factoring Polynomials Over Finite Fields

We present here an algorithm for factoring a given polynomial over GF(q) into powers of irreducible polynomials. The method reduces the factorization of a polynomial of degree m over GF{q) to the solution of aboid m(q -- 1 )/q linear equations in as many unknowns over GF(q). There are many applications in which one wishes to factor polynomials. Some programming systems, such as Brown's ALPAK, 1 deal with polynomials and rational functions with integer coefficients. In such a context one is interested not in approximate numerical values for the real and complex roots, but rather in irreducible factors which are themselves polynomials with integer coefficients. One of the standard tricks mentioned by Johnson2 for finding such irreducible factors is to reduce all of the coefficients of the original polynomial modulo some prime, p, and then factor the reduced polynomial over the Galois Field, GF{p). If the reduced polynomial factors, one gets certain constraints on the factors of the original polynomial; if the reduced polynomial does not factor over GF(p), then one may conclude that the original polynomial is irreducible over the integers. The success of this method for factoring polynomials over the integers clearly depends upon having an efficient procedure for factoring polynomials over GF(p). The problem of factoring polynomials over finite fields arises directly in Golomb's study3 of feedback shift register sequences. In Golomb's words, this study . . has found major applications in a wide variety of technological situations, including secure, reliable and efficient communications, digital ranging and tracking systems, deterministic simulation of random processes, and computer sequencing and timing schemes." The properties of all cyclic error correcting codes, including the important Bose-Chaudhuri'-Hocquenghem5 codes, de1853 1854 T H E BELL SYSTEM TECHNICAL JOURNAL, OCTOBER 19G7 pend on the factors of their generator polynomials in some finite field.