Faster polynomial multiplication via multipoint Kronecker substitution

We present several new algorithms for dense polynomial multiplication in 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 for a word-sized modulus n based on these methods, and compare its performance to that of NTL and Magma.