2

我需要在整数环中使用 FFT 将长整数与任意 BASE 数字相乘。n = 2^ksome的操作数总是有长度的k，并且卷积向量具有2n分量，因此我需要一个2n'th原始单位根。

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

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

  1. 2^n + 1在整数环模（可能是复合）和整数 FIELDS 模一些素数中执行 FFT 之间有什么本质区别或细微差别p？

    我问这个是因为在这样一个环中2是一个(2n)th原始的统一根，因为2^n == -1 (mod 2^n+1)。相反，整数字段需要我搜索这样的原始根。

    但也许还有其他细微差别会阻止我将这种形式的环用于 FFT。

  2. 2^n如果我选择整数环，那么在这个领域中存在 -th 单位根的 充分条件是什么？

    所有其他2^k小阶单位的根都可以通过平方这个根来获得，对吧？..

  3. 环模乘法有哪些基本限制？也许在它们的长度上，也许在数字基础上，甚至可能在用于乘法的数字类型上。

    我怀疑如果通过模运算减少卷积的系数，可能会丢失一些信息。这是真的吗？为什么？.. 有哪些一般条件可以让我避免这种情况？

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

如果对这些问题的一般回答需要太长时间，我会特别满意在以下条件下的回答。我2^30在字段 Z_70383776563201 中找到了顺序统一的原始根表：

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

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

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

4

2 回答 2

2

首先，关于你的身份的算术线索：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) 您不一定需要一个原始根，您需要一个其阶数至少足够大的根。有一些用于查找“高”阶元素的概率算法。它们用于密码学，以确保您拥有强大的密钥材料参数。特别是对于 2^n+1 形式的数字，它们受到了很多因式分解的关注，您可以查看结果。

(2) 模数示例说明了 2^n 阶元素的充分（和必要）条件。条件是模数的某个素因子p必须具有 的性质2^n | p - 1。

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

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

于 2012-11-08T20:36:17.977 回答
1

假设我们需要计算两个 n 位整数乘法，其中

n = 2^30;
m = 2*n; p = 2^{n} + 1

现在， w = 2, x =[w^0,w^1,...w^{m-1}] (mod p).

问题是，对于每个 x[i]，它都会太大，我们无法在 O(1) 时间内完成 w*a_i。

于 2016-01-22T18:05:04.120 回答