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 $33\, \ensuremath{\mathsf{M}}(d)\log(d)+O(d\, \log(d))$ operations $(+,\times,\div)$ 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

$\fbox{ \begin{minipage}{12 cm} \begin{description} \item[{\sc Input:}] $a,\, b\,... ...{\sc 17} \> \> \mbox{{\bf return}} $M_3 M_2 M_1$\ \end{tabbing}\end{minipage}}$

Algorithm 5

$\fbox{ \begin{minipage}{12 cm} \begin{description} \item[{\sc Input:}] $a,\, b\,... ... 10} \> \> \mbox{{\bf return}} $M_3\, M_2\, M_1$\ \end{tabbing}\end{minipage}}$

Algorithm 6

$\fbox{ \begin{minipage}{12 cm} \begin{description} \item[{\sc Input:}] $a,\, b\,... ...> \> \mbox{{\bf else return}} {\rm FEEA}$(b,a)$\\ \end{tabbing}\end{minipage}}$

Marc Moreno Maza
2008-01-07