求有限域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)$ 求更好的方法...

gxqcn

可惜费马素数已知的有限，而且都太小了点。

仙剑魔

2# gxqcn 实数域上原根任意长度的都好计算 有限域上不光难找,而且改变了运算规则 只能从运算分解入手,真悲剧 PS:话说我个潜水的突然发现有了个攻擂高手奖章,神马情况...

liangbch

对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)$是对应幂次相加后再找值(实现的时候就是靠查表) 因为这个所以我跪了...

liangbch

楼主能否给出关于有限域方面的参考读物？

仙剑魔

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$才使用，否则就直接计算 就这么个情况。。。