关于FNT乘法， 我想可能有点误会，想讨论的进来

无心人

本来想循序渐进在那个帖子里讲的
现在在这里先说点

FNT以$M=2^2^t+1, N=2^{t+1}, \alpha=2$作为参数计算NTT
变换长度是$N=2^{t+1}$，因为需要一半填充$0$，所以实际能计算大数的长度是$2^t$块
根据卷积特性，每个块的数字最大是$root{2}{2M / N}=2^{{2^t - t}/2}$，实际取${2^t-t}/2$个bit位

由于$\alpha=2$所以中间步骤仅为加法减法和移位。
变换后的乘法如果还太大则还可以用FNT加速

考虑$M=2^2^10+1, N=2^11, \alpha=2$
则可以进行最大$2^10$个数字块，每个块最大$2^{{1024-10}/2} = 2^507$，共$507$bit，假设为计算方便，取到$507/32=15$双字
则其总可计算bit长度是$1024*15=15360$双字的乘法

和你们熟悉的NTT+CRT做法不同，中间的乘法要以480bit的乘法进行了 ：）
计算的过程除了2048个480bit乘法外，均是加减和移位操作
（$mod 2^2^t+1$操作可转化为减法和移位）

liangbch

GMP 用的是什么算法，楼主研究过吗？

无心人

没有啊

FNT缺点就是有点不灵活
字长和变换长度受限

听说GMP是伪FNT

无心人

伪FNT这么定义

  $M = 2^{k*2^t} + 1$
    $N, \alpha$抱歉不知道如何定义，要看数论变换的书
  稍后几天会在那帖子里说

liangbch

几乎所有的资料都显示，计算大数（非常大）最快的算法是快速傅立叶变换和快速数论变换。对于前者，简称FFT，这应该没有争议。对于后者，一般简称FNT.所以对于FNT我一般认为是快速数论变换。而楼主对FNT的定义是费马数数论变换，这也是我们经常误解的原因之一。

   FNT 指快速数论变换，有下列资料为证：
1. 楼主也曾在http://topic.csdn.net/t/20040815/11/3275755.html 提到：

普通n   位   u   乘   m   位   v的算法在   n,   m很大时就会很慢   
   
  有下面的几个快速算法   
  1、karatsuba算法   
  2、Toom-Hook算法   
  3、模算法   
  4、FFT快速复数富利叶变换算法   
  5、FFT快速整数富利叶变换算法   
  6、FNT快速数论变换算法

2。 http://www.ppvista.net/software/p4/A4519.shtml 中的FNT也指快速数论变换。

无心人

不存在通常意义上的快速数论变换
要NTT是快速数论变换必须满足下列条件
$M$二进制表示简单，$N=2^b$, 最好还要$\alpha=2^c$

Fast Number Theory Transform怎么也不能简化成FNT吧？
FNT确实有时候就是快速数论变换，但一般就是当为费马数变换时才这么说吧

liangbch

在apfloat中，
     1）三个模是 2113929217, 2013265921, 1811939329，这三个数都是素数，但并不是费马数。
     2）对应的三个原根5, 31, 13。
     3）变换长度是 $2^t$, t为整数，但$2^t$不能大于模，另外，apfloat 还是变换长度为 $3xx2^t$的算法。
   可见apfloat并非使用费马数变换。

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亿位，不知对否？

无心人

NTT里$M, N, \alpha$相关，但不要求必须满足快速条件

liangbch

原帖由 无心人 于 2008-4-17 18:29 发表
NTT里$M, N, \alpha$相关，但不要求必须满足快速条件

M 应该是模，N是变换长度，$\alpha $是M的原根. 在apfloat 中，M,N, $\alpha$ 是有限制条件的。 M 和 $\alpha $ 是相关的。M必须是素数。

在 http://topic.csdn.net/t/20041010/17/3441530.html 那个帖子中，joey5491和mathe 给出了更加宽松的条件。
joey5491说: 其实FFT不需要用到质数模就可以运作,apfloat的方法之所以要用到质数,最主要是因为用到了CRT(中国余数定理).   
joey5491又说， 做CRT的三個模數, 只要互質即可, 不必然要是質數.
mathe说，需要 (N,m)=1,   (W-1,m)=1.

N 一般为2^k, M则是越接近$2^t$越好，比如$2^t+1$ 或者$ 2^t-1$或者费马数，这样模运算就可不用除法，而使用加减法来代替。
但是 http://topic.csdn.net/t/20041010/17/3441530.html 给出的结论未经证实，如果能够找到很好的模，则可免去除法。如果找到更大的模，则可将3次变换变为2次。
（当前的apfloat需要3次变换，需要将3次变换的结果由CRM 求得其最终结果）。

无心人

我在数论变换简述中的帖子已经完全的把数论变换满足的条件叙述清楚了