Symbolic Computation Group

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.