ON THE DETERMINISTIC COMPLEXITY OF FACTORING POLYNOMIALS OVER FINITE-FIELDS

We present a new deterministic algorithm for factoring polynomials over Zp of degree n. We show that the worst-case running time of our algorithm is O(p 1 2(log p)2n2+∈), 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 Zp. Specifically, we prove that the fraction of polynomials of degree n over Zp for which our algorithm fails to halt in time O((log p)2n2+∈) is ((n log p)2/p). Consequently, the average-case running time of our algorithm is polynomial in n and log p. © 1990.