主题：有人用FFT写过大数乘法吗？ -- 面壁

近来有些空，翻出以前的RSA算法，想玩玩大数乘法。找了网上很多东东，好多文章细节上都不是很清楚。自己琢磨了半天，现在只到DFT。用C语言的double，以10为基数，8位的大数相乘，误差就到了14了。肯定有办法的，不知有谁有类似兴趣做过这个？向大家讨教了。

因为硬件老师的一句话，怒了。。。其实我的专业偏软，但我只用汇编完成过大数加减乘除，相余还没有做过，有机会可以一起讨论。

先定义一个大数的数据结构，用数组表示每一位数字，然后按照乘法的规则去算就可以了，就看你对运算效率有多高的要求。

另外悄悄问一下，FFT是啥？快速傅立叶变换？这东西和大数乘法有什么关系？

呵呵，终于有人回复了。差点自删了。

讨论不敢，请教为实。我的专业更是不着边，只是对数学和编程感兴趣罢了。

这个DFT的东西当天就基本搞定了。唉，求人不如求己。是C/C++语言double的精度问题。就是说现在以100为基数，并只要认为比0.00000001还小的数是零，我的小程序应该可以计算任意大的整数相乘而没有误差。但是追求速度应该用FFT。

会汇编的人我向来都是高山仰止滴！我想这个大数相乘最终要用于RSA加密，所以还想请教老兄的大质数寻找的算法。

第一开始我觉得用乘法规则去乘，速度不快。而且顺便想弄懂FFT。后来搜到一个帖子，上面说FFT只是对很大的数(好像至少500位)效率有提高，对RSA加密的100或200位的大数用普通乘法规则也不错。

数字可以表示成多项式的形式，所以可以用到傅立叶变换。曾经河里有人2个小时就看懂了FFT，毕竟是专业人士，面壁只是感兴趣，所以才想弄懂什么是FFT，不怕大家笑话，前后花了俺1个多月。嘿嘿。

看来想法还是太局限了，看山是山，看水是水，还没有跳出来

不知老兄是否有兴趣试一试

哈哈，当然有兴趣，不过以我的速度和智商，又得至少一个月的净时间，毛时间。。。

老兄指的是那种最先进的FFT？还是别的什么名字？不妨多写写，我参与讨论。多谢了。

说来惭愧，这本书买了N年，从来没翻过，今天听你一说，模模糊糊有点印象，正好在手边，翻出来，总算派点用场。

搜了一下，不得要领。中文的资料很少，估计又得看英文的了。老兄如果有兴趣，写一下这个题目，尽量通俗点儿，好让我们外行先扫扫盲。

我也没接触过，以前只知道FFT算频谱，今天听你一说，才知道有这么一回事，一时半会儿是看不明白了，等明天有时间的，我把书上相关的章节扫描下来，发在这里，看看能否对你有所帮助。

哈哈，大家都是爱好，我更业余些。俺找时间看点，有了心得俺再来请教。兄台给的信息已经足够了。多谢了。

这个DFT的东西当天就基本搞定了。唉，求人不如求己。是C/C++语言double的精度问题。就是说现在以100为基数，并只要认为比0.00000001还小的数是零，我的小程序应该可以计算任意大的整数相乘而没有误差。

呵呵，多谢回复了，前段时间玩了玩，现在又没时间了。主要是RSA这个算法的RFC_V2.1有些东西很挠头。