“Pushing the Limits on NTT Computation”


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

Written by

Carol Danvers

Table of Contents

Want to discuss further?

Ingonyama is commited to developing hardware for a private future using Zero Knowledge Proofs.

Get in touch
Get our RSS feed