  In this paper, we propose a carefully optimized "half-gcd" algorithm for
polynomials. We achieve a constant speed-up with respect to previous work for
the asymptotic time complexity. We also discuss special optimizations that are
possible when polynomial multiplication is done using radix two FFTs.
