## Fast Extended Euclidean Algorithm

In this section, we assume that is a field. Algorithm 6 has the same specifications as the EEA and runs in operations in for input polynomials in degree .

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]

Algorithm 4

Algorithm 5

Algorithm 6

Marc Moreno Maza
2008-01-07