Title: Faster Multiplication for Long Binary Polynomials,
Abstract: We set new speed records for multiplying long polynomials over finite fields
of characteristic two. Our multiplication algorithm is based on an additive FFT
(Fast Fourier Transform) by Lin, Chung, and Huang in 2014 comparing to
previously best results based on multiplicative FFTs. Both methods have similar
complexity for arithmetic operations on underlying finite field; however, our
implementation shows that the additive FFT has less overhead. For further
optimization, we employ a tower field construction because the multipliers in
the additive FFT naturally fall into small subfields, which leads to speed-ups
using table-lookup instructions in modern CPUs. Benchmarks show that our method
saves about $40 \%$ computing time when multiplying polynomials of $2^{28}$ and
$2^{29}$ bits comparing to previous multiplicative FFT implementations.