On the Deterministic Complexity of Factoring Polynomials

AbstractThe paper focuses on the deterministic complexity of factoring polynomials over finite fields assuming the extended Riemann hypothesis (ERH). By the works of Berlekamp (1967, 1970) and Zassenbaus (1969), the general problem reduces deterministically in polynomial time to finding a proper factor of any squarefree and completely splitting polynomial over a prime field Fp. Algorithms are designed to split such polynomials. It is proved that a proper factor of a polynomial can be found deterministically in polynomial time, under ERH, if its roots do not satisfy some stringent condition, called super square balanced. It is conjectured that super square balanced polynomials do not exist