大整数基本运算的实现 正文.docVIP

摘要 目前，密码学大量被应用到生活中，而随着计算机信息安全要求的不断提高，为保证安全性，数据安全方面往往采用非常大的数作为密钥，来对数据进行分块加密，例如RSA、ECC等公钥密码算法和数字签名算法都需要建立在大整数运算的基础上，而各种编程语言所提供的各种基本数据类型中，一般整型数所能表示的最大整数只有2^32一1，远远不能满足如此大的数之间的运算要求。本文把大整数用十进制表示，B=n0*10^0+n1*10^1+...+nj*10j+...，只要用整型数组把{n0 n1 n2 ...nj..}一一对应保存就能达到目的，本文的大整数基本运算加、减、乘、除都是采用模拟笔算的方法，易读。 关键字：大整数、数组、笔算 目录 1、绪论 1.1背景 随着计算机和网络的发展，计算机已经深入到了生活中的各个行业中了，在计算机给我们带来方便和提高工作效率的同时也带来越来越多的问题，其中信息安全问题最为突出，而随着计算机信息安全要求的不断提高，计算机必威体育官网网址系统变得越来越重要，而密码学的应用迅速扩大到社会的很多领域当中，RSA、ECC等公钥密码算法和数字签名算法等得到了了快速的发展，但这些算法的实现都是建立在大整数运算的基础上，大整数储存问题以及耗时的大整数基本运算都带来巨大的困难和挑战，如何解决这些问题是公钥密码领域普遍关注的热点。 1.2 本文研究内容 本文采用数组的思想，把大整数用十进制表示，用数组储存对应的系数，如B=n[0]*10^0+n[1]*10^1+...+n[j]*10^j+...，只要用整型数组把{n[0] n[1] n[2] ...n[j]...}一一对应保存就能达到目的，本文的大整数基本运算加、减、乘、除都是采用模拟笔算的方法，易读。 2、大整数的结构分析与存储 2.1 大整数的结构分析 大整数的存储结构有链式存储方式和顺序存储方式，一是采用链表作为存储结构，这种方式可以适应不定长度的大数，这种方式的存储空间包括整数表示部分和链表指针部分，其空间利用率不高，而且其存储空间是离散的，所以随机访问效率也不高，而且频繁的堆操作和引用操作势必大量增加开销，不利于编译器优化速度；另外，根据内存管理方式的不同，顺序存储方式可以再分为静态存储方式和动态存储方式。静态存储方式数组的大小是事先已经知道的，适合知道大小的整数运算。而因其数组长度是固定不变的，在运算的时候容易造成溢出。这也是本文的很大缺点，因为大整数比较大，若每次要输入多少位都数过再动态分配内存比较麻烦。 2.2 大整数存储 数的表示必须有一个基数，b进制表示的基数为b，例如基数为b的大整数x表示为x=x[O]*b^0+x[1]*b^1 +x[2]b^3 +? ，其中O≤ x[i] b，本文我们采用b=10，即十进制来表示，数组的每个元素保存大整数的一个十进制数字，容易理解，虽然效率明显不高，也需要比较多的存储空间，但容易理解。 3.大整数的运算 3.1 两个大整数的比较 两个正整数比较，若两个的length不等时，length大的该数大，若两个的length相等，则从x[1ength]一直比到出现对应数组元素不等，大的该数大，当比到x[O]都相等，则两个数相等。代码如下： int compare(int *numa,int *numb,int lenght_a,int lenght_b) //比较大整//数的大小 大于返回1 小于返回-1 等于返回0 { int i; if (lenght_alenght_b) return 1; //比较numa,numb的位数确定返回值 else if (lenght_alenght_b) return -1; else //位数相等时的比较 { i=lenght_a; while (numa[i]==numb[i]) //逐位比较 i--; if (i==0) return 0; else if (numa[i]numb[i]) return 1; else return -1; } } 3.2 加法运算 由于大整数有正负性，所以两个数相加有四种情况a+b,a+(-b),(-a)+b,(-a)+(