FACTORING POLYNOMIALS OVER FINITE-FIELDS USING DIFFERENTIAL-EQUATIONSAND NORMAL BASES

The deterministic factorization algorithm for polynomials over finite fields that was recently introduced by the author is based on a new ty pe of linearization of the factorization problem. The main ingredients are differential equations in rational function fields and normal bas es of field extensions. For finite fields of characteristic 2, it is k nown that this algorithm has several advantages over the classical Ber lekamp algorithm. We develop the algorithm in a general framework, and we show that it is feasible for arbitrary finite fields, in the sense that the linearization can be achieved in polynomial time.