在整数环中使用FFT进行相乘

我需要使用整数环中的FFT将长整数与任意数字的BASE相乘。对于某些k，操作数总是长度为n = 2^k，并且卷积矢量具有2n组件，因此我需要一个2n'th统一的原始根。在整数环中使用FFT进行相乘

我并不特别关心效率问题，所以我不想使用Strassen &Schönhage的算法 - 只是计算基本卷积，然后是一些运算，这没什么别的。

虽然看上去简单，许多数学家，我代数的了解实在是太差了，所以我有很多的问题：

什么是整数环执行FFT有着本质的区别或细微差别模2^n + 1 （也许是复合），并以整数FIELDS为模p？

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

但也许有其他细微差别，这将阻止我使用这种形式的环用于FFT。
如果我选择了整数环，那么在此字段中存在2^n单位根的充分条件是什么？

所有其他2^k较小秩序的统一个根可以用平方这根获得，对吧？..
由环模的乘法强加什么必要限制吗？也许在它们的长度上，也许在数字基础上，甚至可能在用于乘法的数字类型上。

我怀疑如果通过模运算减少卷积的系数，可能会有一些信息丢失。这是真的，为什么？..什么是一般条件，可以让我避免这种情况？
是否有只是原始类型的动态列表的任何可能性（即long）将足以满足FFT矢量，它们的产物和卷积矢量？或者我应该将这些系数转换为BigInteger以防万一（当我真的应该做什么时“情况”）？

如果这些问题的一般答案花费太长时间，我会特别满意的答案在下列条件下。我在外地Z_70383776563201发现，为了统一的原根的表达2^30：

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

所以，如果我使用统一的2^30次方根繁殖长度2^29的号码，什么是精密/算法/效率细微差别我应该考虑什么？..

非常感谢你提前！我要奖赏最好的答案 - 请考虑帮助一些例子。

来源

2012-04-20 wh1t3cat1k

尝试这里更多的理论数值分析的问题：http://scicomp.stackexchange.com/ – tskuzzy 2012-04-20 09:58:59

这是一个非常先进的问题 - 我可能是几个人谁拥有实际动手经验，在这方面的一个能够回答它。但是它太大而无法在SO上得到回答。这将需要页面和页面的文字+图... – Mysticial 2012-04-20 10:14:24

我明白了......但是没有证据的基本事实会占用这么多页面吗？也许，为了证明，我可以在你的帮助下找到方向。另外，在特别关注我的问题结束时，我还特别加以限制。我还欠他一些啤酒，他甚至可以以非常深的方式回答这个问题。 – wh1t3cat1k 2012-04-20 10:34:08

首先，你的身份的算术线索：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-08 20:36:17 eh9

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

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

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

的问题，对于每个x [我]，这将是太大，我们不能做宽*在O（1）时间A_I。

来源

2016-01-22 18:05:04 Kevin

在整数环中使用FFT进行相乘

回答

相关问题