Title: Fast transforms over finite fields of characteristic two,
Abstract: An additive fast Fourier transform over a finite field of characteristic two
efficiently evaluates polynomials at every element of an $\mathbb{F}_2$-linear
subspace of the field. We view these transforms as performing a change of basis
from the monomial basis to the associated Lagrange basis, and consider the
problem of performing the various conversions between these two bases, the
associated Newton basis, and the '' novel '' basis of Lin, Chung and Han (FOCS
2014). Existing algorithms are divided between two families, those designed for
arbitrary subspaces and more efficient algorithms designed for specially
constructed subspaces of fields with degree equal to a power of two. We
generalise techniques from both families to provide new conversion algorithms
that may be applied to arbitrary subspaces, but which benefit equally from the
specially constructed subspaces. We then construct subspaces of fields with
smooth degree for which our algorithms provide better performance than existing
algorithms.