Deterministic Factorization of Polynomials over Finite Fields

We give new results for the problem of deterministically and unconditionally factoring polynomials over finite fields. We give efficient algorithms for the factorization of some odd degree polynomials over finite fields. We remove the assumption of the Extended Riemann Hypothesis from a well known algorithm for factoring polynomials over finite fields in the case that the degree of the polynomial to be factored is coprime to phi(p-1) where p is the characteristic of the field and phi is the Euler totient function. We also give new results on the factorization of polynomials of bounded degree. Using new tools we give a concrete proof of a result from the literature that a polynomial of degree n over the finite field can be factored deterministically in a number of operations that is polynomial in n^l where l is the least prime factor of n and log(p).