By the way, I would guess that Maxima's algorithms are not optimal for very large polynomials. There are also some known bugs in factorization of largish multivariate polynomials. I don't know about GCD.