Home Research People Courses Conferences Seminars Publications Resources

[Gao01a]
Shuhong Gao,
On the deterministic complexity of polynomial factoring,''
J. Symbolic Computation 31 (2001), 19--36.

Abstract:
The 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 Zassenhaus (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 {\em super square balanced}.  It is conjectured that  super square balanced polynomials do not exist.