Designing a deterministic polynomial time algorithm for factoring univariate polynomials over finite fields remains a notorious open problem. In this paper, we present an unconditional deterministic algorithm that takes as input an irreducible polynomial $f \in \mathbb{ Z}[x]$, and computes the factorisation of its reductions modulo $p$ for all primes $p$ up to a prescribed bound $N$. The \emph{ average running time per prime} is polynomial in the size of the input and the degree of the splitting field of $f$ over $\mathbb{ Q}$. In particular, if $f$ is Galois, we succeed in factoring in (amortised) deterministic polynomial time.
Categories: math.NT cs.CC