Factorization of polynomials over finite fields and characteristic sequences (Q1322768)

The first author has recently introduced a new algorithm for the efficient factorization of polynomials over finite fields [Appl. Algebra Eng. Commun. Comput. 4, 81-87 (1993; Zbl 0776.11070)]. Several researchers have generalized the algorithm and suggested techniques for speeding it up. It is noted there are two techniques for generalizing the algorithm, by using either normal bases of field extensions or by applying Hasse-Teichmüller derivatives. This work considers the second techniques using derivatives and shows, in particular, that the linearization step of the general factorization algorithm using these derivatives is feasible for arbitrary finite fields. A general principle for linearizing the factorizing problem for polynomials is introduced which is derived from a certain decimation operator on sequences. The linearization using derivatives is an application of this principle.