想实现FNT，谁陪我实现？

无心人 · 发表于 2009-2-12 22:12:12

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

呵呵

不知道哪位大哥愿意实现FNT，快速费马数变换

即唯一一个可以做到无乘除法参与的大数快速乘法算法的数轮变换

时限是10年，呵呵

就在这里讨论

gxqcn · 发表于 2009-2-13 07:46:42

请先详细介绍 F N T 三个字母的确切含义，
并说明何以是“唯一一个无乘除法参与的大数快速乘法算法”？

无心人 · 发表于 2009-2-13 08:10:30

为什么是无乘除法，你看那个数轮变换的帖子

mathe · 发表于 2009-2-13 08:22:30

我想,为什么是无乘除法,gxqcn应该是理解的,他不理解的应该是"唯一"

无心人 · 发表于 2009-2-13 08:25:30

当且仅当模形式是$2^n +- 1$，$\alpha = 2^k$的数轮变换才不需要乘除法
而模形式是$2^n - 1$时，$\alpha$不可能是2的幂形式
（如果是2的幂形式，得到的变换无法有快速演算形式）
所以仅可能的模形式是$2^n + 1$
这个有FNT，
也有广义FNT，即$n$不是2的幂形式，这时的$\alpha$我不知道是否依然能为2的幂

这个我承认有点冲动了，么验证就说了

g99 · 发表于 2009-2-13 09:10:01

10年为期，很不错

suan1024 · 发表于 2009-2-13 10:00:29

三项式变换选 M N a 要用到好多数论知识需要实现如下算法的
碍事筛法，分解质因数，计算素数的原根，模取幂运算，扩展欧几里得算法来确定参数p M, N, a
高度符合数N ＝ 2^n，为的是快速变换，什么按时按频的，二机四机分割机的，很多算法

无心人 · 发表于 2009-2-13 10:25:48

三项式变换在大数乘法上并不怎么实用

我讨论的是FNT

另外，10年是表示我懒
把期限放很宽罢了
哈哈

suan1024 · 发表于 2009-2-13 12:23:48

Fn = 2 ^ b + 1， a = 2, 或 sqrt(2), N = 2^n
在b位上进行模b+1位的运算，把乘法变加法和移位？

无心人 · 发表于 2009-2-13 13:57:31

对

模就是移位和加减法

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 想实现FNT，谁陪我实现？

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。