Additive FFT Explained: Fast Fourier Transforms over Binary Fields
The article explores the application of Fast Fourier Transforms (FFT) over binary fields, focusing on additive structures instead of multiplicative ones to enable efficient polynomial evaluation and interpolation. It introduces the Additive FFT, based on David Cantor's work, which uses linearized polynomials and additive subgroups to overcome the lack of sufficient roots of unity in finite fields of characteristic 2. This approach supports cryptographic applications such as Reed-Solomon encoding and polynomial commitments in systems like BINIUS.
- ▪The Additive FFT operates on additive subgroups of finite fields, providing an alternative to the classical FFT in characteristic 2 fields.
- ▪Linearized polynomials, whose degrees are powers of the field characteristic, are central to the Additive FFT due to their linearity properties over finite fields.
- ▪Additive FFT enables efficient polynomial evaluation and interpolation, which are essential for Reed-Solomon encoding in cryptographic protocols.
- ▪The method circumvents the limitation of insufficient multiplicative roots of unity in binary fields by leveraging recursive structures in vector subspaces.
- ▪Cantor's 1989 framework for arithmetic over finite fields forms the theoretical foundation for the Additive FFT implementation discussed in the article.
Opening excerpt (first ~120 words) tap to expand
Additive FFT Explained: Fast Fourier Transforms Over Binary Fields LambdaClass 17 Jun 2025 • 14 min read Share Warning: This post is more math heavy than other articles. Introduction In this article we continue our study of towers of binary fields, motivated by the proposal of Diamond and Posen for a complete protocol working over fields of characteristic 2, BINIUS. Previously we covered basic arithmetic of field elements in a tower of binary fields, namely Wiedemann's iterative quadratic extension of $\mathbb{F_2}$. We address the problem of evaluating and interpolating polynomials with coefficients in such fields, with cryptographic applications in mind.
…
Excerpt limited to ~120 words for fair-use compliance. The full article is at LambdaClass Blog.
Discussion
0 commentsMore from LambdaClass Blog
