FACTORIZATION OF POLYNOMIALS OVER FINITE-FIELDS AND CHARACTERISTIC SEQUENCES

A new factorization algorithm for polynomials over finite fields was r ecently developed by the first author. For finite fields of characteri stic 2, it is known from previous work that this algorithm has several advantages over the classical Berlekamp algorithm. In this paper we s how that the linearization step in the new algorithm is feasible-in th e sense that it can be carried out in polynomial time-for arbitrary fi nite fields, by using an approach based on decimation operators and ch aracteristic linear recurring sequences. We also introduce a general p rinciple for the linearization of the factorization problem for polyno mials over finite fields.