Revision history [back]

I do not know whether there is a good solution. Actually, the problem you are trying to solve is NP-hard so there is probably no efficient algorithm. (Note that of course computing the GCD of two dense (or low-degree) polynomials in not hard, the problem here is the degree. )