RSA算法设计与实现

1、实用文案武汉大学密码学课程设计报告题目名称： RSA加密解密的设计与实现姓名：学号：专业：-、设计原理（算法工作原理）RSA原理：RSA密钥的选取和加解密过程都非常简洁，在算法上主要要实现四个问题：1、如何处理大数运算2、如何求解同余方程XY % M = 13、如何快速进行模幕运算4、如何获取大素数（一）大数存储RSA依赖大数运算，目前主流 RSA算法都建立在1024位的大数运算之 上。而大多数的编译器只能支持到 64位的整数运算，即我们在运算中所使用的 整数必须小于等于64位，即：Oxffffffffffffffff，也就是18446744073709551615，这远远达不到RSA的需要，

2、于是需要专门建立大数运算库来解决这一问题。标准一个有效的改进方法是将大数表示为一个 n进制数组，对于目前的32位 系统而言n可以取值为2的32次方，即0x100000000，假如将一个二进制 为1024位的大数转化成0x10000000进制，就变成了 32位，而每一位的取值 范围不再是二进制的0 1或十进制的0 9，而是0-0xffffffff ，我们正好可以 用一个32位的DWORD(如：无符号长整数，unsigned long ) 类型来表示该值。所以1024位的大数就变成一个含有32个元素的DWORD数组，而针 对DWORD数组进行各种运算所需的循环规模至多32次而已。而且0x10000

3、0000 进制与二进制，对于计算机来说，几乎是一回事，转换非常容易。例如：大数 18446744073709551615 ，等于 0xffffffff ffffffff，就相当于十进制的99 :有两位，每位都是 0xffffffff。而18446744073709551616 等于 0x00000001 ； 00000000 00000000 ，就相当于十进制的100 :有三位，第一 位是1，其它两位都是0，如此等等。在实际应用中，“数字数组”的排列顺 序采用低位在前高位在后的方式，这样，大数A就可以方便地用数学表达式来表示其值：A=Sumi=0 to n(A*r*i), r=0x100000

4、000 , 0<=A<r 其中 Sum 表示求和，A表示用以记录A的数组的第i个元素，*表示乘方。任何整数运算 最终都能分解成数字与数字之间的运算，在0x100000000 进制下其“数字”最大达到0xffffffff，其数字与数字之间的运算，结果也必然超出了目前32位系统的字长。在VC+中，存在一个_int64类型可以处理64位的整数，所以不 用担心这一问题。(二)加减乘除设有大数A、B和C,其中A>=B :A=Sumi=0 to p(A*r*i)B=Sumi=O to q(B*r*i)C=Sumi=0 to n(C*r*i)r=0x100000000, 0<=A,B

5、,C<r , p>=q则当C=A+B、C=A-B、C=A*B时，我们都可以通过计算出 C来获得C:C=A+B , 显然C不总是等于A+B，因为A+B可能>0xffffffff ，而C必须v=0xffffffff ， 这时就需要进位，当然在计算Ci-1时也可能产生了进位，所以计算C时还要加 上上次的进位值。如果用一个64位变量result来记录和，另一个32位变量carry 来记录进位，则有：carry=0FOR i FROM 0 TO presult=A+B+carryC=result%0x100000000carry=result/0x100000000IF carry=0

6、 n=pELSE n=p+1C=A-B，同理C不总是等于A-B，因为A-B可能<0 ,而C必须>=0，这时就 需要借位，同样在计算Ci-1时也可能产生了借位，所以计算C时还要减去上次 的借位值：carry=0FOR i FROM 0 TO pIF A-B-carry>=0C=A-B-carrycarry=0ELSEC=0x100000000+A-B-carrycarry=1n=pWHILE C n=0 n=n-1C=A*B，首先我们需要观察日常做乘法所用的“竖式计算”过程:A3 A2 A1 A0* B2 B1 B0=A3B0 A2B0 A1B0 A0B0+ A3B1 A2B1

7、 A1B1 A0B1+ A3B2 A2B2 A1B2 A0B2=C5 C4 C3 C2 C1 C0可以归纳出：C=Sumj=0 to q(Ai-j*Bj) ，其中i-j必须=0且=p。当然这一结论没有考虑进位，虽然计算 Ai-j*Bj和Sum的时候都可能发生进位，但显然这两种原因产生的进位可以累加成一个进位值。最终可用如下算法完成乘法：n=p+q-1carry=0For i FROM 0 TO nresult=carryFor j FROM 0 TO qIF 0<=i-jv=p result=result+Ai-j*BjC=result%0x100000000carry=result/0

8、x100000000IF carry!=0n=n+1Cn=carry对于C=A/B，由于无法将B对A “试商”，我们只能转换成 Bq对Ap的试 商来得到一个近似值，所以无法直接通过计算 C来获得C,只能一步步逼近Co 由于：B*(Ap/Bq-1)*0x100000000*(p-q)<C，令：X=0，重复 A=A-X*B ,X=X+(Ap/Bq-1)*0x100000000*(p-q) ，直到 A<B 贝U: X=A/B，且此时的 A=A%B，注意对于任意大数 A*0x100000000*k ，都等价于将A的数组中的 各元素左移k位，不必计算；同样，A/0x100000000*k 则

9、等价于右移。(三) 欧几里得方程在RSA算法中，往往要在已知A、N的情况下，求B，使得(A*B)%N=1 。 即相当于求解B、M都是未知数的二元一次不定方程A*B-N*M=1的最小整数解。而针对不定方程ax-by=c的最小整数解，有著名的欧几里德算法，即辗转 相除法。事实上二元一次不定方程有整数解的充要条件是c为a、b的最大公约数。即当c=1时，a、b必须互质。而在RSA算法里由于公钥d为素数，素数 与任何正整数互质，所以可以通过欧几里德方程来求解私钥e。欧几里德算法是一种递归算法，比较容易理解:例如：11x-49y=1，求x（a）11 x - 49 y :=1 49%11=5 ->（b

10、）11 x - 5 y =1 11%5 =1 ->（c）x - 5 y = 1令y=0代入（c）得x=1令x=1代入（b）得y=2令y=2代入（a）得x=9同理可使用递归算法求得任意ax-by=1 （a、b互质）的解。实际上通过分析归纳将递归算法转换成非递归算法就变成了大衍求一术：x=0,y=1WHILE a!=0i=yy=x-y*a/bx=ii=aa=b%ab=iIF x<0 x=x+bRETURNx（四）模幕运算模幕运算是RSA的核心算法，最直接地决定了 RSA算法的性能。针对快 速模幕运算这一课题，西方现代数学家提出了大量的解决方案，通常都是先将幕模运算转化为乘模运算。例如求

11、D=C*15 % N，由于：a*b % n = (a % n)*(b % n) % n，所以：C1 =C*C % N =C*2 % NC2 =C1*C % N =C*3 % NC3 =C2*C2 % N =C*6 % NC4 =C3*C % N =C*7 % NC5 =C4*C4 % N =C*14 % NC6 =C5*C % N =C*15 % N即：对于E=15的幕模运算可分解为6个乘模运算，归纳分析以上方法可 以发现对于任意E,都可采用以下算法计算 D=C*E % N :D=1WHILE E>=0IF E%2=0C=C*C % NE=E/2ELSED=D*C % NE=E-1RET

12、URN D继续分析会发现，要知道E何时能整除2，并不需要反复进行减一或除二 的操作，只需验证E的二进制各位是0还是1就可以了，从左至右或从右至左 验证都可以，从左至右会更简洁，设 E=Sumi=0 to n(E*2*i)，0<=E<=1，则：D=1FOR i=n TO 0D=D*D % NIF E=1 D=D*C % NRETURN D这样，模幕运算就转化成了一系列的模乘运算。(五) 蒙哥马利模乘由于RSA的核心算法是模幕运算，模幕运算又相当于模乘运算的循环，要 提高RSA算法的效率，首要问题在于提高模乘运算的效率。不难发现，模乘过 程中复杂度最高的环节是求模运算，因为一次除法实际

13、上包含了多次加法、减法和乘法，如果在算法中能够尽量减少除法甚至避免除法，则算法的效率会大大提高。设 A=Sumi=0 to k(A*2*i)，0<=A<=1 ，贝U:C= A*B = Sumi=0 to k(A*B*2*i)可用循环处理为：C=0FOR i FROM k TO 0C=C*2实用文案C=C+A*BRETURN C若令 C'= A*B*2*(-k)，贝U:C'= Sumi=O to k(A*B*2*(i-k)用循环处理即：C'=0FOR i FROM 0 TO kC'=C'+A*BC'=C'/2RETURN C&#

14、39;通过这一算法求A*B*2*(-k)是不精确的，因为在循环中每次除以 2都可能 有余数被舍弃了，但是可以通过这一算法求A*B*2*(-k) %N 的精确值，方法是在对C'除2之前，让C'加上C'0*N。由于在RSA中N是两个素数的积，总是 奇数，所以当C'是奇数时，C'0=1 ，C'+C'0*N就是偶数，而当C'为偶数时C'0=0，C'+C'0*N 还是偶数，这样C72就不会有余数被舍弃。又因为 C'+N %N = C' %N ，所以在计算过程中加若干次 N，并不会影响结果的正确性。 可

15、以将算法整理如下：C'=0FOR i FROM 0 TO kC'=C'+A*BC'=C'/2C'=C'+C'0*N标准实用文案IF C'>=N C'=C'-NRETURN C'由于在RSA中A、B总是小于N，又Ov=A,C'Ov=1 ，所以：C' = (C'+A*B+C'0*N)/2C' < (C'+2N)/22C' < C'+2NC' < 2N既然C'总是小于2N，所以求C' %N就可以

16、很简单地在结束循环后用一次 减法来完成，即在求A*B*2*(-k) %N 的过程中不用反复求模，达到了我们避免 做除法的目的。当然，这一算法求得的是 A*B*2*(-k) %N ，而不是我们最初需 要的A*B %N。但是利用A*B*2*(-k)我们同样可以求得 A*E %N 。设 R=2*k %N ，R'=2*(-k) %N ，E=Sumi=O to n(E*2*i):A'=A*R %NX=A'FOR i FROM n TO 0X=X*X*R' %NIF E=1 X=X*A'*R' %NX=X*1*R' %NRETURN X最初：X =

17、A*R %N ，开始循环时：X = X*X*R' %N=A*R*A*R*R' %N=A*2*R %N反复循环之后：X = A*E*R %N最后：X = X*1*R' %N=A*E*R*R' %N=A*E %N如此，我们最终实现了不含除法的模幕算法，这就是著名的蒙哥马利算法，而X*Y*R' %N则被称为“蒙哥马利模乘”。以上讨论的是蒙哥马利模乘最简单， 最容易理解的二进制形式。蒙哥马利算法的核心思想在于将求A*B %N转化为不需要反复取模的A*B*R' %N，但是利用二进制算法求1024位的A*B*R' %N， 需要循环1024次之多，必然

18、希望找到更有效的计算 A*B*R' %N的算法。考虑将A表示为任意的r进制：A = Sumi=0 to k(A*r*i) 0<=A<=r我们需要得到的蒙哥马利乘积为：C'= A*B*R' %N R'=r*(-k)则以下算法只能得到C'的近似值C'=0FOR i FROM 0 TO kC'=C'+A*B标准实用文案C'=C'/rIF C'>=N C'=C'-NRETURN C'因为在循环中每次C'=C'/r时，都可能有余数被舍弃。假如我们能够找到一个系

19、数q，使得(C' + A*B + q*N) %r =0，并将算法修改为：C'=0FOR i FROM 0 TO kC'=C'+A*B+q*NC'=C'/rIF C'>=N C'=C'-NRETURN C'则C'的最终返回值就是A*B*R' %N的精确值，所以关键在于求q。由于:(C' + A*B + q*N) %r =0=> (C' %r + A*B %r + q*N %r) %r =0=> (C'0 + A*B0 + q*N0) %r =0若令 N0*N0

20、' %r =1，q=(C'0+A*B0)*(r-N0') %r ，贝U:(C'0 + A*B0 + q*N0) %r=(C'0+A*B0 - (C'0+A*B0)*N0'*N0) %r) %r=0于是我们可以得出r为任何值的蒙哥马利算法：m=r-N0'FOR i FROM 0 TO kq=(C'0+A*B0)*m %rC'=(C'+A*B+q*N)/rIF C'>=N C'=C'-NRETURN C'如果令r=0x100000000 ，贝U %r和/r运算都会变得非常容

21、易，在1024位的运算中，循环次数k不大于32，整个运算过程中最大的中间变量C'=(C'+A*B+q*N)< 2*r*N < 1057 位，算法效率就相当高了。唯一的额外负担 是需要计算N0'，使N0*N0' %r =1，而这一问题前面已经用欧几里德算法解决过了，而且在模幕运算转化成反复模乘运算时，N是固定值，所以N0'只需要计算一次，负担并不大。(六) 素数测试方法数论学家利用费马小定理研究出了多种素数测试方法，目前最快的算法是拉宾米勒测试算法，其过程如下：(1) 计算奇数 M，使得N=(2*r)*M+1(2) 选择随机数A<N(3)

22、 对于任意i<r，若A*(2*i)*M) % N = N-1，贝U N通过随机数A的测试(4) 或者，若A*M % N = 1，贝U N通过随机数A的测试(5) 让A取不同的值对N进行5次测试，若全部通过则判定 N为素数若N通过一次测试，则N不是素数的概率为25%，若N通过t次测试, 则N不是素数的概率为1/4*t。事实上取t为5时，N不是素数的概率为 1/128，N为素数的概率已经大于 99.99%。在实际应用中，可首先用300 500个小素数对N进行测试，以提高拉宾 米勒测试通过的概率，从而提高整体测试速度。而在生成随机素数时，选取的随 机数最好让r=0 ,则可省去步骤(3)的测试，

23、进一步提高测试速度。素数测试 是RSA选取秘钥的第一步，奇妙的是其核心运算与加解密时所需的运算完全一一 致：都是模幕运算。而模幕运算过程中中所需求解的欧几里德方程又恰恰正是选 取密钥第二步所用的运算。二、系统功能描述与软件模块划分实现大素数加法实现大素数减法实现大素数乘法实现大素数除法实现大素数模运算CBIGINT类用以实现大素数的加、减、乘、除CBigl nt Add( CBigI nt& A); /CBigl nt Sub(CBigI nt& A); /CBigl nt Mul(CBigl nt& A); /CBigI nt Div(CBigI nt& A)

24、; /CBigI nt Mod( CBigI nt& A); /CBigInt Add(unsigned long A);CBigInt Sub(unsigned long A);CBigI nt Mul(u nsig ned long A);CBigI nt Div(u nsig ned long A);RSA类用以实现素数检测、生成密钥、加密解密CBigI nt Euc(CBigl nt& A) ;/素数检测void GetKey(i ntlen ,CBigl nt& p,CBigI nt& q,CBigl nt&n ,CBigl nt加密&

25、_n,CBigI nt & e,CBig Int & d);/获得密钥void RsaJiami(char* m,char *c,CBigInt e,CBigInt n);/ void RsaJiemi(char* c,char *m,CBigl nt d,CBigl nt n); 解密三、设计核心代码#i nclude"Bigl nt.h"#i nclude"time.h"#i nclude"stri ng"#in clude<iostream>using n amespace std;const sta

26、tic int PrimeTable550=3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,3

27、97,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,8

28、83,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009, 1013, 1019,1021, 1031,1033,1039,1049,1051,1061, 1063,1069,1087,1091, 1093,1097,1103,1109,1117,1123, 1129,1151,1153,1163, 1171,1181,1187,1193,1201,1213, 1217,1223,1229,1231, 1237,1249,1259,1277,1279,1283, 1289,1291,1297,1301, 1303,1

29、307,1319,1321,1327,1361, 1367,1373,1381,1399, 1409,1423,1427,1429,1433,1439, 1447,1451,1453,1459, 1471,1481,1483,1487,1489,1493, 1499,1511,1523,1531, 1543,1549,1553,1559,1567,1571, 1579,1583,1597,1601, 1607,1609,1613,1619,1621,1627, 1637,1657,1663,1667, 1669,1693,1697,1699,1709,1721, 1723,1733,1741,

30、1747, 1753,1759,1777,1783,1787,1789, 1801,1811,1823,1831, 1847,1861,1867,1871,1873,1877, 1879,1889,1901,1907, 1913,1931,1933,1949,1951,1973, 1979,1987,1993,1997, 1999, 2003, 2011,2017, 2027, 2029, 2039, 2053, 2063,2069, 2081,2083, 2087, 2089, 2099, 2111,2113, 2129, 2131,2137, 2141,2143, 2153, 2161,2

31、179, 2203, 2207, 2213, 2221,2237, 2239, 2243, 2251,2267, 2269, 2273, 2281,2287, 2293,2297, 2309, 2311,2333, 2339, 2341,2347, 2351,2357, 2371,2377, 2381,2383, 2389, 2393, 2399, 2411,2417, 2423, 2437,2441,2447, 2459, 2467, 2473, 2477, 2503, 2521,2531,2539,2543, 2549, 2551,2557, 2579, 2591,2593, 2609,

32、2617, 2621,2633, 2647, 2657, 2659, 2663, 2671,2677, 2683, 2687, 2689,2693, 2699, 2707, 2711,2713, 2719, 2729, 2731,2741,2749,2753, 2767, 2777, 2789, 2791,2797, 2801,2803, 2819, 2833,2837, 2843, 2851,2857, 2861,2879, 2887, 2897, 2903, 2909,2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971,2999, 3001,301

33、1,3019, 3023, 3037, 3041,3049, 3061, 3067, 3079, 3083,3089, 3109, 3119, 3121,3137, 3163, 3167, 3169, 3181,3187,3191,3203, 3209, 3217, 3221,3229, 3251, 3253, 3257, 3259,3271,3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331,3343,3347, 3359, 3361, 3371,3373, 3389, 3391, 3407, 3413, 3433,3449, 3457, 3461,

34、 3463, 3467, 3469, 3491, 3499, 3511,3517,3527, 3529, 3533, 3539, 3541,3547, 3557, 3559, 3571,3581,3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659,3671,3673, 3677, 3691,3697, 3701,3709, 3719, 3727, 3733,3739, 3761,3767, 3769, 3779, 3793, 3797, 3803, 3821,3823,3833,3847,3851, 3853, 3863, 38

35、77, 3881, 3889, 3907, 3911,3917, 3919, 3923, 3929, 3931,3943, 3947, 3967, 3989, 4001；const static long Primeco un t=sizeof(PrimeTable)/sizeof( Ion g);CBigl nt:CBigl nt() /构造大数对象并初始化为零m_nLen gth=1;for(int i=O;i<BI_MAXLEN;i+)m_ulValuei=O;CBigI nt:CBigl nt() /解构大数对象int CBigInt:Cmp(CBiglnt& A) /大

36、数比较，X>A 返回 1 , X=A 返回 0, X<A 返回-1if(m_nLen gth>A.m_ nLen gth)retur n 1;if(m_nLen gth<A.m_ nLen gth)retur n -1;for(i nt i=m_nLen gth-1;i>=0;i-)if(m_ulValuei>A.m_ulValuei)return 1;if(m_ulValuei<A.m_ulValuei)return -1;return 0;void CBigInt:Mov(CBiglnt& A) /把 A 的值赋给 Xm_nLen gth=

37、A.m_ nLen gth;for(int i=0;i<BI_MAXLEN;i+)m_ulValuei=A.m_ulValuei;void CBigl nt:Mov(u nsig ned _in t64 A)if(A>0xffffffff)m_nLen gth=2;m_ulValue1=(unsigned Iong)(A>>32);m_ulValueO=(u nsig ned Ion g)A;elsem_nLen gth=1;m_ulValueO=(u nsig ned Ion g)A;for(int i=m_nLength;i<BI_MAXLEN;i+)m_ul

38、Valuei=O;CBigI nt CBigI nt:Add(CBig lnt& A) /加法CBig Int X;X.Mov(*this);un sig ned carry=0;un sig ned _in t64 sum=0;标准实用文案if(X.m_ nLen gth<A.m_ nLen gth)X.m_ nLen gth=A.m_ nLen gth;for(un sig ned i=0;i<X.m_ nLen gth;i+)sum=A.m_ulValuei;sum=sum+X.m_ulValuei+carry;X.m_ulValuei=(un sig ned Ion

39、 g)sum;carry=(un sig ned)(sum>>32);X.m_ulValueX.m _nLen gth=carry;X.m _nLen gth+=carry;return X;CBigInt CBigInt:Add(unsigned long A)CBig Int X;X.Mov(*this);un sig ned _in t64 sum;sum=X.m_ulValueO;sum+=A;if(sum>0xffffffff)X.m_ulValueO=(un sig ned Ion g)sum;标准实用文案un sig ned i=1;while(X.m_ulVa

40、luei=Oxffffffff)X.m_ulValuei=O;i+;X. m_ulValuei+;if(m_nLen gth=i)m_ nLen gth+;return X;CBigl nt CBigl nt:Sub(CBigl nt& A) /减法CBig Int X;X.Mov(*this);if(X.Cmp(A)<=0)X.Mov(0);return X;un sig ned carry=0;un sig ned _in t64 num;un sig ned i;for(i=0;i<m_ nLen gth;i+)if(m_ulValuei>A.m_ulValue

41、i)|(m_ulValuei=A.m_ulValuei) &&(carry=0) carry=0;X.m_ulValuei=m_ulValuei-carry-A.m_ulValuei;标准实用文案elsenum=0x100000000+m_ulValuei;X. m_ulValuei=(unsigned Iong)(num-carry-A.m_ulValuei); carry=1;while(X.m_ulValueX.m_ nLen gth-1=0)X.m_ nLe ngth_;return X;CBigInt CBigInt:Sub(unsigned long A)CBig

42、Int X;X.Mov(*this);if(X.m_ulValueO>=A)X.m_ulValueO-=A;return X;if(X.m_ nLe ngth=1)X.Mov(0);return X;un sig ned _in t64 num=0x100000000+X.m_ulValue0;X.m_ulValueO=(un sig ned long)(nu m-A);in t i=1;X.m_ulValuei-;while(X.m_ulValuei=O)X.m_ulValuei=Oxffffffff;i+;标准实用文案if(X.m_ulValuei=O)X.m_nLe ngth-;

43、return X;CBigI nt CBigI nt:Mul( CBigI nt& A) /乘法if(A.m_nLength=1)return Mul(A.m_ulValueO);CBigI nt X;un sig ned _in t64 sum,mul=O,carry=O;un sig ned i,j;X. m_ nLen gth=m_ nLen gth+A.m_ nLen gth-1;for(i=0;i<X.m_ nLen gth;i+)sum=carry;carry=0;for(j=0;j<A.m_ nLen gth;j+)if(i-j)>=0)&&am

44、p;(i-j)<m_ nLen gth)mul=m_ulValuei-j;mul*=A.m_ulValuej;carry+=mul>>32;mul=mul&0 xffffffff;sum+=mul;carry+=sum>>32;X. m_ulValuei=(un sig ned Ion g)sum;if(carry)X.m_nLength+;X.m_ulValueX.m_nLength_1=(unsigned Iong)carry; return X;CBigInt CBigInt:Mul(unsigned long A)CBig Int X;un sig

45、 ned _in t64 mul;un sig ned long carry=0;X.Mov(*this);for(un sig ned i=0;i<m_ nLen gth;i+)mul=m_ulValuei;mul=mul*A+carry;X.m_ulValuei=(un sig ned Ion g)mul;carry=(un sig ned Ion g)(mul>>32);if(carry)X.m_ nLen gth+;X.m_ulValueX.m_ nLen gth-1=carry; return X;CBig Int CBigI nt:Div( CBigI nt&am

46、p; A) /除法if(A.m_ nLen gth=1)return Div(A.m_ulValueO);CBigI nt X,Y,Z;un sig ned i,le n;un sig ned _in t64 nu m,div;Y.Mov(*this);while(Y.Cmp(A)>=0)div=Y.m_ulValueY.m_ nLe ngth-1;num=A.m_ulValueA.m_ nLen gth-1;len=Y.m_nLen gth-A.m_ nLen gth;if(div=num)&&(le n=0)X.Mov(X.Add(1);break;if(div<

47、;=nu m)&&len )le n-;div=(div<<32)+Y.m_ulValueY.m_ nLen gth-2;div=div/( nu m+1);Z.Mov(div);if(le n)Z.m_ nLen gth+=le n;for(i=Z.m_ nLen gth-1;i>=le n;i-)Z.m_ulValuei=Z.m_ulValuei-le n; for(i=0;i<le n;i+)Z.m_ulValuei=O;X.Mov(X.Add(Z);Y.Mov(Y.Sub(A.Mul(Z);return X;CBigInt CBigInt:Div

48、(unsigned long A)CBig Int X;X.Mov(*this);if(X.m_ nLen gth=1)X.m_ulValue0=X.m_ulValue0/A;return X;un sig ned _in t64 div,mul;un sig ned long carry=0;for(i nt i=X.m_nLen gth-1;i>=0;i-)div=carry;div=(div<<32)+X.m_ulValuei;X.m_ulValuei=(un sig ned Ion g)(div/A);mul=(div/A)*A;carry=(un sig ned I

49、on g)(div-mul);if(X.m_ulValueX.m_ nLe ngth-1=0)X.m_ nLe ngth_;return X;CBigI nt CBigI nt:Mod(CBigl nt& A) /求模CBig Int X,Y;un sig ned _in t64 div, num;un sig ned long carry=0;un sig ned i,le n;X.Mov(*this);while(X.Cmp(A)>=0)div=X.m_ulValueX.m_ nLe ngth-1;num=A.m_ulValueA.m_ nLen gth-1;len=X.m_ nLen gth-A.m_ nLen gth;if(div=num)&&a