关于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应该还能提高一些。