On the deterministic complexity of factoring polynomials

The paper focuses on the deterministic complexity of factoring polynomials over finite fields assuming the extended Riemann hypothesis (ERH). By the w orks of Berlekamp (1967, 1970) and Zassenbaus (1969), the general problem r educes deterministically in polynomial time to finding a proper factor of a ny squarefree and completely splitting polynomial over a prime field F-p. A lgorithms are designed to split such polynomials. It is proved that a prope r factor of a polynomial can be found deterministically in polynomial time, under ERH, if its roots do not satisfy some stringent condition, called su per square balanced. It is conjectured that super square balanced polynomia ls do not exist. (C) 2001 Academic Press.