Discrete Fourier Transforms

Algorithms and methods

• FFT - Vitalik
• Reed-Solomon code: Vitalik
• FFT Notes
• The Fast Fourier Transform in a Finite Field - Pollard
• Number Theoretic Transform (NTT): Introduction
• NTT with code
• 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

Implementations

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