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.
The participant must provide a program with the following specification:
For example, the polynomial 10*x⁴ - 11*x³ + 12*x² - 13 would be:
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.
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.