Caltech
Fast Polynomial Factorization and Modular Composition in Small Characteristic
Tuesday, March 18, 4:15pm
32-155
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.
Host: Madhu Sudan