设x, y为长度为n的向量，其元素为1或0。我想有效地计算圆卷积
(x * y) mod 2
其中结果的每个分量取mod 2。
我知道如何使用快速傅里叶变换(乘以x和y的傅里叶变换，变换回来。但是，这使用浮点计算来解决离散问题，对于较大的n(我对n ~ 10^7感兴趣)，它可能会导致舍入错误。我希望有一个更好的方法来做到这一点，使用数论变换(NTT)，但不幸的是，我不熟悉数论或NTT。
我看了这个网站。按照这里的程序，
- 假设n = 10^7。我需要
- a模M(使用10^7)。
- 一个素数N=kn+1对于某些k(使用N= 3 * 10^7 +1)
- a根ω≡g^k mod N，其中g为发生器(例如ω=2744)
- 做变换，等等
问题这看起来很有希望。但是，在此计算过程中，我需要32位整数来存储每个位。此外，这并没有利用我只需要结果模2的事实。有没有办法利用这一点来简化程序?由于我不懂数论，这对我来说不是很明显。
我不是在要求一个完整的解决方案，只是为了一个参数，如果我的"mod 2";显着简化了实现(无论是在实现必要算法的难度还是计算资源方面)。
另一个问题:如果不能简化使用"mod 2"，你认为它仍然值得使用NTT，而不是仅仅扔一个著名的FFT库来解决浮点问题吗?对于NTT，您的过程看起来是正确的。是的，原始向量中的每一位都需要32位整数。不幸的是，你不能利用最终结果是对2取模的事实，因为你需要一个10^7阶的根。您可能能够将该数字缩小两个因子(并为几个基本递归级别执行标准DFT)，但相对而言，它不会改变太多。
注意，对于FFT实现，我相信你可以使用整数算术，因为它是mod 2，但我不相信它会是有效的。有关详细信息，请参阅此math stackexchange答案。