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