论文部分内容阅读
本文证明用数论变换(NTT)能非常有效地计算离散傅里叶变换(DFT)值,而乘法次数可进一步减少。这是因为考虑数论变换和离散傅里叶变换的某些简单特性,把一个长度为P的离散傅里叶变换实乘总数减少到(P-1)。这样,每点所需实乘法次数还不到一次。适当选择变换长度和数论变换,每点
This paper proves that it is very effective to calculate the discrete Fourier transform (DFT) value by the number theory transform (NTT), and the number of multiplications can be further reduced. This is because by considering some simple features of number-theoretic transformations and discrete Fourier transformations, the total number of real-world discrete Fourier transformations of length P is reduced to (P-1). In this way, the number of real multiplications needed per point is less than once. Appropriate choice of transform length and number theory transform, each point