Symbolic Computation Group

David R. Cheriton School of Computer Science
University of Waterloo, Waterloo, Ontario, Canada

On Polynomial Gcds over Direct Product of Fields
Marc Moreno Maza, University of Western Ontario
Friday, April 2, 2004, at U. of Western Ontario.


Let K be a field of rational functions and L be a direct product of fields extending K by a tower of simple algebraic extensions. We present a modular algorithm for computing polynomial gcds over L based on a Hensel lifting strategy.

The rational reconstruction is avoided by "guessing" the denominator of the gcd before the lifting step. The algorithm is probabilistic but succeeds with probability one. Our implementation shows a significant improvement with respect to other methods.

This is joint work with Cosmin Oancea based on a preliminary study with Francois Boulier.


Last modified on Sunday, 04 November 2012, at 15:42 hours.