NTT Mini: Exploring Winograd’s Heuristic for Faster NTT
Ingonyama - Zero Knowledge Proof Hardware Acceleration
![Ingonyama - Zero Knowledge Proof Hardware Acceleration]()
Ingonyama - Zero Knowledge Proof Hardware Acceleration
A next-generation semiconductor company, we focus on finding and solving computational bottlenecks in ZKP.
Originally published on Ingonyama Blog
“Pushing the Limits on NTT Computation”
Abstract:
We report on the Winograd-based implementation for the Number Theoretical Transform. It uses less multiplications than the better known Cooley-Tukey alternative. This optimization is important for very high order finite-fields. Unfortunately, the Winograd scheme is difficult to generalize for arbitrary sizes and is only known for small-size transforms. We open-source our hardware implementation for size 32 based on [1].