On the genericity of the modular polynomial GCD algorithm
Erich Kaltofen, Michael Monagan · 1999
In this paper we st,udy the generic setting of the modular GCD algorithm.We develop the algorithm for multivariate polynomials over Euclidean domains which have a spc:&l kind of remainder function.Details for the parameterixation and generic Maple code are given.Applying this grncric algorithm to a GCD problem in Z/(~) [t][z] where 1~ is small yields an improved asymptotic performance over t.he usual approach, and a very practical algorithm for polynomials over small finite fields.