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 focus on the specific case of NTT in the 64 bit Goldilocks field. Following the simple observation that 2⁴⁸ is a root of unity, we show that expressing the first few roots of unity in terms of powers of 2, allows modular multiplications to be replaced with simple bit-shift operations, resulting in a significant cost saving for NTT.
Read the Paper on our Github here: https://github.com/ingonyama-zk/papers/blob/main/goldilocks_ntt_trick.pdf
Follow our Journey
Twitter: https://twitter.com/Ingo_zk
Github: https://github.com/ingonyama-zk
YouTube: https://www.youtube.com/@ingo_zk
