This repository explores the implementation and acceleration of polynomial multiplications using the number-theoretic transform (NTT) and its inverse (iNTT)
It implements polynomial multiplication using the usual polynomial evaluation and Lagrange interpolation and later using NTT and iNTT butterfly based algorithms (Cooley-Tukey and Gentleman-Sande). This transformations are available also on a parallelized fashion using OpenMP.
Compiling this code produces an executable that can be used to measure the performance of the different implementations.
Warning
The correctness of the code is not guaranteed. This is an experimental project.
- Óscar Vera López