C语言大整数运算库的研究与实现.doc

摘要:随着社会的不断进步，科技的不断创新，大整数精确运算在密码学、基因工程、数学验证等方面有着重要的价值。在现代密码学中，安全性基于复杂数学问题的难解性的假设的加密方法，往往需要进行大整数运算，这些大整数已经远远超过了程序设计语言所能表示的最大整数值范围，也不能使用一般的四则运算法则进行运算。本文介绍了一种这样的大整数在程序设计语言中的表示的方法，并对这种方法表示的大整数的基本运算进行了分析，给出了实现算法。

本文基于32位的系统，首先采用模块化的思想建立大整数运算库的基础框架，在实现一些辅助函数后在此框架上讨论并实现多精度大整数的基本加法、减法、乘法、除法、平方算法、缩减、模乘、模幂乘等算法。所用程序均采用C/C++语言编写，所采用的优化也均建立在C/C++语言这一层面上，在保证算法有足够高的效率的同时力求代码清晰易懂，函数接口简单明了，具有可移植性和稳定性。

关键词 多精度大整数；Comba;分治法；平方算法

目录

摘要

Abstract

1 绪论-1

1.1 研究背景-1

1.2 研究内容-1

1.3 研究路线-1

2 大整数的数据结构-2

 2.1 大整数的结构与基选择-2

2.1.1 大整数处理的数据结构选择-2

2.1.2 基选择-2

 2.2大整数结构-2

 2.3预定义变量-3

 2.4大整数基本函数定义-3

 2.5 大整数的移位函数-4

3 大整数加法和减法实现-7

 3.1 加法运算-7

 3.2 减法运算-9

4 大整数乘法实现-12

5 大整数除法实现-17

6 运行界面-19

结论-20

致谢-21

参考文献-22

附录-23