摘要：乘法一直是人类科学发展过程中非常重要的运算工具，许多科学问题的解决都依赖于准确、快速的大整数乘法运算。本文介绍了几类在不同阶段具有代表性的大数相乘算法，具体包括：

（1）竖式计算乘法：这是最早提出的乘法计算方式，形式上类似于人的笔算，时间复杂度为，当问题规模增大时计算所需要的时间会急剧增加，因此该算法不适用于大数相乘的场合。

（2）Karatsuba乘法：这是对两数乘法运算的第一次改进。算法运用分治的思想，分别将乘数和被乘数均分为两段，以少量的加法运算来替代部分乘法运算，时间复杂度为。

（3）多项式乘法：该算法基于快速傅里叶变换（FFT），首先将乘数和被乘数转换为两个多项式的系数向量，然后用FFT计算两个系数向量的卷积，之后对应相乘，再通过IFFT得到最终结果。算法的时间复杂度为，计算速度得到了进一步的提高。

（4）David Harvey–Joris van der Hoeven算法：该算法同样基于快速傅里叶变换，将乘数和被乘数变换到某个多元多项式环上进行相乘，在该多元多项式环中存在特别有效的乘法算法，使得两数相乘所消耗的时间较之于FFT来讲可以忽略不计，算法的时间复杂度为。

本文详细阐述了以上几种算法的算法思想及推导过程，对这几种算法的复杂度进行了分析，并使用matlab编程实现了前三个算法，借助具体实例进行比较分析，更深入的理解了算法的执行效率。

关键词：大整数乘法 分治法 快速傅里叶变换 时间复杂度

目录

摘要

Abstract

1引言-1

1.1研究背景及意义-1

1.2国内外研究现状-1

1.3本文主要工作-2

2早期的大数相乘算法-3

2.1竖式计算乘法-3

2.2Karatsuba乘法算法-5

2.2.1算法思想和复杂度分析-5

2.2.2算法的实现-7

2.2.3算法的最优讨论-10

3基于快速傅里叶变换的大数相乘算法-12

3.1时间复杂度为的大数相乘算法-12

3.1.1多项式乘法算法-12

3.1.2基于快速傅里叶变换计算点值-13

3.1.3基于快速傅里叶逆变换计算插值-16

3.1.4算法的实现与性能分析-18

3.2时间复杂度为的大数相乘算法-22

3.2.1算法思想-23

3.2.2算法的性能分析与优缺点-24

4总结-25

致谢-26

参考文献-27