Factoring modular polynomials (extended abstract)
Joachim von zur Gathen, Silke Hartlieb · 1996
This paper gives analgorithm to factor apolynomialf (in one variable) over residue class rings of ZoriFq [y].The Chinese Remainder Theorem reduces our problem to the case where r is a prime power.Then factorization is not unique, but if r does not divide the discriminant of f, our (probabilistic) algorithm produces a description of all (possibly exponentially many) factorization into irreducible factors in polynomial time.If ~divides the discriminant, we only know how to factor by exhaustive search, in exponential time.