GCD of univariate polynomials with integer coefficients

Problem specification

The problem is to compute as quickly as possible the gcd of two univariate polynomials with integer coefficients. Participants are free to use any piece of software for integer arithmetic or polynomial operations or any other library of their choice.

Specification of the program input/output

The participant must provide a program with the following specification:

For example, the polynomial 10*x⁴ - 11*x³ + 12*x² - 13 would be:

4 10
3 -11
2 12
0 -13

Usage: To compute gcd(A,B) = C, run the program

gcd A B C

where the arguments A, B and C are files storing polynomials.

Reference implementation

We provide a reference implementation using GMP: gcdref.zip.

Sample instances

A,B: deg=100 bits=20
gcd: deg= 10 bits=10

A,B: deg=1000 bits=1000
gcd: deg= 100 bits= 500

A,B: deg=10000 bits=1000
gcd: deg= 1000 bits= 500

A,B: deg=10000 bits=10000
gcd: deg= 5000 bits= 5000
mayhem.zip (warning: 100MB file)

Reference times on a Core i5 750 2.66 - 3.2 GHz with GMP 5.0 are 0.001, 0.21, 4.1, and 160 seconds. We do Kronecker substitution and call GMP's integer gcd, which is asymptotically fast in 5.0.