FACTORING POLYNOMIALS USING BINARY REPRESENTATIONS OF FINITE-FIELDS

The factorization of polynomials over finite fields is considered, A n ew deterministic algorithm is proposed that solves the equal-degree fa ctorization problem by combining Berlekamp's trace algorithm with the concept of binary representations of finite fields, The interesting as pects of the new algorithm are its simple structure, the easy proof of its correctness, and its efficiency when an efficient realization of the mapping from the finite field to a binary representation is known, Some results about binary representations of finite fields are derive d to show that the new factoring algorithm is also nonasymptotically e fficient for every finite field. The only practical drawback may be th e precomputation of some constants needed in the binary representation , but several suggestions are given to improve this when more about th e finite field is known.