关于NTT变换参数的问题

ssikkiss

以前写过一个ntt变换的程序，能正常运行，但我发现我在做重复工作，而且没有别人写的好，就停下了。 最近几天无聊，把以前的代码翻出来看，想把某个地方改改，结果一改就出问题了 是这样的： 情况a：以前的程序，我是使用了32组M (模)，alpha(N次跟)，来分别对不同长度的数据做变换（实际上我只用到20多组，这里只是说明我的方式）。 情况b：现在，我想改成用同一个M (模)，不同的alpha(N次跟)，来分别对不同长度的数据做变换，结果错了。 我求N次跟的方法：因为我的M是素数，所以我先求其原根g，然后alpha=g^((M-1)/N); 在情况a和b里我都用的这个公式，在情况a下，N是最大变换长度，在b下，N除了最大变换长度还有它的1/2，1/4，1/8...............以适应不同的长度。 结果是不能正常工作了。。。。 想问下各位是怎么求N次跟的！（2<=N<=2^m,M=2^m * s+ 1） 顺便问下，对M=2013265921，求其在N=2，到N=2^27的alpha

gxqcn

已知 M=2013265921，求其 N=2^27 根alpha，过程如下： 1、计算 M 的 g=PrimitiveRoot[M]=31 2、计算 alpha =PowerMod[g, (M-1)/N, M] =440564289 证明：$\alpha^N -= (g^((M-1)/N))^N -= g^(M-1) -= 1\quad(mod M)$ 求其 -N 次根过程如下： 1、计算 M 的 g=PrimitiveRoot[M]=31 2、计算 alpha =PowerMod[g, (M-1)(N-1)/N, M] =1713844692 证明：$\alpha^-N -= (g^((M-1)-(M-1)/N))^-N -= (g^(-(M-1)/N))^-N -= g^(M-1) -= 1\quad(mod M)$ 请注意两个数值关于 M 互为数论倒数：440564289*1713844692 ≡ 1 (mod 2013265921)

ssikkiss

2# gxqcn 请问，上面的公式，可不可以把N改成2^26，以适应长为2^26的变换？ 或者改成2^25,2^24,.....

ssikkiss

找到原因了，还是老问题。溢出了。后来把3个模都控制在2^31以内，两数相加不会溢出了。终于能正常工作了。 并和gmp做了对比 1.仅比较乘法 1.1在计算589824位乘以589824位=1179648位的数，gmp比我约快27倍。 1.2计算9*2^24位乘以9*2^24位=9*2^25位，gmp比我快22倍。 2.gmp的输入较慢（因为是10进制），输出比我快2倍（gmp16进制，我的是10进制）。 3.总时间比较：一次10进制输入，一次乘法，一次输出（gmp16进制，我的是10进制）：gmp比我快3倍。如果gmp使用16进输入，将还是我的20多倍

ssikkiss

anjuta很讨厌！ 如果不是这个程序的工程开始是anjuta建立的，我早就删掉anjuta了。 代码提示的时候，经常突然吃掉我100%的cpu和1G-2G内存并卡死，很郁闷。 今天从工程里删除了一个文件，重新打开anjuta的时候居然又吃掉我2G内存并卡死。 哈哈。。 现在这个程序暂告一段落，可以把anjuta请走了！

无心人

现在好多比较好的C/C++ IDE 另外 GMP和你的算法区别在于GMP的算法多 中间步骤是选的比较合适的算法 你只有单一算法。 举个例子，500位二进制以内，还是通常的乘法速度快 也就是说，如果你可以用大的模数，保证模数是简单的，比如二进制表示只有2个1 且在500位二进制内，那么。最后速度不见得比你算法的小模数慢 由于这些算法的分析比较复杂，俺无法胜任，谁有能力帮大家分析下 在大模数下（大于2^32，小于2^10000）的情况

ssikkiss

对大模数这方面我还没研究过，我目前只实现了最基本的算法。不过我可以猜想：一定要找到了一个很好的短整数算法，才能开始做楼上提及的想法。另外因为ntt的理论复杂度是O（n*logn），所以我认为在n越大时，我们得到的收益越大，如果使用大的模，势必会降低n 我对我的程序进行了更细的测量，发现在n较小时，CRT步骤里最后不得不用的__int128的短除法，时间居然占了所有时间的一半，当n较大时，才慢慢降到3/8。这可能是我的程序最大的瓶颈了。 我还曾用fftw做了个乘法来测试，不过是临时起意，对fftw的很多选项不熟。 在长度为2^n时，gmp比用fftw实现的乘法快5倍，其中fftw应该还能提高一些。