(毕业论文   页数:29字数:10981)摘 要: 本文主要论述三方面的内容:一是浅谈大数计算的计算类型，思考大数简单计算的算法，并且做出可行的程序设计；二是将前面生成的算法应用到椭圆曲线密码体制中；三是展望大数计算的发展前景。另外在探讨大数的表示方法和存储技术的时候，文章提到了最常用的数组表示法。本文在设计有关大数间简单运算（加、减、乘、除、取模等）算法的同时，还比较了大数模乘的三种常见算法（加法型算法、估商型算法、Montgomery型算法）。最后结合大数计算在椭圆曲线密码体制中的应用，文章做了一些简单的工作。
[关键词] 椭圆曲线加密体制 大数计算 算法

ABSTRACT
This paper discusses mainly three parts: in the first place, treatise the kinds of computation about larger-number, study arithmetic of simple computation, and design program; secondly, applying the arithmetic above-mentioned to ECC; one more, outlook the development of computation about larger-number. To explain representation and memory about larger-number, the paper relates to the most familiar method----using array. Later, the paper introduces a sort of arithmetic for solving the problem of simple operation (plus, minus, multiply, divide, module, etc.) about larger-number, and compares three kinds of familiar arithmetic of larger-number's module-multiply (addition-arithmetic, estimate quotient arithmetic, Montgomery-arithmetic). Finally, making use of the application of larger-number' computation in ECC, I do some simple works.
[Keywords] ECC computation about larger-number arithmetic

目录:

一、引言
二、讨论超大数、超高精度数的表示方法和存储技术
三、大数计算算法的讨论
四、大数计算在椭圆曲线密码体制中的应用
五、量子计算机的出现与大数计算的发展

一、引言
大数的计算主要牵扯到两个方面的问题：
(1)大数的存储问题，即超大数的存储和超高精度数的精度问题；
(2)大数计算的算法问题，主要涉及大数间四则混合运算及阶乘、大数分解以及有关大数模的取模、模加、模乘、模逆、模幂运算等。
需要笔者指出的是，在本文中大数的概念涉及到了超大数和超高精度数两方面的含义。
二、讨论超大数、超高精度数的表示方法和存储技术
数值处理是计算机的重要应用之一，但目前的计算机所标称的有效数值范围仍是依据计算机的字长来规定的，像现在的Pentium64位机，超过20位有效数字的数值就已不能完整表示。
随着社会经济和高端科学的发展，超大数量级的数值处理也被越来越多的应用到社会和生活的各个领域，比如在国家的经济生活中，决策者们需要通过收集、整理、统计和分析工农业的有关各项数据，从而得到精确的结果，借以指导社会经济的下一步发展；在航空航天领域，科技工作者们更要处理大量的数据，其中一些不乏属于超大数量级的或超高精度的，整个处理计算的过程不能有丝毫的纰漏，而与此同时，假如他们的计算机却做着一些四舍五入之类的工作……由于这一类的数值计算都需要有高性能和高精度的数据处理方式作为保障，所以计算机数据处理长度受限的问题不解决是不行的。
（一）超大数的存储技术
我们采取一些“软处理”方面的方法来实现超大数的存储问题：
1、通过数制转换，利用数组实现存储
作为实现大数存储最常见的一类方法，利用数组的普通做法是：将一个有N位的超大数存入数组，每个数组的一个元素表示一位十进制数，若是N并没有超过普通PC机允许定义的范围，那么由这样而生成的算法是简单易行的（在论文的后面，附有百位左右的大数进行简单意义上的数学运算的C代码）。
但若是要存放比如说10000的阶乘（共有35660位），就要定义一个长度为35660位的一维数组，由于一般的PC机并不能定义这样庞大的数组，因而这个阶乘值就无法求出。这种情况下我们必须再采取一些手段，使得该数组的长度变的更加短一些，也就是要存放的这个数字的位数变少——这很容易让我们想到进行数制转换。
1985年，西安交通大学王永祥副教授就曾提出过采用万进制的方法。按照这种方法，每个数组元素表示一位万进制数，则长度为35660的十进制数就变做长度为8915位的万进制数，这样就可以用一个8915位的一维数组来存储，在PC机上就可以求出10000！。显然采用万进制数大幅度的减少了存储空间，而带来的直接好处是大幅度减少了计算时间，提高了计算速度。
但是通过这种方法，数组在定义范围上的约束已经存在。
2、在VC++中使用无符号长整型队列实现大数的无位数限制
前面提到的数组表示法由于需要在使用之前定义数据元素的个数，也就是总的二进制位数。如果超出这个位数将溢出或发生异常，这样一来势必会造成运算过程中对总位数和空间利用率的限制，因此要对运算加以恰当控制。但是数组表示法能够实现的只是特定有限位大数及其运算，而对于大数的位数不确定的情形来讲，使用数组的方法就不能很好地满足要求了。
对于这种情况，结合对于C++的学习，我们是否可以通过设计一个大数的类来解决呢?
我们都知道，在C++的STL模板中提供了完善的数据结构，其中包括几种队列的实现：deque、vector、list等。经过比较我们发现，deque同时具有数组和链表的优点：它既具有像数组一样的方便性，又可以根据需要自动伸缩，更适合在两端进行插入和删除操作的情况，便于表示任意长度的大数及其中间运算结果。Deque既可以对大数很方便的执行增加或减少位数的操作，也可以很容易地定位在某个位上，重要的是它的位数不受限制。因此该类型是可以作为无位数限制大数类的基本数据结构的。