The Number Theoretic Transform (NTT) is an efficient algorithm for computing the products of polynomials whose coefficients belong to a finite field.
This repository contains SRI's various implementations of the NTT (developed while implementing the Bliss).
It also includes the verification of these algorithms.
The repository is organized into three subdirectories:
-
src contains a plethora of code implementing the algorithms described in paper.
-
verifier contains the code of the verifier that proves absence of integer overflows of the programs described in src.
-
paper contains the VSTTE20 conference version of the paper, as well as the slides from the conference talk.