大数的扩展Euclid算法实现.doc

清华大学课程设计报告课程： 密码学与信息安全 设计题目：大数的Euclid算法实现 姓名： 程 超 学号： 3080103993 班级: 信研22班 一、 设计任务以扩展欧式定理为基础，编程实现：输入两个数，判断：是否互素分别算出：GCD；二者的互模逆。考虑负数和大数(如256位）等情况。欧式定理可被应用于信息安全领域，实现RSA加密。二、 算法设计及实现设计要求实现求两个整数最大公约数或者互模逆，并且要考虑负数和大数的情况。我们选择扩展Euclid算法来实现设计，扩展Euclid算法在Euclid算法基础上可以实现求两个互素整数的互模逆。扩展Euclid算法实现过程只涉及整数的加、减、乘、除运算，因此我们在设计大数运算时只需考虑大数运算的加、减、乘、除运算。1、 扩展Euclid算法已知方程ax+by=c，a，b，c为已知常数，x，y为整数，如何求得一组x，y使得上述方程成立。若a，b存在公约数gcd(a,b)，则只有c为gcd(a,b) 整数k倍时，该式才有解。方程可以写成： ax1+by1=gcda,b，其中x1=xk，x2=yk此时则转化为求方程ax+by=gcd(a,b)的解。如果b为零，则gcd(a,b)=a，那么x=1,y=0为一组解；如果b不为零，根据Euclid定理，有ax1+by1=gcd(a,b)=gcd(b,a%b)=bx2+(a%b)y2=bx2+(a-(a/b)*b)y2有x1=y2，y1=x2-aby2。根据递推关系计算下去，直至n次使得b=0，则有xn=1,yn=0，此时a便为a，b最大公约数。若a，b互素，则有ax1+by1=1，其中x1=xc，x2=yc，可以看出此时的x1是a模b的逆元。根据上述分析，扩展Euclid实现过程如下：1. (X1,X2,X3) (1,0,b), (Y1,Y2,Y3) (0,1,a)2. if Y3 = 0 then return X3=gcd(a,b), no inverse3. if Y3 = 1 then return Y3=gcd(a,b), Y2=a-1mod b4. Q =(X3/Y3)的整数部分5. (T1,T2,T3) (X1-QY1, X2-QY2, X3-QY3)6. (X1,X2,X3) (Y1,Y2,Y3)7. (Y1,Y2,Y3) (T1,T2,T3)8. goto 2下面考虑a，b为负数的情况，并且令d=abs(a),f=abs(b),当d,f存在公约数时，则gcd(a,b)=gcd(d,f),所以可以直接用d,f代替a,b进行计算。当d,f互素时，即存在dm+fn=1 ，a0，则有a*(-m)+b*n=1，即a模b的逆为b-m；a0,b0,b0,则有a*m+b*(-n)=1，即a模b的逆为m。根据上述分析，可知在a,b有负数的情况下，其最大公约数与模逆可由求其绝对值的最大公约数与模逆得到。根据上述分析可得扩展Euclid算法代码实现过程如下： char *op1,*op2; if(*s1=-) op1=s1+1; else op1=s1; if(*s2=-) op2=s2+1; else op2=s2; char *X1,*X2,*X3,*Y1,*Y2,*Y3,*Q; char *T1,*T2,*T3; X1=1;X2=0;X3=op2; Y1=0;Y2=1;Y3=op1; while(!IsEqual(Y3,0)&!IsEqual(Y3,1) Q=ClassInstance.DivNum(X3,Y3); T1=ClassInstance.SubNum(X1,ClassInstance.MulNum(Q,Y1); T2=ClassInstance.SubNum(X2,ClassInstance.MulNum(Q,Y2); T3=ClassInstance.SubNum(X3,ClassInstance.MulNum(Q,Y3); X1=Y1;X2=Y2;X3=Y3; Y1=T1;Y2=T2;Y3=T3; if(*Y2=-) Y2=ClassInstance.AddNum(op2,Y2); char *result; result=(char*)malloc(2*sizeof(char)*MAX); if(IsEqual(Y3,0) *result=Y3;*(result+1)=X3; if(IsEqual(Y3,1) *result=Y3; if(*s1=-) *(result+1)=ClassInstance.SubNum(op2,Y2); else *(result+1)=Y2; 2、大数运算算法 设计任务中要求要考虑大数的情况，因此需要设计一套关于大数的运算类BigNumOperation，要包括加、减、乘、除四类运算，分别为类方法Add Num(),SubNum(),MulNum()和DivNum()。由于大数超过普通数据类型的存储范围，因此将大数存储为一个字符串，相应运算都是针对字符串进行操作。 大数运算类要求能处理正数、负数两种情况，设待处理的两个数为A，B，均存储为char*类型数据。1)、大数加法char* AddNum(char *add1,char* add2) 加法采用按位相加的算法，实现过程如下： (1)、将A，B按位对齐； (2)、从低位开始逐位相加； (3)、对结果进行位调整(进位)。/对齐两个操作数for(i=strlen(add2);ilen;i+)add2i=0; add2len=0; /按位元算for(i=0;ilen;i+)/和（被加数）（/）（加数进位）adresult=(add1i-0)+(add2i-0+inc)*flag;if(adresult9)adresult-=10;inc=1;elseinc=0;resulti=adresult+0;/由于被加数加数，如果运算结束，进位/借位标志1，则可确定是加法进位标志，直接进位if(inc=1)resulti=1;len+; 由于A，B可能为负数，所以在此之前，需要进行去符号位、确定结果符号等预处理过程。由于字符串从头到尾依次代表数据的高位到低位，为了便于处理，将去符号的数据逆转，并在求得结果后再次逆转，并确定是否添加负号。2)、大数减法char* SubNum(char *add1,char* add2) 减法采用调用加法处理的方法，在调用之前需将数据B进行换号处理。若B为负数，则去掉头部负号；若为正数，则在头部插入负号。if(*data2=-) for(int i=0;i0;i-)data2i=data2i-1;data20=-;data2len2+1=0;3)、大数乘法char* MulNum(char *add1,char* add2) 大数乘法运算算法实现过程如下：(1)、将A，B按位对齐；(2)、逐位相乘累加；(3)、对结果进行进位调整。做乘法运算前需对数据进行去符号位、确定结果符号等操作。对计算结果，要进行去零、添加符号等操作。for (i=0;ica+cb;i+) si=0; / 每个元素赋初值0 for (i=0;ica;i+) for (j=0;j=0;i-) /if (si=10) si-1+=si/10; si%=10;4)、大数除法char* DivNum(char *add1,char* add2)大数乘法运算算法实现过程如下： (1)、从高位开始，对位做减法，并完成借位； (2)、高位开始逐位计算商； (3)、整理商，产生余数。做除法运算前需对数据进行去符号位、确定结果符号等操作。对计算结果，要进行添加符号等操作。/*首先把余数部分设置为和DIV2等长度的DIV1*/for(i=len2-1;i=0)BigIntSub(remain,p2);/*余数和DIV2相减*/k+;AddDivMub(remain,p1+i);/*添加余数*/resultm+=k+0;3、设计功能验证输入21与50，-21与50,21与-50，-21与-50时输出显示：输入22与44，-22与44,22与-44，-22与-44时输出显示：输入大数若干经验算准确无误。上述实验结果表明，本设计实现了预期目标。4、设计总结本次设计任务重点在于扩展Euclid算法及大数算法的实现。Euclid算法主要是利用递推方法实现，难点是将其扩展到负数领域。通过推导可以可以发现，可通过其绝对值计算实现。大数算法实现是本设计重难点，是设计主要工作所在。首先大数存储是通过字符串实现的，需要将字符串所表示的数学意义自行读取出来，如正负，大小，高/低位数等。对字符串进行加减乘除等运算操作，需要自行提供其运算的方法函数，在函数里面实现对其的运算，如加/减法的对应位元操作及进位，乘法的对应位元叠加及进位，除法的辗转相减等。在代码编辑过程中，注意指针的使用，如指针需要预先分配相应的内存空间，在结束时需要释放相应的内存空间