Modular GCD

also: crt, chinese remainder, brown's algorithm

Computing a polynomial GCD over Z by computing it modulo several machine-word primes and reconstructing by the Chinese remainder theorem, stopping once the modulus provably exceeds twice the largest coefficient the answer could have. The answer is small even when the road to it is not, which is why this is orders of magnitude faster than any remainder sequence.

The answer is small even when the road to it is not: the GCD of two polynomials with ten-digit coefficients has coefficients of about the same size. There is therefore no reason to ever hold a three-thousand-digit intermediate, and the modular algorithm never does.

The shape of it.

for each machine-word prime p (skipping bad ones):
    reduce both inputs mod p           coefficients are now ints
    take the gcd in F_p[x]             plain Euclid: F_p is a field
    combine with the previous primes   Chinese remainder theorem
until the modulus exceeds twice the coefficient bound
then verify by trial division

Two primes have to be rejected. One dividing the leading coefficients drops the degree; an unlucky one gives an image GCD of too high a degree, detected by comparing against the accumulation so far. An image of smaller degree invalidates everything collected before it, so the accumulation restarts.

The final trial division is not optional. The bound is a bound on the true GCD, and an unlucky run of primes can converge on a proper multiple of it, so dividing into both inputs is what turns a likely answer into a certain one.

Both algorithms on the same random inputs with a planted common factor. Verbatim.

deg(g)   deg(a)        prs (s)  modular (s) max digits
8        16             0.0041       0.0005         18
16       32             0.0541       0.0008         19
24       48             0.2715       0.0012         19
32       64             0.7490       0.0020         19
40       80             1.7554       0.0026         19
48       96             3.5659       0.0033         19

Roughly a thousand times faster at degree 96, and the gap widens. The last column is why: the answer's size never moves, so the modular cost grows linearly while the remainder sequence grows faster than the cube of the degree.