fast Euclidean algorithm


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

The algorithm can be made to work over 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 qi 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)=anxn+an-1xn-1++a0,B(x)=bn-1xn-1++b0

then

quo(A(x),B(x))=anbn-1x+bn-1an-1-anbn-2bn-12

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 completePlanetmathPlanetmathPlanetmathPlanetmath 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