大整数基本运算实现研究报告及分析.pdf

个人资料整理仅限学习使用 课 程 设 计 课程名称应用密码学 题目名称大整数基本运算的实现研究及分析 学生学院应用数学 专业班级信息安全 081 班 学号3108008921,3108008945,3108008944 学生姓名洪亿鹏，熊邦名，伍尚鹏 指导教师李峰 2018年 12 月 19 日 个人资料整理仅限学习使用 广东工业大学课程设计任务书 题目名称 大整数基本运算的实现研究及分析 学生学院 应用数学学院 专业班级 08 级信息安全 , 写出课程设计说明书。 四、课程设计进程安排 序 号 设计各阶段内容地点起止日期 个人资料整理仅限学习使用 1 领取课程设计任务课室2018.12.13 2 组员讨论选取课程设计题目课室2018.12.13 3 查阅相关课题的各种资料 图书馆， 宿舍2018.12.132018.12.14 4 组员直接讨论课题，并且分配各部分 任务课室2018.12.14 5 各自编写各部分代码宿舍2018.12.152018.12.17 6 汇集已写好的各部分代码，并进去测 试宿舍2018.12.18 7 代码顺利运行，运用MFC 可视化方法 为程序提供友好的用户界面宿舍2018.12.19 8 分工合作拟写课程设计报告书宿舍2018.12.19 五、应收集的资料及主要参考文献 1宋震.密码学 M. 北京：中国水利水电出版社. 2002：87-151. 2 (美Garlisle Adams Steve Lloyd 著 冯登国等译 .公开密钥基础设施概念、标准 和实施 M. 北京：人民邮电出版社 .2001：71-98. 3王永祥 . 超高精度超大数算法与程序设计M. 陕西:西安交通大学出版社 ,1990：75- 105. 4 胡向东，魏琴芳编著 .应用密码学 .北京：电子工业出版社，2006.11 5 谭浩强， C 程序设计 3 3.2 用 C+编写大整数类3 3.3 本章小结5 4 基本运算的原理和代码实现5 4.1 加法运算5 4.11 实现原理5 4.12 代码实现6 4.13数据测试结果8 4.2 减法运算8 4.21减法运算代码实现8 4.22数据测试结果10 4.3 乘法运算11 4.31乘法运算原理11 个人资料整理仅限学习使用 4.32乘法运算代码实现12 4.33数据测试结果14 4.4 除法运算14 4.41除法运算代码实现14 4.42数据测试结果16 结论 17 参考文献 17 附录 A17 个人资料整理仅限学习使用 1 绪论 1.1 大整数的概念 “大整数”一般指位数达到十几或成百上千甚至更多的整数，而更准确地说，应该 是指普通程序设计语言中的整数类型值集范围以上的整数。如标准的C的Unsigned long 型整数所能处理的整数范围最大，有效数位也最多，为4294967295(占据 32 位 中的应用前景广泛。 微观世界中的许多对象的活动可以进行数字化模拟，而且其活动变化也可以通过大整 数的运算来表示，其表达与处理就非常方便了。 1.3 大整数处理的研究现状 由于“大整数”超出了程序设计语言本身整数类型值集范围，所以它的表达、存 储、读取、处理 (各种运算 、输出等问题用一般编程方法难以解决。一般的程序设计 语言数值处理范围均有限。C+及其系列语言的数值处理的有效数位是整型4 个字节， 个人资料整理仅限学习使用 数值型可达到 8 个字节。新版的微软操作系统自带的“运算器”的处理能力非常强，但 精确数位也只能达到 32 个十进制位。因而大整数运算处理系统的研究与开发有极强的 实际意义。 由于大整数处理系统的复杂性，以及其一般用于高尖新技术领域，所以系统 化研究及其开发工作主要集中在一些国家级的计算中心、安全中心。但随着大整 数应用领域逐渐扩大及个人计算机处理能力的快速发展，这项工作已经受到越来 越多的科技工作者的关注。 1.4 本文主要研究内容 本文基于MFC应用框架，首先采用模块化的思想建立大整数运算库，利用数组存 储不大于310 位的大整数，在实现一些辅助函数后在此运算库框架上讨论并实现多精 度大整数的基本加法、减法、乘法、除法等基本算法。本文采用C+为主要语言编写 程序代码。在保证算法有足够高的效率的同时力求代码清晰易懂，函数接口简单明 了，具有可移植性和稳定性。 2大整数概述 2.1本文研究的大整数特定含义 为了系统地研究大整数的处理，本文提到的大整数处理程序中所指的大整数是指 最大位数为 310位的大整数。采用数组存储方式存储。 2.2大整数的存储 我们采用数组存储的方式存储，也可以采用字符串的方式存储，但最终还是要转化为 “数组”的方式存储，并且存储的位数不能大于310位，否则会发生溢出错误而导致大 整数处理错误。 个人资料整理仅限学习使用 2.3大整数的输入与读取 如果是从键盘输入大整数，要求连续输入正负号及全部数字，程序将实现专用处理命 令自动完成分组。 2.4 大整数的基本运算处理 本程序可以实现位数少于310位的大整数的加，减，乘，除等运算，输出 位数同样不可以大于 310位，对于负数，程序将不能处理，并且不能直接 输入。 3 大整数的类的开发 3.1如何表示一个大整数 (12345678901234567890 3.2用 C+编写大整数类 class CBigInt public: / 大数在 0x100000000进制下的长度 个人资料整理仅限学习使用 unsigned m_nLength。 / 用数组记录大数在 0x100000000进制下每一位的值 unsigned long m_ulValueBI_MAXLEN。 CBigInt(。 CBigInt(。 /* 基本操作与运算 Mov ，赋值运算，可赋值为大数或普通整数，可重载为运算符“=” Cmp ，比较运算，可重载为运算符“=”、“ !=”、“ =”、“ 。 void Mov(CBigInt& A。 CBigInt Add(CBigInt& A。 CBigInt Sub(CBigInt& A。 CBigInt Mul(CBigInt& A。 CBigInt Div(CBigInt& A。 CBigInt Add(unsigned long A。 CBigInt Sub(unsigned long A。 个人资料整理仅限学习使用 CBigInt Mul(unsigned long A。 CBigInt Div(unsigned long A。 int Cmp(CBigInt& A。 void Get(CString& str, unsigned int system=HEX。 /Get ，从字符串按 10进制或 16进制格式输入到大数 void Put(CString& str, unsigned int system=HEX。 /Put ，将大数按 10进制或16进制格式输出到字符串 CBigInt Euc(CBigInt& A。 CBigInt RsaTrans(CBigInt& A, CBigInt& B。 。 3.3本章小结 基于面向对象程序设计开发的基本思想，本章介绍了大整数“类”的结构，包括大 整数的构造，加，减，乘，除基本运算的函数模块和大整数的获取、赋值函数模块。 4基本运算的原理和代码实现 4.1 加法运算 4.11 实现原理 如何进行大整数的加法运算 个人资料整理仅限学习使用 4.12 代码实现 CBigInt CBigInt:Add(CBigInt& A / 大数相加 ,调用形式： N.Add(A, 返回值： N+A CBigInt X 。 X.Mov(*this 。 unsigned carry=0 。/进位 unsigned _int64 sum=0 。 if(X.m_nLengthX.m_nLength=A.m_nLength 。 for(unsigned i=0。i sum=A.m_ulValuei。 sum=sum+X.m_ulValuei+carry。 X.m_ulValuei=(unsigned longsum。 carry=(unsigned(sum32 。 X.m_ulValueX.m_nLength=carry。 X.m_nLength+=carry。 return X。 个人资料整理仅限学习使用 CBigInt CBigInt:Add(unsigned long A CBigInt X 。 X.Mov(*this 。 unsigned _int64 sum 。 sum=X.m_ulValue0。 sum+=A。 X.m_ulValue0=(unsigned longsum。 if(sum0xffffffff unsigned i=1。 while(X.m_ulValuei=0xffffffffX.m_ulValuei=0。i+。 X.m_ulValuei+ 。 if(m_nLength=im_nLength+。 return X。 个人资料整理仅限学习使用 4.13数据测试结果 图 4.13 4.2 减法运算 4.21减法运算代码实现 CBigInt CBigInt:Sub(CBigInt& A / 大数相减 调用形式： N.Sub(A 返回值： N-A CBigInt X 。 X.Mov(*this 。 if(X.Cmp(AX.Mov(0 。return X。 unsigned carry=0 。 unsigned _int64 num 。 unsigned i。 for(i=0。i if(m_ulValueiA.m_ulValuei|(m_ulValuei=A.m_ulValuei&&(carry=0 个人资料整理仅限学习使用 X.m_ulValuei=m_ulValuei-carry-A.m_ulValuei 。 carry=0。 else num=0x100000000+m_ulValuei。 X.m_ulValuei=(unsigned long(num-carry-A.m_ulValuei 。 carry=1。 while(X.m_ulValueX.m_nLength-1=0X.m_nLength- 。 return X。 CBigInt CBigInt:Sub(unsigned long A CBigInt X 。 X.Mov(*this 。 if(X.m_ulValue0=AX.m_ulValue0-=A。return X。 if(X.m_nLength=1X.Mov(0 。return X。 unsigned _int64 num=0x100000000+X.m_ulValue0 。 X.m_ulValue0=(unsigned long(num-A。 int i=1。 while(X.m_ulValuei=0X.m_ulValuei=0xffffffff。i+。 X.m_ulValuei- 。 if(X.m_ulValuei=0X.m_nLength- 。 return X。 个人资料整理仅限学习使用 4.22数据测试结果 图 4.22 个人资料整理仅限学习使用 4.3乘法运算 4.31乘法运算原理 个人资料整理仅限学习使用 4.32乘法运算代码实现 CBigInt CBigInt:Mul(CBigInt& A / 大数相乘调用形式： N.Mul(A 返回值： N*A if(A.m_nLength=1return Mul(A.m_ulValue0 。 CBigInt X 。 unsigned _int64 sum,mul=0,carry=0 。 unsigned i,j。 X.m_nLength=m_nLength+A.m_nLength-1。 for(i=0。i sum=carry。 carry=0。 for(j=0。j if(i-j=0&&(i-j mul=m_ulValuei-j 。 mul*=A.m_ulValuej 。 carry+=mul32。 mul=mul&0xffffffff。 sum+=mul。 carry+=sum32。 X.m_ulValuei=(unsigned longsum。 if(carryX.m_nLength+ 。X.m_ulValueX.m_nLength-1=(unsigned longcarry。 return X。 个人资料整理仅限学习使用 CBigInt CBigInt:Mul(unsigned long A CBigInt X 。 unsigned _int64 mul 。 unsigned long carry=0 。 X.Mov(*this 。 for(unsigned i=0。i mul=m_ulValuei。 mul=mul*A+carry 。 X.m_ulValuei=(unsigned longmul。 carry=(unsigned long(mul32。 if(carryX.m_nLength+ 。X.m_ulValueX.m_nLength-1=carry 。 return X。 个人资料整理仅限学习使用 4.33数据测试结果 图 4.33 4.4除法运算 4.41除法运算代码实现 CBigInt CBigInt:Div(CBigInt& A / 大数相除 调用形式： N.Div(A 返回值： N/A if(A.m_nLength=1return Div(A.m_ulValue0 。 CBigInt X,Y ,Z。 unsigned i,len 。 unsigned _int64 num,div。 Y.Mov(*this 。 while(Y.Cmp(A=0 div=Y.m_ulValueY.m_nLength-1。 num=A.m_ulValueA.m_nLength-1。 个人资料整理仅限学习使用 len=Y.m_nLength-A.m_nLength。 if(div=num&&(len=0X.Mov(X.Add(1。break。 if(div&&lenlen-。 div=(div+Y .m_ulValueY.m_nLength- 2。 div=div/(num+1 。 Z.Mov(div 。 if(len Z.m_nLength+=len。 for(i=Z.m_nLength-1 。 i=len 。 iZ.m_ulValuei=Z.m_ulValuei- len。 for(i=0。iZ.m_ulValuei=0 。 X.Mov(X.Add(Z 。 Y.Mov(Y.Sub(A.Mul(Z 。 return X。 CBigInt CBigInt:Div(unsigned long A CBigInt X 。 X.Mov(*this 。 if(X.m_nLength=1X.m_ulValue0=X.m_ulValue0/A。return X。 unsigned _int64 div,mul。 unsigned long carry=0 。 for(int i=X.m_nLength-1 。i=0。i div=carry。 个人资料整理仅限学习使用 div=(div+X.m_ulValuei 。 X.m_ulValuei=(unsigned long(div/A 。 mul=(div/A*A 。 carry=(unsigned long(div-mul。 if(X.m_ulValueX.m_nLength-1=0X.m_nLength- 。 return X。 4.42数据测试结果 图 4.42 个人资料整理仅限学习使用 结论 一个星期的课程设计结束，通过我们组成员的合作，终于完成了本次课程设计。 中间，我们也遇到了很多的问题，例如MFC 的应用，数据存储的方式，算法的实现 等。通过我们的共同努力，看了不同的资料。总算找到了解决的方案。 这次课程设计，我们组员之间分工明确，都很出色的做好了自己的工作。其中， 洪亿鹏同学完成了大数算法的乘法部分，并且领导全体组员一起完成了除法部分的算 法，在 MFC 的实现过程中，成为核心角色，而在最后的论文编写中，也给出了也重要 的指示，带领大家完成任务；熊邦名同学完成了大数算法的加法部分，协调组员之间 的关系，大家团结一致完成认为，并且在论文编写中做出了比较大的贡献；伍尚鹏同 学完成了大数算法的减法部分；发扬不怕苦不怕累的精神，拼搏精神感染了大家，为 这次课程设计的圆满完成作出了很大的贡献，同时论文编写部分也是以伍尚鹏同学为 核心完成的，大家通力合作。 本文讨论的主要是大数运算中的基本算法，而要实现一个比较好的大数运算库则 除此之外还有很多工作要做。大数算法是一个很大的考验，既要有不错的软件编码知 识又要对硬件细节有足够的了解，还要求会根据情况自己推导数学公式，优化算法， 同时也需要很强的耐心、足够的细心和大量的时间。 参考文献 4宋震.密码学 M. 北京：中国水利水电出版社.2002：87-151. 5 (美Garlisle Adams Steve Lloyd 著 冯登国等译 .公开密钥基础设施概念、标准 和实施 M. 北京：人民邮电出版社 .2001：71-98. 6王永祥 . 超高精度超大数算法与程序设计M. 陕西:西安交通大学出版社 ,1990：75- 105. 4 胡向东，魏琴芳编著 .应用密码学 .北京：电子工业出版社，2006.11 5 谭浩强， C 程序设计 返回值： N 被赋值为相应大数 sys暂时只能为 10或 16 */ void CBigInt:Get(CString& str, unsigned int system int len=str.GetLength(,k。 Mov(0。 for(int i=0 。i Mov(Mul(system。 if(stri='0'&&(strik=stri-48。 else if(stri='A'&&(strik=stri-55。 else if(stri='a'&&(strik=stri-87。 else k=0 。 Mov(Add(k 。 个人资料整理仅限学习使用 /* 将大数按 10进制或 16进制格式输出为字符串 调用格式： N.Put(str,sys 返回值：无，参数str被赋值为 N 的 sys进制字符串 sys暂时只能为 10或 16 */ void CBigInt:Put(CString& str, unsigned int system if(m_nLength=1&&(m_ulValue0=0str=“0“。return。 str=“。 CString t=“0123456789ABCDEF“。 int a。 char ch 。 CBigInt X 。 X.Mov(*this 。 while(X.m_ulValueX.m_nLength-10 a=X.Mod(system。 ch=ta。 str.Insert(0,ch 。 X.Mov(X.Div(system 。 /* 大数赋值 调用方式： N.Mov(A 返回值：无， N 被赋值为 A */ 个人资料整理仅限学习使用 void CBigInt:Mov(CBigInt& A m_nLength=A.m_nLength。 for(int i=0 。im_ulValuei=A.m_ulValuei 。 void CBigInt:Mov(unsigned _int64 A if(A0xffffffff m_nLength=2。 m_ulValue1=(unsigned long(A32。 m_ulValue0=(unsigned longA。 else m_nLength=1。 m_ulValue0=(unsigned longA。 for(int i=m_nLength。im_ulValuei=0 。