想实现FNT，谁陪我实现？
呵呵不知道哪位大哥愿意实现FNT，快速费马数变换
即唯一一个可以做到无乘除法参与的大数快速乘法算法的数轮变换
时限是10年，呵呵
就在这里讨论 请先详细介绍 F N T 三个字母的确切含义，
并说明何以是“唯一一个无乘除法参与的大数快速乘法算法”？ :)
为什么是无乘除法，你看那个数轮变换的帖子 我想,为什么是无乘除法,gxqcn应该是理解的,他不理解的应该是"唯一":lol 当且仅当模形式是$2^n +- 1$，$\alpha = 2^k$的数轮变换才不需要乘除法
而模形式是$2^n - 1$时，$\alpha$不可能是2的幂形式
（如果是2的幂形式，得到的变换无法有快速演算形式）
所以仅可能的模形式是$2^n + 1$
这个有FNT，
也有广义FNT，即$n$不是2的幂形式，这时的$\alpha$我不知道是否依然能为2的幂
这个我承认有点冲动了，么验证就说了 10年为期，很不错:b: 三项式变换 选 M N a 要用到好多数论知识 需要实现如下算法的
碍事筛法，分解质因数，计算素数的原根，模取幂运算，扩展欧几里得算法 来确定参数p M, N, a
高度符合数N ＝ 2^n，为的是快速变换，什么按时按频的，二机四机分割机的，很多算法 :)
三项式变换在大数乘法上并不怎么实用
我讨论的是FNT
另外，10年是表示我懒
把期限放很宽罢了
哈哈 Fn = 2 ^ b + 1， a = 2, 或 sqrt(2), N = 2^n
在b位上进行模b+1位 的运算，把乘法变加法和移位？ 对
模就是移位和加减法
页:
[1]
2