离散傅里叶变换

算法和方法

• FFT - Vitalik
• Reed-Solomon 编码：Vitalik
• FFT 笔记
• 有限域中的快速傅里叶变换 - Pollard
• 数论变换（NTT）：介绍
• 简单地介绍 NTT 1（包括环）
• 简单地介绍 NTT 2（包括环）
• NTT 的高效素数 - Goldilocks
  • nuFHE 中的 Goldilocks
  • Goldilocks NTT技巧 - Solberg
• 椭圆曲线快速傅里叶变换（ECFFT）第一部分：所有有限域上的快速多项式算法：Eli Ben-Sasson等
  • Talk - zk study club
  • ECFFT 算法
  • Rust 实现 - Wboregaud
  • Rust ECFFT BN254 - Wboregeaud
• ECFFT-2 Ben-Sasson 等
• FFT - Ferror Moreno 论文
• Zcash FFT
• 用于多项式乘法的 FFT
• 快速重心评估教程 - Vitalik
• 重心插值 - Math Oxford
• Walsh Hadamard 变换 - Borgeaud
• 有限域上的 FFT 介绍

实现

• 论文：BUNTTERFLY：用于数论变换的灵活硬件生成器 - Jason Vranek
• CycloneNTT
• NTL：用于 NTT 的库
• Zprize 2022