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# 无心人的帖子