FACTORING MODULAR POLYNOMIALS

This paper gives an algorithm to factor a polynomial f (in one variabl e) over rings like Z/rZ for r is an element of Z or F-q[y]/rF(q)[y] fo r r is an element of F-q[y]. The Chinese Remainder Theorem reduces our problem to the case where r is a prime power. Then factorization is n ot unique, but if r does not divide the discriminant of f, our (probab ilistic) algorithm produces a description of all (possibly exponential ly many) factorizations into irreducible factors in polynomial time. I f r divides the discriminant, we only know how to factor by exhaustive search, in exponential time. (C) 1998 Academic Press.