To expedite the computation, take a ring "D" for which "f" and "g" are in "D"["x"], and take an ideal "I" such that "D"/"I" 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 "f" and "g" from its image modulo a number of ideals "I". One can prove that this works provided that one discards modular images with non-minimal degrees, and avoids ideals "I" modulo which a leading coefficient vanishes.