## 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:

**Polynomial file storage format**: a polynomial having *N* non-zero terms will be stored in a file having *N+1* lines.
- First line: the number
*N* of non-zero terms
- Each of the following lines will contain the degree of a term followed by its coefficient. These are separated by a space. The terms will be given in order of descending degree.

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

4

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

fun.zip

A,B: deg=1000 bits=1000

gcd: deg= 100 bits= 500

tricky.zip

A,B: deg=10000 bits=1000

gcd: deg= 1000 bits= 500

taxing.zip

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.