求有限域GF(2^m)上的FFT算法
据说在实数域上的任意n都存在时间复杂度0(nlogn)的FFT那么有限域上是否也是如此的?
在GF(2^m)的域上最大的变换长度是2^m-1
用素因子算法或Cooley-Tukey算法等分解到长度为p(素数)的DFT
然后怎么整?
用Rader算法把长度为p的DFT转化成长度为p-1的卷积的话
悲剧的发现没有原根可以用了,连运算法则都不同了
现在唯一想到的是把那个卷积按大数乘法的分治法那样搞
但是那样的时间复杂度不是0(nlogn),而是o(n^1.67)
求更好的方法... 可惜费马素数已知的有限，而且都太小了点。 2# gxqcn
实数域上原根任意长度的都好计算
有限域上不光难找,而且改变了运算规则
只能从运算分解入手,真悲剧
PS:话说我个潜水的突然发现有了个攻擂高手奖章,神马情况... 对GMP中的算法FFT算法尚未做研究，不过我学习过apfloat,现将apfloat中的数论变换说一下。在apfloat中，
1）三个模(m)是 2113929217, 2013265921, 1811939329，这三个数都是素数，但并不是费马数。
2）对应的三个原根5, 31, 13。
3）变换长度是 2^t, t为整数,2^t,是(m-1)的因子。
因为 2113929217= 63*2^25+1，2013265921= 15*2^27+1，1811939329= 27*2^26+1，故其变换长度最大可为 2^25=33554432, 因为 apfloat使用10^9进制，所以在计算大数乘法时，其 乘数长度+被乘数长度不能大于33554432 *9 =301989888~~3亿位10进制数。
更多详细的信息请看我在站内帖中关于《FNT乘法， 我想可能有点误会，想讨论的进来》的讨论 4# liangbch
数论变换基本掌握
我问的那个其实是GF(2^m)的伽罗华域
而数论变换的域是GF(p)(p是素数)
这两个的运算规则不一样
加法GF(p)是(a+b)mod p,GF(2^m)是a xor b
乘法GF(p)是(a*b)mod p,GF(2^m)是对应幂次相加后再找值(实现的时候就是靠查表)
因为这个所以我跪了... 楼主能否给出关于有限域方面的参考读物？ 6# liangbch
我也是看RS码现学现卖的
那个PDF超过附件限制发不上来
暂且贴下域的部分
以GF(2^m),m=16为例
我现在的处理是：
65535=3*5*17*257
这样变换长度为65535的FFT能够被分解为4个维度上的短FFT
也就是计算变换长度分别为3,5,17,257的FFT
原理见"素因子算法"或"Cooley-Tukey算法",两个算法效果接近，只是"Cooley-Tukey算法"多一个旋转因子
3,5,17这3个我懒得优化了
257这个我想优化下
于是观摩了下"Rader算法",他能够把N点的FFT用N-1点的循环卷积来表示
无奈由于这个有限域的定义，257-1=256的循环卷积无法用FFT做（运算的定义不同，不然直接NTT了）
然后我想到（其实是BAIDU发现有这么个关系存在）先计算2*(N-1)的线性卷积，再叠加得到N-1点的循环卷积
至于计算的方法，因为FFT不能用了，只好用Karatsuba了
刚才试了下，效果还是有的
只是Karatsuba需要额外开内存，反复的new和delete后速度会很悲剧
现在设定递归时N>30才使用，否则就直接计算
就这么个情况。。。
页:
[1]