NTT 学习笔记
在基于格构建的后量子密码体制中，要多次使用环上多项式乘法。但多项式乘法的时间复杂度为O()，这将降低密码算法的运行效率。 而通过NTT变换，可以将环上多项式乘法的时间复杂度降为O(nlogn)，有效提升整体算法运行效率。在第一部分，将介绍多项式的两种表示 方法及对应的乘法;在第二部分，将介绍NTT方法的基本思想与方法;在第三部分，将介绍在与两个常用多项式环上的乘法。 在第四部分，将给出具体的实例来说明以上方法。
1. 多项式的两种表示方法及对应的乘法
1.1 多项式的一般表示及对应乘法
一般情况下，将n次多项式定义如下：
其中第n项系数。
对于两个多项式，： 其乘法为：
即两多项式相乘后的系数为与下标和为对应项的系数乘积的和。 由于其中含有两个求和符号，所以使用该表达式进行多项式乘法时间复杂度为O()。
1.2 多项式的点值表示法及有关乘法
根据插值理论，如果有个点，则可以唯一恢复出一个次多项式，即可以用个点来表示一个多项式。 例如，可以使用点,来表示一次多项式。
对于一般情况，若次多项式,已知个点:
将其写为线性方程组的形式，即
可将其进一步转化为矩阵表示：
因此，在已知后可通过求解线性方程组来快速确定多项式系数。其中的矩阵为范德蒙矩阵，设为。
例如，对于,若求得如下个值：
将对应纵坐标的点相乘得：
在得到这个点后，通过求解线性方程组即可恢复的系数并得到两多项式相乘的结果:。
在上述求解过程中，如果利用高斯消元法来求解对应的系数，时间复杂度为，比直接相乘的时间复杂度更高。 但是上述过程并没有对多项式及相关参数进行限制，而在格密码中如果能很好地控制多项式环的参数，就能有效地降低多项式乘法的时间复杂度。
2. NTT方法的基本思想
NTT的基本思想与多项式的点值表示的多项式乘法类似，即通过将多项式转化为不同的点值，再根据这些不同的点值的相乘来得到所需多项式的不同的点值， 最后根据这些点值来逆向求解多项式乘法。在该过程中，将多项式转化为点值的过程称为NTT(正向NTT)，将点值恢复为多项式的过程称为INTT(逆NTT)。
在NTT中，可以通过参数的选取使选点采样的过程变为递归问题，使时间复杂度降为O(nlogn)。
2.1 NTT参数选取限制
在实际应用中，多项式次数多为偶数，因此以下均假设多项式次数为偶数。
假设多项式，对所有奇数项提取得：
其中表示中的偶数项,表示中的奇数项。 若对取反为得：
公式为CT蝴蝶变换的基础，将在之后详细介绍。
取得：
该过程就是将原来求解次多项式的问题转化为求解次多项式，并可以一直向下分解直至转化为求解一次多项式,此过程即可用递归完成求解，并使时间复杂度 降为O(n logn)。
但在该递归过程中，需要，即。 因此，在该过程中，首先需要找到一个使得，再依次采样。 最后公式(1)中的范德蒙矩阵可写为:
此时，若有任意一对或多对相等则会导致该矩阵行列式为0，无逆矩阵可进行INTT变换。 因此要求两两不等。
因此，在使用NTT时需存在参数，并有两点参数限制:
1.(保证递归可以进行)
2.两两不等(保证INTT可以进行)
2.2 NTT与INTT的定义
定义NTT:
设为次多项式,系数，,其中:
该定义是对上述文本的总结，即NTT变换是在已知多项式系数的情况下将多项式变换为点值。 而INTT变换则是在已知多项式的点值的情况下求出多项式的系数。
根据公式(2)可知，根据多项式的点值求出多项式系数，将该式同时左乘即可得到多项式系数。通过对范德蒙矩阵求逆可得:
基于此，即可定义INTT。
定义INTT:
,其中：
要能够使用NTT与INTT变换来实现多项式乘法，依赖于两个重要的性质:
1.
2.
其中表示向量对应位置元素相乘，因此可通过计算多项式相乘后的结果。
3. 在两种常用多项式环上的NTT
在格密码方案中，所基于的多项式环多为与。 其中，基于的多项式乘法称之为循环卷积(Cyclic convolution, CC)或正闭包卷积PWC(Postive wrapped convolution),基于此的NTT称为CC-based NTT； 基于的多项式乘法称之为负闭包卷积(Negative wrapped convolution),基于此的NTT称为NWC-based NTT。
根据基于的环的不同，NTT变换将会有不同的定义，但其核心思想均第二部分相同。在该部分，将依次介绍 基于与环上的乘法定义，NTT与INTT的定义，CT蝴蝶变换与GS蝴蝶变换。
3.1 基于环上的NTT
在该环上的NTT参数需要满足为2的次幂，且,其中为素数。
在基于的环中，，即。因此在此多项式环上，多项式的次数不会高于n，即多项式次数最高为。
取在该环上的两个多项式:
由于,所以,即在该环上的多项式乘法为：
可以看到，式(1)与式(5)并无本质区别，因此基于环上的NTT与未加限制的NTT与INTT定义并无不同，即:
,其中
,其中
3.2 基于环上的NTT
在该环上的NTT参数需要满足为2的次幂，且,其中为素数。
在基于的环中，其多项式次数最高为,但在该环中，即，所以。 因此该环上的多项式乘法为:
在这个环上的多项式乘法与环上的多项式乘法相比，差异在于内层括号的符号不同。
根据条件，以及3.1节中的相关内容，在环中必然存在。
在中，;而在中，但是对于则有。 因此，若将的元素映射到上，则需要多乘一个， 使得变为。通过上述映射，则公式(6)则可以写为：
因此，在中的NTT与INTT定义为:
,其中
,其中
由上述结论知, 因此NTT与INTT定义可进一步化简为:
,其中
,其中
此处给出另一种理解中的NTT的角度。 对于多项式可以被分解为，那么在环中的NTT应该是环的一部分， 因此环中的参数要求都与相关。
3.3 CT蝴蝶变换与GS蝴蝶变换
CT蝴蝶变换是将NTT变换不断按照奇偶划分，将递归过程具象化，并达到加速的目的；而GS蝴蝶变换是CT蝴蝶变换的逆变换，并且加速INTT变换。 待参数确定后，CT蝴蝶变换与GS蝴蝶变换的各个过程也随之确定，即可将递归过程具象为带有或不同幂次的表达式， 通过预计算确定或不同幂次就可直接代入多项式系数进行计算，有效提升运算效率。
在不同环上的CT蝴蝶变换与GS蝴蝶变换并没有太大区别，因此以下介绍均基于环。
在中，存在。 基于此，若对NTT变换按照奇偶划分得:
将代换为,则，因此：
设,有：
因此，通过重复利用的值计算得到,并且的值也可以通过下一层的计算得到。 该过程可表示为下图:
GS蝴蝶变换是CT蝴蝶变换的逆变换,其过程可参照下图：
将CT蝴蝶变换的输出作为GS蝴蝶变换的输入即可恢复原来的多项式。在下一部分，将给出具体的实例来描述NTT，INTT变换与两种蝴蝶变换。
4. 实例
在该部分，将基于环，选取来说明NTT、INTT变换与两种蝴蝶变换。
选取,根据定义可知相乘后结果为：
在此之前，首先给出比特翻转的定义，以便后续说明:
定义比特翻转:
若为2的次幂，为非负数且b < n, 则 b 比特翻转后为:
例如，若，则,比特翻转后为。
对各系数使用数组存储，即,设经过CT蝴蝶变换的结果为具体过程可参照下图:
根据图3,并使用进行代换知:
可以看到，此结果与NTT定义所得到的结果相同。但是由于CT蝴蝶变换的输出会导致下标比特翻转， 因此CT蝴蝶变换的输出为，而。
在该过程中，需要进行层，且每一层需要计算次。因此，该算法的时间复杂度为。
此处给出对进行CT蝴蝶变换时的各中间值:
将CT蝴蝶变换的输出作为GS蝴蝶变换的输入，具体可参见下图：
根据图4，并使用进行代换知:
可以看到，此结果与INTT定义所得到的结果相同，且按照比特翻转后的顺序输入后得到的顺序为正常顺序。 此过程时间复杂度仍为。
对得到的结果乘以即可得到：
此处给出对进行GS蝴蝶变换的各中间值:
以下给出使用NTT计算的过程:
1.计算,
;
2.计算;
3.计算。
以上显示的均为正常顺序，但在实际操作中可以直接让经过NTT变换后的两多项式相乘，并按比特翻转的顺序输入INTT，最终仍将 按正常顺序输出两多项式相乘后的结果。而NTT变换与INTT变换的时间复杂度均为,因此通过此方法即可将多项式在乘法的 时间复杂度由降低为。
5. 结语
本文对NTT变换的思想与过程进行了说明，希望能够通过此对NTT有一个初步认识，因此很多结论的证明并未给出，主要参考的资料有[1][2][3]。 在理论上，有"上裁法"与"下裁法"来使NTT的参数限制变得更为宽松，也可综合两种方法达到该效果，即"混合NTT"[4]; 并且可以综合使用Karatsuba等技巧[5]，使NTT的速度变得更快。
在实现上，则有对基于AVX2，ARM Cortex-M4，GPU等的NTT多平台实现的研究，力求使NTT能够在各种软硬件上更快实现。 也有基于NTT的特性，分析其在硬件实现上的能耗等特性从而对基于格的密码体制进行侧信道分析的研究[6]。 可以根据这些方向，来进一步学习NTT。
参考文献
[1] 微信公众号：Coder 小 Q. 格密码学习笔记 (十八) 乘法运算加速: 快速数论变换,2024.
[2] Ardianto Satriawan, Infall Syafalni, Rella Mareta, Isa Anshori, Wervyan Shalannanda, and Aleams Barra. Conceptual review on number theoretic transformand comprehensive review on its implementations. IEEE Access, 11:70288–70316,2023.
[3] Zhichuang Liang and Yunlei Zhao. Number theoretic transform and its applications in lattice-based cryptosystems: A survey. arXiv preprint arXiv:2211.13546,2022.
[4] Shuai Zhou, Haiyang Xue, Daode Zhang, Kunpeng Wang, Xianhui Lu, Bao Li, and Jingnan He. Preprocess-then-ntt technique and its applications to k yber and new h ope. In Information Security and Cryptology: 14th International Conference, Inscrypt 2018, Fuzhou, China, December 14-17, 2018, Revised Selected Papers 14, pages 117–137. Springer, 2019.
[5] Yiming Zhu, Zhen Liu, and Yanbin Pan. When ntt meets karatsuba: preprocessthen-ntt technique revisited. In International conference on information and communications security, pages 249–264. Springer, 2021.
[6] Tianrun Yu, Chi Cheng, Zilong Yang, Yingchen Wang, Yanbin Pan, and Jian Weng. Hints from hertz: Dynamic frequency scaling side-channel analysis of number theoretic transform in lattice-based kems. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2024(3):200–223, 2024.