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

仙剑魔 · 发表于 2008-8-30 21:43:08

#39说得没错,只是做乘法的话,可以不倒位序数论变换和傅立叶变换一样有基时分和基频分2种算法基时分是先倒位序再用蝴蝶形算法基频分是先用蝴蝶形算法再倒位序所以只要先用基频分做正变换再用基时分做逆变换,就可以省略倒位序的过程

无心人 · 发表于 2008-8-30 21:53:12

受教受教呵呵

仙剑魔 · 发表于 2008-8-30 22:00:41

用CRT是怎么个情况呀是不是中间计算的时候有a*b%c的时候,为了弥补这个乘法变量字长不够用的? 我不是很清楚CRT的作用

无心人 · 发表于 2008-8-30 22:09:23

CRT乃中国剩余定理也是用三个不同参数但变换长度相等的变换最后以CRT得到最终结果以达到减少字长，简化运算的目的啊请看俺数论变换的那个帖子应该有相关介绍吧

仙剑魔 · 发表于 2008-8-30 22:41:06

有点了解是怎么回事了我一直在用单个变量长度计算诶...真狭隘...就因为这个我一直在考虑增加字长又要避免益出

无心人 · 发表于 2008-8-31 21:14:44

你考虑在相同的变换长度上，最简单的变换是 FNT，速度也最快但缺点是变换长度固定在我那个帖子里有相应的FNT变换参数列表 FNT迭代意义下的大数字乘法是最优化的但有点失之于复杂了相对于CRT和FFT（整数意义下的模2^n + 1）也存在不同程度的空间复杂度的增加而CRT特点在于变换代码不涉及大数字运算仅中间步骤乘法有部分小的大整数的运算但需要进行至少三次的不同参数的变换参数的选择面受限于变换长度的限制可选择的参数有限，且alpha的值很可能不是2的幂基于模2^n + 1的变换则可能处于CRT数论变换和FNT之间吧 ==================================== 是我粗略的理解并没仔细的思考如有错误请指正

仙剑魔 · 发表于 2008-9-6 14:45:22

学会了.. 用了CRT以后就相当于同步进行3个变换了我为了中间计算不超出32字节,特意挑选了特殊的素数 p=a*2^b+1=k^2+1,这样a必须是平方数,b必须是偶数... 但是最后用CRT的组装的中间计算挺麻烦的我做1E8进制的变换,组装后的结果大约有15-16的十进制位,但是中间计算却有20+的十进制位这个地方让我很不爽...

无心人 · 发表于 2008-9-6 15:26:48

那你就实现FNT吧那个没乘法的光加减和移位操作就能完成的

仙剑魔 · 发表于 2008-9-6 17:35:20

FNT的参数不知道怎么选费马数不是从第5个开始不是素数的么原根,变换长度我就晕的...

还有我搞不清那个移位的确切价值貌似就算可以移位还是要算 mod p 的而且如果移位了我就不能用那个减小中间运算大小的方法了

最关键的问题: 目前最擅长的还是VB6,没有移位,所以白搭

无心人 · 发表于 2008-9-6 18:02:05

不是素数的费马数必须以2或者根号2为alpha 此时的幂乘就是移位而且模费马数的运算实际上是个减法

账号		自动登录	找回密码
密码			欢迎注册

[讨论] NTT相关问题一则，有兴趣的参与

回复 44# 无心人的帖子

[讨论] NTT相关问题一则，有兴趣的参与

回复 44# 无心人 的帖子

回复 44# 无心人的帖子