Factoring modular polynomials (Q1273766)

Let \(R\) be either \(Z\) or \(F_q [y]\), \(F_q\) the finite field containing \(q\) elements, and let \(r \in R\) be a non-zero non-unit. The aim of the work is to describe all possible factorizations into irreducibles of polynomials in \(R[x]\) over the ring \(R/(r)\) where \((r)\) is the ideal generated by \(r\). Factorization of polynomials into irreducible factors over such rings is not unique. For example: \[ x^2 \equiv (x- \alpha p)(x+ \alpha p)\bmod{p^2} \] for all \(\alpha \in \{ 0,1,\dots , p-1 \}\). An example due to Shamir shows that for certain rings, non-trivial factors of \(f\) can have the same degree as \(f\): e.g for \(r=pq\) for different (non-associate) primes, then \(p^2 +q^2\) is a unit in \(Z/(r)\) and \[ x \equiv (p^2 + q^2)^{-1} (px+q)(qx+p)\bmod{r}. \] It is first shown that the problem can be reduced, by use of the Chinese remainder theorem and a generalization of Hensel's lemma, to the case where \(r \in R\) is a prime power, or the power of an irreducible polynomial modulo the prime. The main result of the paper is then an algorithm for finding all irreducible factorizations if \(r = p^k\). The algorithm only works when the discriminant of the polynomial is not divisible by \(p^k\). In particular, the polynomial to be factored must be square-free. In this case the algorithm produces a description of all factorizations and is polynomial in time, even when there exist exponentially many irreducible factors. In the case when \(r\) divides the discriminant, the only known algorithm for factorization is by exhaustive search, in exponential time.