问题标签 [ntt]

这是我第一次在这里提问，如果有问题，请见谅。
我正在尝试使用 cpp 线程并行化 NTT，但我只是迷路了。我将代码基于一篇解释 NTT 的 CUDA 并行化的文章并对其进行了调整，以便它对处理器更有意义（更少的线程），但我碰壁了，无法进步。基本上，创建了一个类来映射每个线程与数组中的哪对元素需要使蝴蝶打开，结果是错误的，并且 psis 似乎被正确计算（位反转顺序）。
我是并行计算和 NTT 的新手，不胜感激。

感谢您的关注。
EDIT1：
解释得更好一点，数论变换基本上是傅里叶变换，在以模为界的字段中具有整数，它从 x-power=index 更改多项式的表示（例如：6x^2 + 5x +9） ([9,5,6]) 到 {x,y}={index, variable}([9,20,26]) 以便我们可以更快地乘以多项式。为此，我们需要原始根（代码中的 psis）及其幂，它们基于多项式的大小及其模数。
Ntt里面是一个蝶形操作，论文把这个操作里面的数组元素分给了gpu的各个线程，所以为了cpus的修改，我创建了一个类来符号化各个线程，给各个线程传递SIZEOFPOLYNOMIAL/TH​​READNUMBER元素. 当线程被调用时，它会为其给定的元素数组计算蝶形。
我正在使用gcc -O3 -std=c++17 -pthread -march=native -lm并且我正在使用各种实现测试 NTT，唯一不起作用的是这个，所以主要功能（是巨大的）在这种情况下并不重要，只会使这篇文章膨胀。
论文：https ://eprint.iacr.org/2021/124.pdf