- 发帖可能变空内容，邪门暂不知所以然
- 『稷下学宫』新认证方式，24年网站打算和努力目标
主题：有人用FFT写过大数乘法吗？ -- 面壁
共:💬16 🌺13 新:
家园 有人用FFT写过大数乘法吗？ 近来有些空，翻出以前的RSA算法，想玩玩大数乘法。找了网上很多东东，好多文章细节上都不是很清楚。自己琢磨了半天，现在只到DFT。用C语言的double，以10为基数，8位的大数相乘，误差就到了14了。肯定有办法的，不知有谁有类似兴趣做过这个？向大家讨教了。
家园 这个，算法大全上没有么？ 家园 用C语言写一个大数乘法不困难 先定义一个大数的数据结构，用数组表示每一位数字，然后按照乘法的规则去算就可以了，就看你对运算效率有多高的要求。
另外悄悄问一下，FFT是啥？快速傅立叶变换？这东西和大数乘法有什么关系？
家园 就是快速傅立叶变换 第一开始我觉得用乘法规则去乘，速度不快。而且顺便想弄懂FFT。后来搜到一个帖子，上面说FFT只是对很大的数(好像至少500位)效率有提高，对RSA加密的100或200位的大数用普通乘法规则也不错。
数字可以表示成多项式的形式，所以可以用到傅立叶变换。曾经河里有人2个小时就看懂了FFT，毕竟是专业人士，面壁只是感兴趣，所以才想弄懂什么是FFT，不怕大家笑话，前后花了俺1个多月。嘿嘿。
家园 受教了，没往那上去想，多谢！ 看来想法还是太局限了，看山是山，看水是水，还没有跳出来
家园 不敢不敢，面壁这是搜了一个多月后的结果。 家园 刚才翻了一下书，说是多项式变换效率更高 用于一维及多维数字卷积、多维DFT、多项式乘积、大整数乘积等快速计算中，其效率高于FFT不知老兄是否有兴趣试一试
家园 哈哈，当然有兴趣， 哈哈，当然有兴趣，不过以我的速度和智商，又得至少一个月的净时间，毛时间。。。
老兄指的是那种最先进的FFT？还是别的什么名字？不妨多写写，我参与讨论。多谢了。
家园 抄一段书 多项式变换（PT)是1978年法国著名信号处理与计算机专家H.J.Nussbaumer提出的一种正交离散变换，当时主要用来计算多维数字卷积和多维DFT,引起了国际上普遍关注，著名数学家S.Winograd指出用多项式变换成为计算二维DFT的算法同阿贝尔半单代数有密切关系，并且可能成为处理多维问题的一种有力工具。多项式变换是以多项式M(z)为模的多项式剩余环F[z]/(M[z])上的一种离散傅立叶变换，由于常用的多项式变换的计算不需要乘法运算（只需加法运算），因此已成功用于一维及多维数字卷积、多维DFT、多项式乘积、大整数乘积等快速计算中，其效率高于FFT，而且特别适合并行计算说来惭愧，这本书买了N年，从来没翻过，今天听你一说，模模糊糊有点印象，正好在手边，翻出来，总算派点用场。
家园 用汇编写过大数乘法。。。 因为硬件老师的一句话，怒了。。。其实我的专业偏软，但我只用汇编完成过大数加减乘除，相余还没有做过，有机会可以一起讨论。