Given two polynomials of degree with coefficients from a field , the straightforward Eucliean Algorithm uses field operations to compute their greatest common divisor. The Fast Euclidean Algorithm computes the same GCD in field operations, where is the time to multiply two -degree polynomials; with FFT multiplication the GCD can thus be computed in time . 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 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 . The basic idea is that the quotients computed by the Euclidean Algorithm can usually be computed by looking at only the first few coefficients of the polynomial; for example, if

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 or less from both polynomials and . Then, we recursively compute their GCD and Euclidean coefficients. We then apply the Euclidean coefficients to and , 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.