Alexei Sheplyakov wrote:
Hello!
Heuristic code in gcd [very] often makes bad choice of the main variable. In particular, if one of polynomials (say, p2) does not contain the variable x which _is contained_ in another one (say, p1), than gcd(p1, p2) will use such a variable as a main, so subsequent calculation becomes unnecessary complicated. Fixing this substantially improves worst case performance (less than minute versus infinity).
hello, in this case, you should compute the content with respect to x of p1 and then the gcd of the content with p2. A good candidate for the gcd will be the gcd of p2 with a random integer linear combination of the coeffs of p1 with respect to x. Anyway, heuristic gcd is most of the time not a good choice if there are more than a few variables. Modular gcd is in my experience faster (and this is theoretically also true).