模算法与NTT(有限域DFT)优化

Question

模算法与NTT(有限域DFT)优化我想使用NTT进行快速平方(参见快速大平方计算)，但是即使对于非常大的数字，结果也是缓慢的。超过12000位。所以我的问题是：有办法优化我的NTT变换吗？我并不打算通过并行(线程)来加快它的速度；这只是低级层。有办法加速我的模块运算吗？这是我的(已经优化的)C+的NTT源代码(它是完整的，100%工作在C+白化任何需要第三方库，也应该是线程安全的。请注意，源数组被用作临时的！，它也不能将数组转换为自身)。//---------------------------------------------------------------------------class fourier_NTT                                    // Number theoretic transform    {public:    DWORD r,L,p,N;    DWORD W,iW,rN;    fourier_NTT(){ r=0; L=0; p=0; W=0; iW=0; rN=0; }    // main interface    void  NTT(DWORD *dst,DWORD *src,DWORD n=0);               // DWORD dst[n] = fast  NTT(DWORD src[n])    void INTT(DWORD *dst,DWORD *src,DWORD n=0);               // DWORD dst[n] = fast INTT(DWORD src[n])    // Helper functions    bool init(DWORD n);                                       // init r,L,p,W,iW,rN    void  NTT_fast(DWORD *dst,DWORD *src,DWORD n,DWORD w);    // DWORD dst[n] = fast  NTT(DWORD src[n])    // Only for testing    void  NTT_slow(DWORD *dst,DWORD *src,DWORD n,DWORD w);    // DWORD dst[n] = slow  NTT(DWORD src[n])    void INTT_slow(DWORD *dst,DWORD *src,DWORD n,DWORD w);    // DWORD dst[n] = slow INTT(DWORD src[n])    // DWORD arithmetics    DWORD shl(DWORD a);    DWORD shr(DWORD a);    // Modular arithmetics    DWORD mod(DWORD a);    DWORD modadd(DWORD a,DWORD b);    DWORD modsub(DWORD a,DWORD b);    DWORD modmul(DWORD a,DWORD b);    DWORD modpow(DWORD a,DWORD b);    };//---------------------------------------------------------------------------void fourier_NTT:: NTT(DWORD *dst,DWORD *src,DWORD n)    {    if (n>0) init(n);    NTT_fast(dst,src,N,W);//    NTT_slow(dst,src,N,W);    }优化后的一些度量(当前代码、较低的递归参数大小/计数以及更好的模块化算法)：检查NTTmul和NTTsqr时间(我的优化使它加快了3倍多)。它只有1倍的循环，所以它不是很精确(误差~10%)，但加速比即使现在也是明显的(通常我会循环它1000倍或更多，但我的NTT太慢了)。你可以自由使用我的代码.。只需保留我的Nick和/或链接到这个页面的某个地方(rem in code，README.txt，约或诸如此类)。希望能帮上忙.。(我在任何地方都没有看到用于快速NTT的C+源代码，所以我不得不自己编写它)。统一的根测试了所有接受的N，见fourier_NTT::init(DWORD n)功能。