合工大分数线-肥水之战

课 程 设 计

课程名称 应用密码学
题目名称
大整数基本运算的实现研究及分析

学生学院 应用数学
专业班级 信息安全081班
学 号
3108008921,3108008945,3108008944

学生姓名
洪亿鹏，熊邦名，伍尚鹏

指导教师 李峰

2010 年 12 月 19 日

I

广东工业大学课程设计任务书

题目名称
学生学院
专业班级
姓 名
学 号
大整数基本运算的实现研究及分析
应用数学学院
08级信息安全（1）班
洪亿鹏，熊邦名，伍尚鹏
3108008921,3108008945,3108008944

一、课程设计的内容

本文介绍了一种这样的大整数在程序设计语言中的表示 的方法，并对这种方法表示
的大整数的基本运算进行了分析，给出了实现算法，并提供良好的用户界面。
二、课程设计的要求与数据
1.
实现大整数的基本运算；

2.提供友好的用户界面；

三、课程设计应完成的工作
1、查阅相关资料，了解关于大整数基本运算的实现研究及分析；
2、在Visual C++6.0进行编程，设计出合乎要求的程序；
3、测试程序的正确性和稳定性；
4、根据<<广东工业大学课程设计管理规定>>, 写出课程设计说明书。

四、课程设计进程安排

序
号
设计各阶段内容 地点 起止日期

II

1
2
领取课程设计任务
组员讨论选取课程设计题目
课室
课室
图书馆，宿
2010.12.13
2010.12.13
3 查阅相关课题的各种资料
组员直接讨论课题，并且分配各部分任
舍 2010.12.13~2010.12.14
4
5
6
务
各自编写各部分代码
汇集已写好的各部分代码，并进去测试
代码顺利运行，运用MFC可视化方法为
课室
宿舍
宿舍
2010.12.14
2010.12.15~2010.12.17
2010.12.18
7
8
程序提供友好的用户界面
分工合作拟写课程设计报告书
宿舍
宿舍
2010.12.19
2010.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程序设计（第三版）北京：清华大学出版社，2005
[6] 郑莉，C++语言程序设计（第三版）北京：清华大学出版社，2006


发出任务书日期： 年 月 日 指导教师签名：

计划完成日期： 年 月 日 基层教学单位责任人签章：

主管院长签章：

III

摘 要

随着计算机信息安全要求的不断提高，密码学被大量 应用到生活中。在现代密码学
中，安全性基于复杂数学问题的难解性假设的加密方法，往往需要进行大整 数运算，这
些大整数已经远远超过了程序设计语言所能表示的最大整数值范围。也不能使用一般的
四则运算法则进行运算。本文介绍了一种这样的大整数在程序设计语言中的表示的方
法，并对这种方法 表示的大整数的基本运算进行了分析，给出了实现算法。RSA、
ElGamal、DSA、ECC 等 公钥密码算法和数字签名算法都建立在大整数运算的基础上，
比较耗时的大整数乘法、除法、模乘、幂运 算、幂乘等运算却被上述算法大量使用，它
们的运算速度对这些算法的高效实现起着重要的作用，如何快 速实现上述几种运算是公
钥密码领域普遍关注的热点问题。

关键词：
大整数、存储、模块、数组。














IV

目 录
1 绪论 ........................................ .................................................. ....... 1

1.1

大整数的概念 ............. .................................................. .................................................. ............................. 1

1.2

大整数处理的应用价值 ................................... .................................................. ......................................... 1

1.3

大整数处理的研究现状 ....................... .................................................. .................................................. ... 1

1.4

本文主要研究内容 ............... .................................................. .................................................. ................... 2

2大整数概述 ............. .................................................. ......................... 2

2.1本文研究的大整数特定含义 .............................. .................................................. ...................................... 2

2.2

大整数的存储 ........................... .................................................. .................................................. ............... 2

2.3

大整数的输入与读取 .. .................................................. .................................................. ............................ 3

2.4

大整数的基本运算处理 ................................... .................................................. ......................................... 3

3 大整数的类的开发.................................... ....................................... 3

3.1如何表示一个大整数(123456789) ...................... .................................................. ................ 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


V

4.32
乘法运算代码实现
.................. .................................................. .................................................. ........ 12

4.33
数据测试结果
........... .................................................. .................................................. ...................... 14

4.4除法运算 ........ .................................................. .................................................. ........................................ 14

4.41
除法运算代码实现
......................... .................................................. .................................................. . 14

4.42
数据测试结果
.................. .................................................. .................................................. ............... 16

结 论 ................. .................................................. ............................ 17

参 考 文 献 .. .................................................. ................................... 17

附录 A ................................................ ................................................ 18








VI

1 绪论
1.1 大整数的概念
“大整数”一般指位数达到十几 或成百上千甚至更多的整数，而更准确地说，应该
是指普通程序设计语言中的整数类型值集范围以上的整 数。如标准的C的Unsigned long
型整数所能处理的整数范围最大，有效数位也最多，为4294967295(
（4 个字节）存贮空间，此时，大整数就是指十位以上的十进制整数了。
“大整数”运算是指“大整数”之 间的加减乘除等运算结果依然保持其数学理论上
准确和精确的结果。
)占据32 位
1.2 大整数处理的应用价值
“大整数”运算在数学验证方面有重要的应用价值。数学中 的大整数运算验证工作
如果靠手工计算完成，从时间上看几乎是不可能，而借助于计算机，由于传统编程 方法
精确度远远达不到要求，所以也无法完成。有了大整数运
算程序，这些工作才能得以进行。
大整数运算在密码学中具有实用价值。随着计算机发展，密 码运算对整数运算长度、
速度等要求越来越高，因而对大整数运算的精准精度也越来越高，高效的大整数 运算系
统不仅可用于密码学的实践教学环节，也可用于实际的密码处理工作中。
大整数运算在 微观模拟(如生物信息、基因工程、数量遗传)中的应用前景广泛。微
观世界中的许多对象的活动可以进 行数字化模拟，而且其活动变化也可以通过大整数的
运算来表示，其表达与处理就非常方便了。
1.3 大整数处理的研究现状
由于“大整数”超出了程序设计语言本身整数类型值集范围， 所以它的表达、存储、
读取、处理(各种运算)、输出等问题用一般编程方法难以解决。一般的程序设计 语言数
值处理范围均有限。C++及其系列语言的数值处理的有效数位是整型4 个字节，数值型
1

可达到8 个字节。新版的微软操作系统自带的“运算器”的处理能力非常强，但精确数
位也只能达到32 个十进制位。因而大整数运算处理系统的研究与开发有极强的实际意
义。
由于大整数处理系统的复杂性，以及其一般用于高尖新技术领域，所以系统
化研究及其开发工作主要集中在一些国家级的计算中心、安全中心。但随着大整
数应用领域逐渐扩大及个人计算机处理能力的快速发展，这项工作已经受到越来
越多的科技工作者的关注。
1.4 本文主要研究内容
本文基于MFC应用框架， 首先采用模块化的思想建立大整数运算库，利用数组存储
不大于310位的大整数，在实现一些辅助函数 后在此运算库框架上讨论并实现多精度大
整数的基本加法、减法、乘法、除法等基本算法。本文采用C+ +为主要语言编写程序代
码。在保证算法有足够高的效率的同时力求代码清晰易懂，函数接口简单明了， 具有可
移植性和稳定性。

2大整数概述
2.1本文研究的大整数特定含义
为了系统地研究大整数的处理，本文提到的大整数处理程序 中所指的大整数是指最
大位数为310位的大整数。采用数组存储方式存储。
2.2 大整数的存储

我们采用数组存储的方式存储，也可以采用字符串的方式存储，但最终还是 要转化为
“数组”的方式存储，并且存储的位数不能大于310位，否则会发生溢出错误而导致大
整数处理错误。
2

2.3 大整数的输入与读取

如果是从键盘输入大整数，要求连续输入正负号及全部数字，程序将实现专用处理
命令自动完成分组。
2.4 大整数的基本运算处理

本程序可以实现位数少于310位的大整数的加 ，减，乘，除等运算，输出
位数同样不可以大于310位，对于负数，程序将不能处理，并且不能直接输
入。

3 大整数的类的开发
3.1如何表示一个大整数(123456789)

3.2用C++编写大整数类
class CBigInt
{
public:
大数在0x100000000进制下的长度
3

unsigned m_nLength;
用数组记录大数在0x100000000进制下每一位的值
unsigned long m_ulValue[BI_MAXLEN];
CBigInt();
~CBigInt();
*
基本操作与运算
Mov，赋值运算，可赋值为大数或普通整数，可重载为运算符“=”
Cmp，比较运算，可重载为运算符“==”、“!=”、“>=”、“<=”等
Add，加 ，求大数与大数或大数与普通整数的和，可重载为运算符“+”
Sub，减，求大数与大数或大数与普通 整数的差，可重载为运算符“-”
Mul，乘，求大数与大数或大数与普通整数的积，可重载为运算符“ *”
Div，除，求大数与大数或大数与普通整数的商，可重载为运算符“”
*
void Mov(unsigned __int64 A);
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);
4

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 实现原理
如何进行大整数的加法运算
5

4.12 代码实现
CBigInt CBigInt::Add(CBigInt& A)
{大数相加,调用形式：(A), 返回值：N+A
CBigInt X;
(*this);
unsigned carry=0;进位
unsigned __int64 sum=0;
if(X.m_nLength for(unsigned i=0;i {
sum=A.m_ulValue[i];
sum=sum+X.m_ulValue[i]+carry;
X.m_ulValue[i]=(unsigned long)sum;
carry=(unsigned)(sum>>32);
}
X.m_ulValue[X.m_nLength]=carry;
X.m_nLength+=carry;
return X;
}

6

CBigInt CBigInt::Add(unsigned long A)
{
CBigInt X;
(*this);
unsigned __int64 sum;
sum=X.m_ulValue[0];
sum+=A;
X.m_ulValue[0]=(unsigned long)sum;
if(sum>0xffffffff)
{
unsigned i=1;
while(X.m_ulValue[i]==0xffffffff) {X.m_ulValue[i]=0;i++;}
X.m_ulValue[i]++;
if(m_nLength==i)m_nLength++;
}
return X;
}
7

4.13数据测试结果

图4.13
4.2 减法运算
4.21减法运算代码实现
CBigInt CBigInt::Sub(CBigInt& A)
{大数相减 调用形式：(A) 返回值：N-A
CBigInt X;
(*this);
if((A)<=0){(0);return X;}
unsigned carry=0;
unsigned __int64 num;
unsigned i;
for(i=0;i {

8

if((m_ulVal ue[i]>A.m_ulValue[i])||((m_ulValue[i]==A.m_ulValue [i])&&(carry==0)))
{
X.m_ulValue[i]=m_ulValue[i]-carry-A.m_ulValue[i];
carry=0;
}
else
{
num=0x100000000+m_ulValue[i];
X.m_ulValue[i]=(unsigned long)(num- carry-A.m_ulValue[i]);
carry=1;
}
}
while(X.m_ulValue[X.m_nLength-1]==0)X.m_nLength--;
return X;
}

CBigInt CBigInt::Sub(unsigned long A)
{
CBigInt X;
(*this);
if(X.m_ulValue[0]>=A){X.m_ulValue[0]-=A;return X;}
if(X.m_nLength==1){(0);return X;}
unsigned __int64 num=0x100000000+X.m_ulValue[0];
X.m_ulValue[0]=(unsigned long)(num-A);
int i=1;
while(X.m_ulValue[i]==0){ X.m_ulValue[i]=0xffffffff;i++;}
X.m_ulValue[i]--;
if(X.m_ulValue[i]==0)X.m_nLength--;
return X;
9

}
4.22数据测试结果

图4.22
10

4.3乘法运算
4.31乘法运算原理



11

4.32乘法运算代码实现
CBigInt CBigInt::Mul(CBigInt& A)
{大数相乘 调用形式：(A) 返回值：N*A
if(A.m_nLength==1)return Mul(A.m_ulValue[0]);
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_ulValue[i-j];
mul*=A.m_ulValue[j];
carry+=mul>>32;
mul=mul&0xffffffff;
sum+=mul;
}
}
carry+=sum>>32;
X.m_ulValue[i]=(unsigned long)sum;
}
if( carry){X.m_nLength++;X.m_ulValue[X.m_nLength-1]=(u nsigned long)carry;}
return X;
12

}

CBigInt CBigInt::Mul(unsigned long A)
{
CBigInt X;
unsigned __int64 mul;
unsigned long carry=0;
(*this);
for(unsigned i=0;i {
mul=m_ulValue[i];
mul=mul*A+carry;
X.m_ulValue[i]=(unsigned long)mul;
carry=(unsigned long)(mul>>32);
}
if(carry){X.m_nLength++;X.m_ulValue[X.m_ nLength-1]=carry;}
return X;
}
13

4.33数据测试结果

图4.33
4.4除法运算
4.41除法运算代码实现
CBigInt CBigInt::Div(CBigInt& A)
{大数相除 调用形式：(A) 返回值：NA
if(A.m_nLength==1)return Div(A.m_ulValue[0]);
CBigInt X,Y,Z;
unsigned i,len;
unsigned __int64 num,div;
(*this);
while((A)>=0)
{
div=Y.m_ulValue[Y.m_nLength-1];
num=A.m_ulValue[A.m_nLength-1];
14

len=Y.m_nLength-A.m_nLength;
if((div==num)&&(len==0)){((1));break;}
if((d iv<=num)&&len){len--;div=(div<<32)+Y.m_ulValue[Y.m _nLength-2];}
div=div(num+1);
(div);
if(len)
{
Z.m_nLength+=len;
for(i=Z.m_nLength-1;i>=len;i--)Z.m_ulValue[ i]=Z.m_ulValue[i-len];
for(i=0;i }
((Z));
(((Z)));
}
return X;
}

CBigInt CBigInt::Div(unsigned long A)
{
CBigInt X;
(*this);
if(X.m_nLength ==1){X.m_ulValue[0]=X.m_ulValue[0]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<<32)+X.m_ulValue[i];
X.m_ulValue[i]=(unsigned long)(divA);
15

mul=(divA)*A;
carry=(unsigned long)(div-mul);
}
if(X.m_ulValue[X.m_nLength-1]==0)X.m_nLength--;
return X;
}

4.42数据测试结果
图4.42





16

结 论
一个星期的课程设计结束，通过我们组成员的合作，终于完成了本 次课程设计。中
间，我们也遇到了很多的问题，例如MFC的应用，数据存储的方式，算法的实现等。< br>通过我们的共同努力，看了不同的资料。总算找到了解决的方案。
这次课程设计，我们组员之间 分工明确，都很出色的做好了自己的工作。其中，洪
亿鹏同学完成了大数算法的乘法部分，并且领导全体 组员一起完成了除法部分的算法，
在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程序设计（第三版）北京：清华大学出版社，2005
[6] 郑莉，C++语言程序设计（第三版）北京：清华大学出版社，2006

17

附录 A
#ifndef BI_MAXLEN
#define BI_MAXLEN 35
#define DEC 10
#define HEX 16

********************** ************************************************** ***
从字符串按10进制或16进制格式输入到大数
调用格式：(str,sys)
返回值：N被赋值为相应大数
sys暂时只能为10或16
********** ************************************************** ***************
void CBigInt::Get(CString& str, unsigned int system)
{
int len=gth(),k;
Mov(0);
for(int i=0;i {
Mov(Mul(system));
if((str[i]>='0')&&(str[i]<='9'))k=str[i]-48;
else if((str[i]>='A')&&(str[i]<='F'))k=str[i]-55;
else if((str[i]>='a')&&(str[i]<='f'))k=str[i]-87;
else k=0;
Mov(Add(k));
}
}
18

*************************** ************************************************
将大数按10进制或16进制格式输出为字符串
调用格式：(str,sys)
返回值：无，参数str被赋值为N的sys进制字符串
sys暂时只能为10或16 ************************************************ ***************************
void CBigInt::Put(CString& str, unsigned int system)
{
if((m_nLength==1)&&(m_ulValue[0]==0)){str=
str=
CString t=
int a;
char ch;
CBigInt X;
(*this);
while(X.m_ulValue[X.m_nLength-1]>0)
{
a=(system);
ch=t[a];
(0,ch);
((system));
}
} ************************************************ ***************************
大数赋值
调用方式：(A)
返回值：无，N被赋值为A
***************************** **********************************************
19

void CBigInt::Mov(CBigInt& A)
{
m_nLength=A.m_nLength;
for(int i=0;i}

void CBigInt::Mov(unsigned __int64 A)
{
if(A>0xffffffff)
{
m_nLength=2;
m_ulValue[1]=(unsigned long)(A>>32);
m_ulValue[0]=(unsigned long)A;
}
else
{
m_nLength=1;
m_ulValue[0]=(unsigned long)A;
}
for(int i=m_nLength;i}
20