大数计算的算法探讨及其在椭圆曲线密码体制中的应用

摘  要

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

[关键词]  椭圆曲线加密体制  大数计算  算法

目录

摘  要 1

ABSTRACT 1

一、引言 2

二、讨论超大数、超高精度数的表示方法和存储技术 3

（一）超大数的存储技术 3

1、通过数制转换，利用数组实现存储 3

2、在VC++中使用无符号长整型队列实现大数的无位数限制 4

（二）超高精度数的存储技术和误差分析 6

三、大数计算算法的讨论 6

（一）大数的一些简单计算的算法 7

1、大数加法运算的实现算法 7

2、大数减法运算实现算法 7

3、大数乘法运算实现算法 7

4、大数除法运算的算法实现 8

5、大数取模运算的算法实现 8

（二）大数模乘算法 9

1、加法型算法 9

2、估商型算法 10

3、Montgomery型算法 11

4、小结 12

（三）大数分解问题 12

1、试除法 13

2、费马方法 13

3、勒让德方法 14

4、连分数法 14

四、大数计算在椭圆曲线密码体制中的应用 15

（一）椭圆曲线密码体制 15

1、椭圆曲线密码算法的特点： 15

2、椭圆曲线密码体制中的有关计算 15

（二）大数计算在椭圆曲线密码体制中的应用 16

1、E（Fq）中的密码体制 16

2、椭圆曲线基本协议举例 17

3、基于E（Fq）的加密/解密算法实现 18

五、量子计算机的出现与大数计算的发展 19

参考文献 20

致谢 21

附录1、大数之间进行简单运算的C源码： 21

附录2、ammd.h文件： 26