Fast transforms over finite fields of characteristic two. (May 2021)

• Record Type: Journal Article
• Authors: Coxon, Nicholas
• Is Part Of: Journal of symbolic computation. Volume 104(2021)
• Page Start: 824
• Page End: 854
• Publication Date: 2021-05
• Subjects: Fast Fourier transform -- Newton basis -- Finite field -- Characteristic two; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2020.10.002
• Languages: English
• ISSNs: 0747-7171

Abstract

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.