CSAIL Event Calendar: Previous Series

Fast Polynomial Factorization and Modular Composition in Small Characteristic

Speaker: Chris Umans , Caltech
Date: March 18 2008
Time: 4:15PM to 5:25PM
Location: 32-155
Host: Madhu Sudan, MIT

I'll describe a new algorithm for univariate polynomial
factorization over F_q that uses roughly O(n^{1.5} + nlog q) field
operations, when the characteristic is at most n^{o(1)}. This asymptotically
beats all previous algorithms when log q < n and matches them when log q >=
n.

The improvement comes from a new algorithm for "modular composition," which
is the bottleneck in modern polynomial factorization algorithms. Modular
composition is the problem: given degree n polynomials f(x), g(x), h(x),
compute f(g(x)) mod h(x). It is a very natural operation on polynomials,
which lies at the core of algorithms for basic algebraic problems like
irreducibility testing, manipulating normal bases, constructing minimal
polynomials, and others.

The only nontrivial algorithm for modular composition (Brent & Kung 1978)
has a running time that is far from optimal. I'll describe a new algorithm
whose running time is optimal up to lower order terms, and which uses
completely different ideas (inspired by recent work in coding theory). This
in turn leads to the improved algorithm for polynomial factorization. I'll
also highlight a self-contained open problem whose resolution would lead to
nearly-linear time algorithms for polynomial factorization.

See other events that are part of Theory Colloquium Spring 2008

See other events happening in March 2008