Photo credit: Pierre Jayet – Grenoble Tourisme & Congrès

Home Call for Papers Programming Contest Invited Speakers and Tutorials A3-poster Committees Local information Registration Program Proceedings

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.