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

是否能简化参数的选择
==================
不过这种方式采用的少
可能复杂些
效率提升不明显