文档介绍：摘要
随着计算机技术和因特网的迅速发展，计算机已经深入到各行业的方方面面，与此
同时，信息 安全也变得越来越重要，而密码技术则是保障信息安全的一个重要手段。RSA、
ElGamal 等公钥密码算法都是建立在大整数运算的基础上，模缩减、模乘、模幂算法被
大量使用。基于性能的原因，在密码算法中使用的大整数其二进制位数一般在 2048bits
以内。
在科学计算特别是大规模科学计算中，IEEE 754 标准定义的浮点格式可能无法满足
计算精度要求，可利用大整数来构建高精度的浮点数据类型，确保最终输出结果的正确
性。此外，大整数还被用来精确计算某些常数，如自然对数底数 e 和圆周率 π 等。在这
类应用中，大整数乘法是最核心的运算，数据量也更大，其 10 进制位数可能达到上亿
位甚至更高，有时也称为超大整数。
本文侧重于从数学运算功能的角度，对大整数数值算法的核心——大整数乘法算法
进行深入研究。本文首先对大整数乘法算法要用到的数学知识进行了简单归纳，介绍了
大整数的底层实现与基本操作。在此基础上，对传统的笔算乘法、Comba 乘法、Karatsuba
乘法以及 FFT 乘法进行了对比分析研究，并给出了快速实现方法，提供了详细的测试数
据。最后，本文提出了一种将 Karatsuba 乘法与 FFT 乘法相结合的改进乘法算法，测试
表明，其具有良好的灵活性和很高的效率。
本文在 32 位 Windows 操作系统下，以 C99 标准 C 为开发语言，以 VC++ 2010 为开
发工具，实现了上述所有算法并进行了优化设计，通过周密测试给出了详细的实验数据。
关键词：大整数；乘法；Comba；Karatsuba；FFT
I
Abstract
With the rapid development of computer technology and the Internet, the computer has
gone deep into all aspects of the industry, at the same time, information security has become
increasingly important, and the password technology is an important means of ensuring
information security. RSA, ElGamal, and other public-key cryptographic algorithms are all
based on numerical algorithm on large integers, modular reduction, modular multiplication,
modular exponentiation algorithm have been widely used. For performance reasons, the
number of bits of large integers used in cryptographic algorithms is always less than 2048
bits.
In scientific computation, especially in large-scale scientific computation, the floating
format defined by IEEE 754 standard may not be able to meet the computational accuracy
requirements, large integers can be used to build high-precision floating-point data types to
ensure the correctness of the final output. In addition, large integers have al