text: Modular GCD algorithm If  and  are polynomials in  for some finitely generated field , the Euclidean Algorithm is the most natural way to compute their GCD. However, modern computer algebra systems only use it if  is finite because of a phenomenon called intermediate expression swell. Although degrees keep decreasing during the Euclidean algorithm, if  is not finite then the bit size of the polynomials can increase (sometimes dramatically) during the computations because repeated arithmetic operations in  tends to lead to larger expressions. For example, the addition of two rational numbers whose denominators are bounded by  leads to a rational number whose denominator is bounded by , so in the worst case, the bit size could nearly double with just one operation.
  To expedite the computation, take a ring  for which  and  are in , and take an ideal  such that  is a finite ring. Then compute the GCD over this finite ring with the Euclidean Algorithm. Using reconstruction techniques (Chinese remainder theorem, rational reconstruction, etc.) one can recover the GCD of  and  from its image modulo a number of ideals . One can prove that this works provided that one discards modular images with non-minimal degrees, and avoids ideals  modulo which a leading coefficient vanishes.
  Suppose , ,  and . If we take  then  is a finite ring (not a field since  is not maximal in ). The Euclidean algorithm applied to the images of  in  succeeds and returns 1. This implies that the GCD of  in  must be 1 as well. Note that this example could easily be handled by any method because the degrees were too small for expression swell to occur, but it illustrates that if two polynomials have GCD 1, then the modular algorithm is likely to terminate after a single ideal .