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 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.
展开▼
