Fast Extended Euclidean Algorithm

In this section, we assume that $ R$ 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 $ R$ for input polynomials in degree $ d$ .

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