问题标签 [ntt]

下午好！

我正在尝试基于我已经拥有的朴素递归 FFT 实现来开发 NTT 算法。

考虑以下代码（coefficients' 长度，顺其自然m，是 2 的精确幂）：

它适用于复杂的 FFT（替换BigInteger为复杂的数字类型（我有自己的））。即使我适当地更改了找到统一的原始根源的程序，它也不起作用。

假设，问题是这样的：rootsOfUnity传递的参数最初只包含第m-th 个复单位根的前半部分，顺序如下：

omega^0 = 1, omega^1, omega^2, ..., omega^(n/2)

就足够了，因为在这三行代码中：

我最初利用了这样一个事实，即在任何递归级别（对于任何nand i），unity 的复杂根-omega^(i) = omega^(i + n/2)。

但是，该属性显然不适用于有限域。但是是否有任何类似物可以让我仍然只计算根的前半部分？

或者我应该将循环从n/2to扩展n并预先计算所有m-th 统一的根？

也许这段代码还有其他问题？...

非常感谢您！

我想使用 NTT 进行快速平方计算（请参阅 Fast bignum square calculation），但即使对于非常大的数字，结果也很慢......超过 12000 位。

所以我的问题是：

1. 有没有办法优化我的 NTT 转换？我并不是要通过并行（线程）来加速它；这只是低级层。
2. 有没有办法加快我的模运算？

这是我在 C++ 中为 NTT 编写的（已经优化的）源代码（它是完整的，并且 100% 在 C++ 中工作，不需要第三方库，也应该是线程安全的。当心源数组被用作临时的！！！ , 它也不能将数组转换为自身）。

我的 NTT 类的使用示例：

优化前的一些测量（非 NTT 类）：

我优化后的一些测量（当前代码、更低的递归参数大小/计数和更好的模块化算法）：

检查 NTT mul 和 NTT sqr 时间（我的优化将其加快了 3 倍多一点）。它只有 1 倍循环，所以它不是很精确（误差 ~ 10%），但即使现在加速也很明显（通常我循环它 1000 倍甚至更多，但我的 NTT 太慢了）。

您可以自由使用我的代码...只需将我的昵称和/或指向此页面的链接保留在某处（代码中的 rem、readme.txt、about 或其他）。我希望它有所帮助......（我在任何地方都没有看到快速 NTT 的 C++ 源代码，所以我不得不自己编写）。对所有接受的 N 进行了统一根测试，请参见fourier_NTT::init(DWORD n)函数。

PS：有关 NTT 的更多信息，请参阅Translation from Complex-FFT to Finite-Field-FFT。此代码基于我在该链接中的帖子。

[edit1:] 代码中的进一步更改

通过利用模素数始终为 0xC0000001 并消除不必要的调用，我设法进一步优化了我的模运算。现在产生的加速效果令人惊叹（超过 40 倍），并且在大约 1500 * 32 位阈值之后，NTT 乘法比 karatsuba 更快。顺便说一句，我的 NTT 的速度现在与我在 64 位双精度上优化的 DFFT 相同。

一些测量：

模运算的新源代码：

如您所见，函数shl并shr不再使用。我认为 modpow 可以进一步优化，但它不是一个关键函数，因为它只被调用很少。最关键的功能是 modmul，它似乎处于最佳状态。

进一步的问题：

• 有没有其他加速 NTT 的选项？
• 我对模运算的优化是否安全？（结果似乎是一样的，但我可能会错过一些东西。）

[edit2] 新的优化

我从您的所有评论中实现了所有可用的东西（感谢您的洞察力）。

加速：

• +2.5% 移除不必要的安全模组（Mandalf The Beige）
• +34.9% 使用预先计算的 W,iW 力量（神秘）
• +35% 总计

实际完整源代码：

NTT_fast通过分离为两个函数，仍然有可能使用更少的堆垃圾。一个 withWW[]和另一个 with iWW[]which 导致递归调用中的一个参数减少。但我对它的期望并不高（仅限 32 位指针），而是有一个功能可以在将来更好地管理代码。许多功能现在处于休眠状态（用于测试），例如慢速变体mod和较旧的快速功能（使用w参数而不是*w2,i2）。

为避免大数据集溢出，请将输入数字限制为p/4位。每个NTT元素p的位数在哪里，因此对于这个 32 位版本，使用最大输入值。(32 bit/4 -> 8 bit)

[edit3]bigint用于测试的简单字符串乘法

我使用AnsiString's，所以我char*希望将它移植到，我没有做错什么。看起来它工作正常（与AnsiString版本相比）。

• sx,sy是十进制整数
• 返回分配的字符串(char*)=sx*sy

每个 32 位数据字只有约 4 位，因此没有溢出风险，但它当然更慢。在我的bignum库中，我使用二进制表示并为NTT8 bit使用每个 32 位 WORD 的块。如果大的话，更多的是有风险的......N

玩得开心

我正在尝试在 Objective C 中实现 NTT（数论变换），但是在线发布的抽象数学文档缺少关键细节。我发现了以下关于 Stack Overflow 的现有问题，该问题声称包括 NTT 的工作（尽管不是最佳）实现： 模块化算法和 NTT（有限域 DFT）优化

我的问题是关于“W”的计算。“p”显然是一个选择的素数。然而，这个实现计算“W=(2^L) mod p”。“L”是一个预定义的常数，等于“0x30000000”，这绝对不是以 2 为底的幂。这与我发现的几个不同的数学摘要直接矛盾，这似乎表明“L”不仅应该是源数组中的元素（因此是基数 2 的幂），但也可以启动！显然我在这里遗漏了一些重要的东西。有人可以解决这个矛盾吗？此处“L”的值是如何选择的？更重要的是，给定一个不同的素数，如何确定“L”的对应值？

一般来说，在实施 FFT 时，我有点新手，但我认为我已经掌握了大部分基本想法。在这种特定情况下，我在 257 有限域上实现了数论变换。它基本上是典型的 Radix-2 Cooley-Tukey FFT。我想知道的是：有没有更好的替代 Cooley-Tukey Radix-2 更适合有效地执行此特定 NTT（如果答案是不合格的“是”或“是”的条件不完全在范围内这个问题，我有兴趣听到任何一个），或者是否有特定于 Mersenne NTT 的东西可以比更一般的情况更有效地实现？

以下代码中的多个 where 条件导致仅显示第一行，

我想显示与此条件匹配的所有行，

即使对于单个条件，第一行也只能显示，我如何显示所有行。

我在实施 NTT 时遇到了困难。在阅读了来自http://www.apfloat.org/ntt.html、http://codeforces.com/blog/entry/43499和其他一些关于 FFT 和 NTT 的大量教程后，我利用 Fermats 理论实现了NTT在选择模素数时。但我仍然认为我错过了一些东西，因为 invNTT(NNT(a)) 没有以'a'的形式出现。

请看看我的实现。

我一直在研究使用 NTT (FFT) 将多项式相乘的代码，我做了 2 种不同的实现，并使用现有的实现来验证，例如：https ://www.nayuki.io/page/number-theoretic-transform -integer-dft，https://github.com/iblue/ntt。

问题是所有结果似乎都向左移动一次（乘以 x），如下所示：

此外，平凡的案例 1*1 也是错误的：

我不知道为什么会发生这种情况，到目前为止我读过的任何文章都没有提到它。

我错过了什么？

我想使用 NTT 实现多项式的乘法。我遵循数论变换（整数 DFT），它似乎有效。

现在我想在任意素数的有限域Z_p[x]上实现多项式的乘法。p

p与以前的无界情况相比，它是否改变了系数现在以 为界的任何内容？

特别是，原始 NTT 需要找到N大于的工作模数作为工作模数，(magnitude of largest element of input vector)^2 * (length of input vector) + 1以便结果永远不会溢出。如果结果无论如何都会受到那个p素数的限制，那么模数可以有多小？请注意，p - 1不必是 form (some positive integer) * (length of input vector)。

编辑：我从上面的链接中复制粘贴了源代码来说明问题：

印刷：

但是，在我更改minmod = maxval**2 * len(vec0) + 1为 的地方minmod = maxval + 1，它停止工作：

为了按预期工作，最小的minmod（在上面的链接中）是什么？N

我正在尝试学习template用 C++ 实现。当我将我的 NTT（数论变换）代码更改为使用的代码template时，如下所示：

它告诉我做 x static。

当我这样做时，它告诉我制作 x const，这击败了 x 首先存在的原因。

如果有帮助，我使用（GNU C++11）和我的编译器（Dev-C++ 5.11）设置为配置（TDM-GCC 4.9.2 64 位版本）。

我真的很想完成这项工作，但我不知道该怎么做。

这可能是愚蠢的容易，但正是我错过了什么？

先感谢您。

我正在寻找一种模式来递归地将数组拆分为奇数和偶数元素。我将尝试在以下内容中描述问题：

假设我们有一个长度为 16 的数组：

第一次迭代：拆分奇数和偶数

基本上是

再次将这些数组中的每一个拆分为奇数和偶数元素，我们有

同样是

再次拆分数组元素将是

或者

数组需要递归拆分，直到每个数组只有两个元素。

我注意到下半部分与上半部分相似的一件事，我们只需要在索引词中添加“1”

我想知道如何找到具有“n”个元素的数组的模式？

非常感谢您的宝贵时间。