math - 在整数环中使用 FFT 进行乘法

Question

我需要在整数环中使用 FFT 将长整数与任意数字基数相乘。对于某些 k 来说，操作数的长度始终为 n = 2^k，并且卷积向量具有 2n 分量，因此我需要一个 第二个统一原根。

我并不是特别关心效率问题，所以我不想使用 Strassen & Schönhage 的算法 - 只是计算基本卷积，然后进行一些进位，仅此而已。

尽管对许多数学家来说似乎很简单，但我对代数的理解非常糟糕，所以我有很多问题:

1. 在整数环模 2^n + 1(可能是复合)中执行 FFT 与在整数 FIELDS 模某个素数 p 中执行 FFT 之间有哪些本质区别或细微差别>？
   
   我问这个是因为 2 是这样一个环中的 (2n)th 单位原根，因为 2^n == -1 (mod 2^n +1)。相反，整数字段需要我搜索这样的原根。
   
   但也许还有其他细微差别会阻止我使用这种形式的环进行 FFT。

2. 如果我选择整数环，那么该域中存在 2^n 单位根的充分条件是什么？
   
   所有其他较小阶的2^k次单位根都可以通过对该根进行平方来获得，对吧？..

3. 环模乘法有哪些基本限制？也许取决于它们的长度，也许取决于数字基数，甚至可能取决于用于乘法的数字类型。
   
   我怀疑如果通过模运算减少卷积系数，可能会丢失一些信息。这是真的吗？为什么？...可以让我避免这种情况的一般条件是什么？
   
   

4. 是否有可能仅原始类型的动态列表(即 long)就足以满足 FFT 向量、它们的乘积和卷积向量？或者我应该将系数转换为 BigInteger 以防万一(当我真正应该这样做时，“情况”是什么)？

如果对这些问题的一般性回答花费的时间太长，那么我会对以下条件下的答案感到特别满意。我在 Z_70383776563201 字段中找到了一个最高 2^30 的阶单位原根表:

http://people.cis.ksu.edu/~rhowell/calculator/roots.html

因此，如果我使用 2^30 单位根来乘以长度 2^29 的数字，我应该考虑哪些精度/算法/效率细微差别？ ..

提前非常感谢! 我将奖励最佳答案 - 请考虑帮助提供一些示例。

Answer 1

首先，关于您身份的算术线索:70383776563201 = 1 + 65550 * 2^30。那个长数字就是素数。在页面 How the FFT constants were found 上有很多关于模数的见解。 .

这是您应该了解的群论事实。以 N 为模的整数乘法群是循环群的乘积，循环群的阶数由 N 的素数因子决定。当 N 为素数时，有一个循环。然而，这种循环群中元素的阶数与N - 1的质因数有关。 70383776563201 - 1 = 2^31 * 3^1 * 5^2 * 11 * 13，指数给出元素可能的顺序。

(1) 你不一定需要原根，你需要一个至少阶数足够大的根。有一些概率算法用于查找“高”阶元素。它们用于密码学，以确保您拥有强大的 key Material 参数。特别是对于 2^n+1 形式的数字，它们受到了很多因式分解的关注，您可以去查找结果。

(2) 2^n 阶元素的充分(且必要)条件由示例模数说明。条件是模数的某个素因数 p 必须具有以下属性:2^n | p - 1。

(3) 仅当元素不可乘法可逆时才会发生信息丢失，而素数模数的循环乘法群则不是这种情况。如果您在具有复合模量的模环中工作，则某些元素不是那么可逆。

(4) 如果您想使用 long 数组，您实际上需要重写您的大整数库。