**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]
**

*
*

*
*

2008-01-07