论坛 › 算法交流 › 大整数计算相关论文

无心人 发表于 2008-4-14 17:02:03

中午看了joey5491在那帖子里的回复
想来apfloat的NTT+CRT也不是很完美的
我的数论变换也快写到具体的几个变换了
等写到了，每写一种，有价值的我都分析下吧
觉得迭代式的NTT也未尝不是一个途径
况且，类FNT变换的限制也不是很大的

liangbch 发表于 2008-4-21 16:51:27

新加一篇论文，来自http://www.loria.fr/~zimmerma/bignum/

An implementation of Schönhage's multiplication algorithm

liangbch 发表于 2008-4-21 17:12:39

An GMP-based implementation of Schönhage-Strassen's large integer multiplication algorithm
第一楼的第2篇文章和本楼的2篇文章同名。也就是说这3篇文章同名，但内容各不相同。我们注意到：
第一篇文章（1楼第二篇)的作者为Paul Zimmermann
第三篇文章（issac2007-slides.pdf) 作者为 Alexander Kruppa
第二篇文章（issa07.pdf)的作者为Pierrick Gaudry,Alexander Kruppa,Paul Zimmermann，包括上面2篇文章的作者。

无心人 发表于 2008-4-21 17:19:38

这几篇东西有什么闪光点？

liangbch 发表于 2008-4-21 18:30:15

基本上可以断定，GMP中的FFT并非真正的FFT（应该属于一种NTT）其算法应该就是楼上提到的算法，研究这些论文，就可以弄明白GMP中的大数乘法中最难的FFT是如何实现的，从而可以仿照他们的算法，编写出速度接近甚至超过他们的大数相乘程序来。

无心人 发表于 2008-4-21 19:15:22

:)

你想做最好的整数卷积算法还是最好的NTT算法还是最好的整数FFT算法
可绝对绝对不同的级别啊

无心人 发表于 2008-4-21 19:16:38

:)

可以断定
GMP乃模仿FFT中的算法
但以整数$\omega$和模$2^m+1$代替FFT浮点参数

liangbch 发表于 2008-4-22 11:43:48

站内链接: Fast Division of Large Integers

liangbch 发表于 2008-5-4 18:04:02

发现一本介绍大数运算的 中文图书，书名《BigNum Math:加密多精度算法的理论与实现》，china-pub链接 http://www.china-pub.com/937746

无心人 发表于 2008-5-4 20:21:43

刚看了目录

怎么说呢

聊胜于无吧

真正有志实现大数库的

还是 Knuth的书，和一本介绍公开密码算法的书组合最好了，这本中的知识可做knuth的补充

另外就是一本快速傅立叶变换加80年的两本（数论变换、快速数论变换），大概93-94年的一本 广义斐波那契-卢卡斯序列，一本椭圆曲线的书

英文的没发言权

==============================
对于一本介绍大数运算的书，231页的篇幅是太少太少了，至少要600页才能大概说明白

查看完整版本: 大整数计算相关论文