The key algorithm is Algorithm 4, called the Half-GCD algorithm. This algorithm originated in the ideas of Lehmer, Knuth and Schönhage. Though, it has appeared in many books including [AA74,Yap93,GG99] and in many other publications, it is frequently specified incorrectly. This creates an implementation challenge. We adapted Yap's [Yap93]
Marc Moreno Maza