主题:有人用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有些东西很挠头。