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 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

Join us: https://www.ingonyama.com/#careers-section

--

--

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].

Carol Danvers

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

Join us: https://www.ingonyama.com/careers

--

--

Ingonyama

Ingonyama means Lion. We are a next-generation semiconductor company, designing accelerators for Zero Knowledge cryptography.