一般来说，在实施 FFT 时，我有点新手，但我认为我已经掌握了大部分基本想法。在这种特定情况下，我在 257 有限域上实现了数论变换。它基本上是典型的 Radix-2 Cooley-Tukey FFT。我想知道的是：有没有更好的替代 Cooley-Tukey Radix-2 更适合有效地执行此特定 NTT（如果答案是不合格的“是”或“是”的条件不完全在范围内这个问题，我有兴趣听到任何一个），或者是否有特定于 Mersenne NTT 的东西可以比更一般的情况更有效地实现？
问问题
1113 次
1 回答
0
我想说，对于二元长度 FFT，没有什么比 Cooley-Tukey 更好的了。
这与梅森数没有直接关系，任何具有模数的数字字段都2^(m*2^n)+1符合条件。I=2^(m*2^(n-1))是复单位，I^2=2^(m*2^n)=-1 mod (2^(m*2^n)+1)，q=2^(2*m)是一个原始2^n的单位根。
有关第二点的灵感，请参见Schönhage 的第 1 节：数值乘法的渐近快速算法 ...，以及快速乘法的总体摘要
于 2015-03-30T08:47:22.077 回答