by Tomer Solberg
Polynomial arithmetic is at the heart of modern Zero Knowledge Proving (ZKP) systems. The Number Theoretic Transform (NTT) is a crucial tool in facilitating efficient computational complexity over large polynomials encountered in ZKPs. NTTs are dominated by the number of field multiplications.
In this short note we…
by Carol Danvers
“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-Tuckey 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].
Read the full paper here:https://github.com/ingonyama-zk/papers/blob/main/Winograd_fft.pdf
Follow our Journey
Twitter:https://twitter.com/Ingo_zk
Github:https://github.com/ingonyama-zk
YouTube:https://www.youtube.com/@ingo_zk
LINK BELOW:
https://github.com/ingonyama-zk/papers/blob/main/Marlin_and_me.pdf
Follow our Journey
Twitter:https://twitter.com/Ingo_zk
Github:https://github.com/ingonyama-zk
YouTube:https://www.youtube.com/@ingo_zk