Discrete Fourier Transforms

Algorithms and methods

• FFT - Vitalik
• Bailey’s method
• FFTs for fun and profit - GentleMan Sande
• Reed-Solomon code: Vitalik
• FFT Notes
• The Fast Fourier Transform in a Finite Field - Pollard
• Number Theoretic Transform (NTT): Introduction
• Gentle intro to NTT 1 (includes rings)
• Gentle intro to NTT2 (includes rings)
• Efficient primes for NTT - Goldilocks
  • Goldilocks in nuFHE
  • Goldilocks NTT trick - Solberg
• Elliptic Curve Fast Fourier Transform (ECFFT) Part I: Fast Polynomial Algorithms over all Finite Fields: Eli Ben-Sasson et.al
  • Talk -zk study club
  • ECFFT algorithm
  • Rust Implementation -Wboregaud
  • Rust ECFFT BN254- Wboregeaud
• ECFFT-2 Ben-Sasson et.al
• FFT - Ferror Moreno thesis
• Zcash FFT
• FFT for polynomial multiplication
• A quick barycentric evaluation tutorial - Vitalik
• Barycentric interpolation - Math Oxford
• Walsh Hadamard Transform - Borgeaud
• FFT on finite fields intro
• Algebraic FFTs - Sage

Large FFTs

• Large-Scale Discrete Fourier Transform on TPUs
• Hybrid CPU/GPU FFTs - Chen
  • Thesis
• Large Scale 3d FFT on GPU

Implementations

• Thesis: BUNTTERFLY: A Flexible Hardware Generator for the Number Theoretic Transform - Jason Vranek
• CycloneNTT
• NTL: a library for NTT
• Zprize 2022