Fast transforms over finite fields of characteristic two. (May 2021) - Coxon, Nicholas
Abstract: We describe new fast algorithms for evaluation and interpolation on the "novel" polynomial basis over finite fields of characteristic two introduced by Lin et al. (2014) . Fast algorithms are also described for converting between their basis and the monomial basis, as well as for converting to and from the Newton basis associated with the evaluation points of the evaluation and interpolation algorithms. Combining algorithms yields a new truncated additive fast Fourier transform (FFT) and inverse truncated additive FFT which improve upon some previous algorithms when the field possesses an appropriate tower of subfields.