大整数基本运算的研究与实现.zip

摘要：随着科学技术的发展，需要应用大整数运算的场合越来越多。大整数是指超出了程序设计语言整数类型的值集范围，所以它的表达、存储、读取、处理、输出等问题用一般编程方法难以实现。在科学计算方面，大整数的运算是必不可少的，因为科学计算中为了确保精度通常参与运算的数值都非常大，此外计算机编程语言中的浮点数据类型精度也达不到科学计算的要求，通过对大整数的运算的推广可以实现任意精度浮点数的计算。在信息安全方面，著名的RSA、ElGamal公钥密码体制，都是建立在大整数运算的基础上的。

本文侧重于从数学理论角度，首先对大整数的基本运算进行深入研究，然后根据总结出的大整数基本运算的算法，详细阐述了大整数在计算机上的表示，以及大整数加减乘除等基本运算的软件实现，并且着重讨论了大整数基本运算的乘法、除法和乘方算法。本文对这三类运算都采用了两种算法，对于乘法实现了Baseline乘法算法和Karatsuba乘法算法，对于除法实现了二分试商法除法算法和精确试商法除法算法，对于乘方算分实现了经典乘方算法和快速乘方算法。最后，本文分别对这三类算法进行了深入的实验分析，对于三类运算中同类的两种算法都分别进行了对比测试得出试验数据。以验证各个算法的实际计算效率是否与理论一致。其中，所有算法均是在64位Windows操作系统下，以C++为开发语言，以Visual C++ 6.0为开发工具，实现了所有大整数基本运算算法并进行了实验测试分析，通过周密测试给出了详细的实验数据。

关键词 大整数；Baseline乘法；Karatsuba乘法；二分试商法除法；精确试商法除法；经典乘方算法；快速乘方算法

目录

摘要

Abstract

1 绪论-1

1.1 背景简述-1

1.1.1 研究意义-1

1.2.2 研究概况-1

1.2.3 主要工作-2

1.2 理论基础-2

1.3 其它说明-4

2 大整数的表示与比较-6

2.1 常用表示方法概述-6

2.2 本文表示方法详述-6

2.3 大整数的比较算法-7

3 整数环上的运算-9

3.1 加法-9

3.2 减法-9

3.3 乘法-10

3.3.1 Baseline乘法算法-10

3.3.2 Comba乘法算法-11

3.3.3 Karatsuba乘法算法-11

3.3.4 乘法算法分析与测试-13

4 带余数除法运算-18

4.1 理论基础-18

4.1.1 二分试商法-18

4.1.2 精确试商法-19

4.2 算法描述-23

4.2.1 一位商除法算法-23

4.2.2 多位商除法算法-24

4.3 算法实现-24

4.4 实例分析-25

4.5 对比测试-26

5 乘方算法的优化-28

5.1 算法描述-28

5.1.1 经典乘方算法-28

5.1.2 快速乘方算法-28

5.2 对比测试-29

6 综合应用与系统实现-33

6.1 软件实现细节与分析-33

6.2 模素数一次同余方程-34

6.2.1 辗转相除降模法算法-34

6.2.2 综合应用测试与分析-36

6.3 算法正确性检验系统-37

6.4 时间复杂度估测系统-38

6.5 大整数基本运算系统-39

结论-42

致谢-43

参考文献-44