# fast Euclidean algorithm

Given two polynomials of degree $n$ with coefficients from a field $K$, the straightforward Eucliean Algorithm^{} uses $O({n}^{2})$ field operations^{} to compute their greatest common divisor^{}. The Fast Euclidean Algorithm computes the same GCD in $O(\U0001d5ac(n)\mathrm{log}(n))$ field operations, where $\U0001d5ac(n)$ is the time to multiply two $n$-degree polynomials; with FFT multiplication^{} the GCD can thus be computed in time $O(n{\mathrm{log}}^{2}(n)\mathrm{log}(\mathrm{log}(n)))$. The algorithm can also be used to compute any particular pair of coefficients from the Extended Euclidean Algorithm^{}, although computing every pair of coefficients would involve $O({n}^{2})$ outputs and so the efficiency is not as helpful when all are needed.

The algorithm can be made to work over $\mathbb{Z}$ but it is very tricky. A newer version that is easier to understand was published by Damien Stehlé and Paul Zimmerman, “A Binary Recursive Gcd Algorithm.”

Here we sketch the algorithm over $K[x]$. The basic idea is that the quotients ${q}_{i}$ computed by the Euclidean Algorithm can usually be computed by looking at only the first few coefficients of the polynomial; for example, if

$$A(x)={a}_{n}{x}^{n}+{a}_{n-1}{x}^{n-1}+\mathrm{\dots}+{a}_{0},B(x)={b}_{n-1}{x}^{n-1}+\mathrm{\dots}+{b}_{0}$$ |

then

$$quo(A(x),B(x))=\frac{{a}_{n}}{{b}_{n-1}}x+\frac{{b}_{n-1}{a}_{n-1}-{a}_{n}{b}_{n-2}}{{b}_{n-1}^{2}}$$ |

With more detailed analysis, we can show that in fact a divide-and-conquer approach can be used to calculate the GCD. First, we remove the terms whose degree is $n/2$ or less from both polynomials $A$ and $B$. Then, we recursively compute their GCD and Euclidean coefficients. We then apply the Euclidean coefficients to $A$ and $B$, and recursively complete^{} the Euclidean Algorithm.

The full algorithm, and a comprehensive runtime analysis is given in “Modern Computer Algebra” by von zur Gathen and Gerhard.

Title | fast Euclidean algorithm |
---|---|

Canonical name | FastEuclideanAlgorithm |

Date of creation | 2013-03-22 14:28:52 |

Last modified on | 2013-03-22 14:28:52 |

Owner | mathcam (2727) |

Last modified by | mathcam (2727) |

Numerical id | 7 |

Author | mathcam (2727) |

Entry type | Algorithm |

Classification | msc 11A05 |

Synonym | Half-GCD Algorithm |

Synonym | Lehmer’s Algorithm |

Related topic | EuclidsAlgorithm |