NTT相关问题一则，有兴趣的参与

无心人

费马数变换，就比较理想 如果不考虑字长的话 如果考虑字长，则看用途 用于大数运算的，可适当扩大大数的基以不浪费空间 如果是计算卷积 做多次不同模的NTT 再用CRT做减少字长的处理

ssikkiss

抱歉!更正我以上发的2个代码,刚刚又温习了下,书里说是叫三项式变换.以前我贴错了 不过我还是觉得这个三项式变换比较顺手,它能提供容易控制的变换长度!缺点是计算没费马变换快! 我来谈几点感受,希望大家多多指正: 关于NTT的2个限制:设变换长度=N,模=M,我们利用NTT来计算乘法,且大数的基=base 1,模M的大小: 我觉得M不能太小,不然就NTT就没法利用,又不能太大,计算机字长的关系. 一般我控制在M>N*base*base,设base=10^9,或base=2^32,一般N不会超过2^32, 则M不会超过2^96,三个DWORD就可以表示.即使考虑N可以小到几十,还是得要三个DWORD来表示,想用2各DWORD来表示不可能. 现在问题来了: A:在进行乘法的时候,使用3个每个DWORD大小的模来对2个相乘的大数作各3次NTT变换,变换后相乘,在作3次逆NTT变换,最后再用CRT来处理3个变换的结果得到乘积 B:干脆直接自己定义一个2^96大小的数据类型,直接对2个相乘的大数各1次NTT变换,相乘,在作1次逆NTT,得到结果 C:修改base为10,或16,这样,就不必面对太大的模,以10进制为例,和10^9进制比,空间多用了9倍,而且做加减的时候也要慢不止9倍,用NTT作乘法的时候要比前2个方案方便. 请问这3个方案谁更快! 2.变换长度N: 感觉费马变换提供的长度仍然不过灵活,而另一个三项式变换却能容易提供合适的长度 假设我们需要变换长度N=2^m,只要找到一个素数M,使M=s * N+1是素数即可.这样,不需要太大的模,就能具备较长的长度了.缺点是,这样的素数M容易找,但要使其N阶单位跟等于2(或4,或8..)就很少见了.这使得其计算会稍慢.

无心人

先回答容易的2，使用伪费马数变换似乎容易找到 问题1、如果某个一次变换的根简单，我觉得还是一次变换好，只要根是2方幂，则中间步骤就简单 如果找不到，用CRT三次变换并不慢 问题1的C并不是专业人员考虑的，不要问这个问题

ssikkiss

用CRT三次变换,关键是最后CRT那步,还是得使用2^96的数据类型. 我对CRT的理解是: 假设有M=m1 * m2 * m3,其中m1,m2,m3都是DWORD型的数据,m1,m2,m3两两互素 对此3个模分别求得3个数k1,k2,k3,使得k1*m2*m3=1(mod m1),k2*m1*m3=1(mod m2),k3*m2*m1=1(mod m3) 有一个数据A,A < M 求p1= A mod m1,p2= A mod m2,p3=A mod m3 ;在这一步里,因为模是DWORD型的数据,是很好计算的 然后求B=p1*m2*m3+p2*m1*m3+p3*m1*m2 ;这里已经超出计算机字长,并不好算! 再求X = B mod M ;这里也超出计算机字长,并不好算! 则 A=X ;(CRT完成)

无心人

不要害怕使用96位结构 只需要两个32位乘法两个64位加法就能搞定

ssikkiss

如果不使用CRT,要直接用2^96型数据,使用CRT,也要用2^96型数据, 不知谁更快! 我现在倾向于干脆直接使用2^96型数据了!

无心人

那也要找到相关的参数啊 GxQ倒是有一组 你可以在论坛找到 这个大的数字 最好根是2的方幂，长度也最好是2的方幂 模最好是$2^n+-1$

无心人

如果有相关的好参数 一次处理的数据甚至可以高于96bit 比如甚至最终的两项乘积可以达到上千bit 处理的bit如果适当 同样规模的乘法 大的基本单位不见得比一次32位花费时间长

gxqcn

原帖由 无心人 于 2008-5-5 20:19 发表 最好根是2的方幂，长度也最好是2的方幂 模最好是$2^n+-1$

这几个条件可并不好找，尤其是最后那句。 我现在只知道用 $k*2^n + 1$ 形式的模，还不知道 $k*2^n - 1$ 形式的模咋用？ 前者，我曾试过 $2^96 - 2^32 + 1$ 为模，但测试结果并不理想。主要是中途的进位处理非常拖后腿。

无心人

考虑过么？ 使用大的简单模 但长度小 这样子，中间乘法也达到NTT要求 则会出现迭代的NTT 是否能简化参数的选择 ================== 不过这种方式采用的少 可能复杂些 效率提升不明显