找回密码
 欢迎注册
楼主: 无心人

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

[复制链接]
 楼主| 发表于 2008-5-1 22:08:04 | 显示全部楼层
费马数变换,就比较理想 如果不考虑字长的话 如果考虑字长,则看用途 用于大数运算的,可适当扩大大数的基以不浪费空间 如果是计算卷积 做多次不同模的NTT 再用CRT做减少字长的处理
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-4 20:58:21 | 显示全部楼层
抱歉!更正我以上发的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..)就很少见了.这使得其计算会稍慢.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-5-4 21:17:05 | 显示全部楼层
先回答容易的2,使用伪费马数变换似乎容易找到 问题1、如果某个一次变换的根简单,我觉得还是一次变换好,只要根是2方幂,则中间步骤就简单 如果找不到,用CRT三次变换并不慢 问题1的C并不是专业人员考虑的,不要问这个问题
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-5 18:27:43 | 显示全部楼层
用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完成)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-5-5 18:31:12 | 显示全部楼层
不要害怕使用96位结构 只需要两个32位乘法两个64位加法就能搞定
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-5 18:44:05 | 显示全部楼层
如果不使用CRT,要直接用2^96型数据,使用CRT,也要用2^96型数据, 不知谁更快! 我现在倾向于干脆直接使用2^96型数据了!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-5-5 20:19:49 | 显示全部楼层
那也要找到相关的参数啊 GxQ倒是有一组 你可以在论坛找到 这个大的数字 最好根是2的方幂,长度也最好是2的方幂 模最好是$2^n+-1$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-5-5 20:24:20 | 显示全部楼层
如果有相关的好参数 一次处理的数据甚至可以高于96bit 比如甚至最终的两项乘积可以达到上千bit 处理的bit如果适当 同样规模的乘法 大的基本单位不见得比一次32位花费时间长
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-5 20:29:28 | 显示全部楼层
原帖由 无心人 于 2008-5-5 20:19 发表 最好根是2的方幂,长度也最好是2的方幂 模最好是$2^n+-1$
这几个条件可并不好找,尤其是最后那句。 我现在只知道用 $k*2^n + 1$ 形式的模,还不知道 $k*2^n - 1$ 形式的模咋用? 前者,我曾试过 $2^96 - 2^32 + 1$ 为模,但测试结果并不理想。主要是中途的进位处理非常拖后腿。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-5-5 20:36:26 | 显示全部楼层
考虑过么? 使用大的简单模 但长度小 这样子,中间乘法也达到NTT要求 则会出现迭代的NTT 是否能简化参数的选择 ================== 不过这种方式采用的少 可能复杂些 效率提升不明显
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-11-22 00:40 , Processed in 0.024361 second(s), 15 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表