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

1、清华大学课程设计报告课程： 密码学与信息安全 设计题目：大数的 Euclid 算法实现 姓名： 程 超 学号： 3080103993 班级: 信研 22 班 一、 设计任务以扩展欧式定理为基础，编程实现：输入两个数，判断：是否互素分别算出：GCD；二者的互模逆。考虑负数和大数 (如 256 位）等情况。欧式定理可被应用于信息安全领域，实现 RSA 加密。二、 算法设计及实现设计要求实现求两个整数最大公约数或者互模逆，并且要考虑负数和大数的情况。我们选择扩展 Euclid 算法来实现设计，扩展 Euclid 算法在 Euclid算法基础上可以实现求两个互素整数的互模逆。扩展 Euclid 算法实

2、现过程只涉及整数的加、减、乘、除运算，因此我们在设计大数运算时只需考虑大数运算的加、减、乘、除运算。1、 扩展 Euclid 算法已知方程 ，a， b，c 为已知常数，x，y 为整数，如何求得一+=组 x， y 使得上述方程成立。若 a，b 存在公约数 gcd(a,b)，则只有 c 为 gcd(a,b) 整数 k 倍时，该式才有解。方程可以写成：，其中1+1=gcd(,) 1=， 2=此时则转化为求方程 的解。+=(,)如果 b 为零，则 gcd(a,b)=a，那么 x=1,y=0 为一组解；如果 b 不为零，根据 Euclid 定理，有1+1=(,)=(,%)=2+(%)2=2+(/)2有

3、。1=2， 1=2()2根据递推关系计算下去，直至 n 次使得 b=0，则有 xn=1,yn=0，此时 a便为 a，b 最大公约数。若 a，b 互素，则有 ，其中 ，可以看出此1+1=1 1=， 2=时的 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.

4、 (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 互素时，即存在 ，+=1a0，则有 ，即 a 模 b 的逆为 b-m；a*(-m)+b*n=1a0,b9)adresult-=10;inc=1;elseinc=0;resulti=adresult+0;/由于被加数

5、加数，如果运算结束，进位/借位标志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-)da

6、ta2i=data2i-1;data20=-;data2len2+1=0;3)、大数乘法char* MulNum(char *add1,char* add2)大数乘法运算算法实现过程如下：(1)、将 A，B 按位对齐；(2)、逐位相乘累加；(3)、对结果进行进位调整。做乘法运算前需对数据进行去符号位、确定结果符号等操作。对计算结果，要进行去零、添加符号等操作。for (i=0;i=0;i-) /if (si=10) si-1+=si/10; si%=10;4)、大数除法char* DivNum(char *add1,char* add2)大数乘法运算算法实现过程如下：(1)、从高位开始，对位做

7、减法，并完成借位；(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 时输

8、出显示：输入大数若干经验算准确无误。上述实验结果表明，本设计实现了预期目标。4、设计总结本次设计任务重点在于扩展 Euclid 算法及大数算法的实现。Euclid 算法主要是利用递推方法实现，难点是将其扩展到负数领域。通过推导可以可以发现，可通过其绝对值计算实现。大数算法实现是本设计重难点，是设计主要工作所在。首先大数存储是通过字符串实现的，需要将字符串所表示的数学意义自行读取出来，如正负，大小，高/低位数等。对字符串进行加减乘除等运算操作，需要自行提供其运算的方法函数，在函数里面实现对其的运算，如加/减法的对应位元操作及进位，乘法的对应位元叠加及进位，除法的辗转相减等。在代码编辑过程中，注意指针的使用，如指针需要预先分配相应的内存空间，在结束时需要释放相应的内存空间，指针需初始化后才能进行操作等。在代码调试过程中，发现 char*指针在被敞亮或者指针赋值后，不能被修改。需要用 malloc 函数分配内存空间后，再用 memcpy 函数赋值才可被修改；或者用 char形式表示字符串，然后再初始化。因为直接赋值字符串常量或者指针，所赋值仍在常量区间，不能被访问。本次设计很好地完成了任务所要求的全部功能，但仍有可以改进的地方，比如界面设计，大数算法的复杂度设计等。