On the deterministic complexity of factoring polynomials (Q5928878)

The problem considered is factoring polynomials over finite fields. In 1970 Berlekamp published an algorithm solving this problem in probabilistic polynomial time. It is still an open question whether there exists a deterministic polynomial time algorithm, even under the extended Riemann hypothesis (ERH). Since 1992, several authors have given, under ERH, efficient algorithms for special classes of polynomials or for polynomials over special fields. This paper continues this line of research for deterministic polynomial time algorithms under GRH. The paper contains such a result which applies to polynomials which do not satisfy a very stringent condition. The other one conjectures that the class of polynomials satisfying this condition is empty.