Tutte seminar - Bruce Richmond

Factoring Polynomials over a Finite Field

Abstract:

The basic algorithms for factoring polynomials over a finite field go back two hundred years, according to the book Modern Computer Algebra by Joachim von zur Gathen and Jürgen Gerhard. It seems Galois first publised an algorithm but this algorithm was given previously by Gauss in sources unpublished until after his death.

There has been rapid progress in the last 20 years. There is now an algorithm of von zur Gathen and Gerhard that factored a pseudorandom polynomial of degree more than 1,000,000 in four days of CPU time on a Linux PC with four Pentium III processors clocked at 500 MHz (whatever that means).

Recently von zur Gathen, Panario and I published a paper in Algorithmica (2012) 63:363-397 analyzing a factoring method of Cantor and Zassenhaus. This algorithm partitions the set of potential factor degrees into intervals [s_k-1+1,s_k]. It turns out that the optimal choice for s_k is s_k=k^1/3. In this case a polynomial of degree n requires calculating n^1/3 gcds.