Faster polynomial multiplication via multipoint Kronecker substitution

J. Symb. Comp. 44 (2009), 1502–1510 (DOI).

arXiv preprint (December 2007) (published version is substantially revised and improved).

Abstract

We present several new algorithms for dense polynomial multiplication in Z[x] based on the Kronecker substitution method. Instead of reducing to a single integer multiplication, we reduce to several smaller multiplications. We describe an implementation of multiplication in (Z/nZ)[x] for a word-sized modulus n based on these methods, and compare its performance to that of NTL and Magma.

Implementation

See the file mul_ks.c in zn_poly.


Back to the main page