论文总字数：12609字

目 录

中文摘要 3

英文摘要 4

第一章绪论 5

1.1研究背景和意义 5

1.1.1 研究背景 5

1.1.2研究意义 5

1.2国内外研究现状 6

1.3本文的研究内容 6

第二章用户界面 7

2.1用户界面流程图 7

2.2用户界面截图 7

第三章数据结构 8

3.1数据结构的处理 8

3.2符号 8

3.3函数 9

第四章算法 9

4.1大整数加法运算 9

4.1.1算法介绍 9

4.1.2加法运算程序的解读 9

4.1.3加法运算程序的流程图 10

4.1.4加法运算程序的截图 11

4.2大整数减法运算 11

4.2.1算法介绍 11

4.2.2减法运算程序的解读 11

4.2.3减法运算程序的流程图 12

4.2.4减法运算程序的截图 13

4.3大整数乘法运算 13

4.3.1算法介绍 13

4.3.2乘法运算程序的解读 13

4.3.3乘法运算程序的流程图 14

4.3.4乘法运算程序的截图 15

4.4大整数除法运算 15

4.4.1算法介绍 15

4.4.2除法运算程序的解读 15

4.4.3除法运算程序的流程图 16

4.4.4除法运算程序的截图 16

第五章总结与展望 17

参考文献 18

致谢 19

大整数算术的实现

李维豪

, China

Abstract：Cryptography plays a fundamental and irreplaceable role in the field of information security. RSA algorithm, driving safety early warning and navigation system, error checking and correcting the public key cipher algorithm and digital signature is on the basis of large integer arithmetic to implement and fast development. Due to the frequently used public key cryptography algorithm algorithm of big integer arithmetic and other basic algorithm, so if based algorithm can improve the computing speed, can effectively solve the problem of the public key cipher algorithm takes. Therefore, the implementation and development of large integer operations is the focus of this paper.

This procedure is done on Windows 32 bit system. The basis of the first to establish a large integer arithmetic program frame and when part of the auxiliary function has been successfully implemented, then added new complete part of the program. The modular thought makes every time after completion of part of the program can be to add it to the big integer arithmetic program based framework and then immediately see results and errors, convenient your correction and optimization, thus avoiding the unexplained mistake until after the found trouble. Microsoft Visual c 6.0 is made of the completion of this program and debug the main operating tools, enough to achieve high efficiency in application of the basic computing. Secondly in order to make this program has the portability and stability, to create a simple function interface. Transparent code, friendly user interface and for abnormal expression will prompt wrong, these also are to complete the program.

Key words：Large integer; The code clear and easy to understand; Modular thinking; High precision;

第一章 绪论

研究背景和意义

1.1.1 研究背景

随着信息化时代的来临，一切领域都被信息技术所覆盖，从政治到经济，从教育到社会，没有哪一个领域不受到信息技术的影响。在信息技术带给我们便捷的同时，信息安全所要经受的考验也日益严峻[3]。传统的信息安全管理逐渐难以满足日益复杂的信息安全形势的需求，来自互联网的攻击和信息泄露问题逐渐成为计算机信息安全防护的重点。信息安全出现任何问题都将关乎计算机信息的正常传递。信息安全早已引起国家保密局和国内各机构的高度重视。

随之信息安全技术的日趋完善，最佳方法就是从系统安全和数据安全这一被动一主动两方面共同协作来保障信息安全。一方面方面通过 firewall防御、virus查杀防御和预防提供等被动的防御，另一方面，主要就是靠密码学的应用来提供主动地保护。

密码技术掌握着数据安全的命脉这一点绝不是空穴来风。像身份识别、信息在存储和传输过程中的加密保护、信息的完整性、数字签名和验证都要依靠密码技术才能得以实现。密码学在信息安全领域起着基本的、无可替代的作用。RSA algorithm、驾驶安全预警与导航系统、错误检查和纠正等公钥密码算法还有数字签名都是在大整数运算的基础上在才得以实现并快速发展的。由于这些公钥密码算法频频使用大整数算法中的四则运算及其它基础算法，所以如果可以提升这些基础算法的运算速度，就可以有效地解决上述公钥密码算法耗时的难题。因此大整数运算的实现与开发是本文研究的重点。

1.1.2研究意义

大整数在很多领域都有重要的应用价值。例如在密码学方面，整数运算的长度和速度对密码运算来说至关重要，因而它对大整数运算精确度也同样有很高的要求。[4]在数学验证方面，如果仅仅靠手工计算和借助计算机完成数学中大整数的运算验证工作，几乎是无法实现的。前者在时间来说几乎是不可能的，后者又由于传统编程方法的精确度远远达不到要求，也无法完成任务。而直到有了大整数运算程序，这些工作才能得以进行。在微观模拟方面(如基因工程、生物信息、数量遗传)，可以通过数字化模拟微观世界中许多对象的活动，而且通过大整数的运算也可以非常方便的表示其活动变化。大整数还有一个最为重要的作用，就是可以保证数据存储的安全，由于它自身的定义和特性使得它构成的数据信息很难被截获，安全性也就大大提升了。例如，在RSA公钥体制下，主要使用三种长度的密钥，在平时生活中使用是521位的；如果是是商业中有需要的话一般会选择1024位的；如果是军事方面中使用则推荐2048位，安全性更好。拿商业中使用的密钥长度为例，存储它需要1KB的内存空间，密钥需要的空间为-1，相对于表达范围仅在0~-1的32位系统来说，不能被完全表示。如果不能保证运算的正常进行，整个系统会因为数的溢出而崩溃失效。因此，选择合适的数据结构和有效的算法十分的重要。

1.2国内外研究现状

由于大整数的定义就是指超出计当前程序整数类型范围的整数，所以很难用通用编程语言所完成的程序来处理它，即使是Microsoft自带的CPU数据宽度为32的“运算器”，也不能完全解决它的所有问题，所以大整数运算的实现与开发十分必要。

随着科学技术的快速发展， PC的处理能力得到大大的加强，以前只能在一些国家级的科技中心才能研究和开发的大数运算也已经逐渐普及大众化。而且大整数应用领域的也在日益扩大，成为许多高新技术开发的基石，发展前景一片大好，这些种种使得越来越多的科研人员开始投身于这项工作的开发。

Popie 和Steinn在1960 年提出了通过运用乘法和除法来代替模乘计算的思想[5]，21年后 Knuth在他们思想的引导下，通过不断地实验具体给出了一种估商型模乘算法。之后在1983年，Blakley 加以改进，提出可以通过一系列加法来代替模乘的加法型模乘算法[6]。之后人们在他思想的基础上相继提出了窗口模乘算法和滑动窗口模乘算法还有一些改进方法，成功的的减少所要使用的加法的次数，取得了比较理想的效果。在1985年，Montgomery另辟蹊径提出一种将普通的模乘转化为更加易于计算的特殊模乘的改进算法，在经过人们的不断改进后，同样得到了非常广泛的实际应用。

同样有很多的学术著作都曾深刻的介绍过大数算数，像《The Art of Computer Programming Volume 2》、《Handbook of Applied Cryptography》、《Kryptographie in C und C 》和《BigNum Math: Implementing Cryptographic Multiple Precision Arithmetic》等都带给我多个方向的启迪[7]，比如在高效算法所使用的数学概念，应用密码学如何在大数算数中成功实现，以及大数算数如何应用在编程方面。

1.3本文的研究内容

本程序是在windows 32位系统上完成的。首先先建立大整数运算程序的基础框架并当部分辅助函数已经成功实现后，再将新完成的部分程序加进去。这种模块化的思想使得每当完成一部分程序后，都可以将它加入大整数运算程序基础框架中然后立马见到成效和错误，方便自己的改正和优化，这样就避免了直到整体完成后才发现不明原因错误的烦恼。Microsoft Visual C 6.0是本程序完成制作并进行调试的主要操作工具[8]，在程序中力求达到足够高效率的基本运算。其次为了使本程序具备可移植性和稳定性，创建了简单明了的函数接口。清晰易懂的代码，友好的用户界面，显示计算所花费的时间和对于异常的表达式会提示出错，这些同样都是本程序所要完成的。

第二章 用户界面

2.1用户界面流程图

开始

剩余内容已隐藏，请支付后下载全文，论文总字数：12609字