On the deterministic complexity of factoring polynomials over finite fields

We present a new deterministic algorithm for factoring polynomials over Z_p of degree n. We show that the worst-case running time of our algorithm is O(p ^{1 2}(log p)²n^2+∈), which is faster than the running times of previous determi nistic algorithms with respect to both n and p. We also show that our algorithm runs in polynomial time for all but at most an exponentially small fraction of the polynomials of degree n over Z_p. Specifically, we prove that the fraction of polynomials of degree n over Z_p for which our algorithm fails to halt in time O((log p)²n^2+∈) is ((n log p)²/p). Consequently, the average-case running time of our algorithm is polynomial in n and log p.