RSA算法設計實現(xiàn)分析

1、-*大學密碼學課程設計報告題目名稱：RSA加密解密的設計與實現(xiàn)姓 名：學 號：專 業(yè)：一、 設計原理算法工作原理RSA 原理：RSA 密鑰的選取和加解密過程都非常簡潔，在算法上主要要實現(xiàn)四個問題：1、如何處理大數(shù)運算2、如何求解同余方程 *Y % M = 13、如何快速進展模冪運算4、如何獲取大素數(shù)(一) 大數(shù)存儲RSA 依賴大數(shù)運算，目前主流RSA 算法都建立在1024位的大數(shù)運算之上。而大多數(shù)的編譯器只能支持到64位的整數(shù)運算，即我們在運算中所使用的整數(shù)必須小于等于64位，即：0*ffffffffffffffff，也就是615，這遠遠達不到RSA 的需要，于是需要專門建立大數(shù)運算庫來解決這

2、一問題。一個有效的改進方法是將大數(shù)表示為一個n 進制數(shù)組，對于目前的32位系統(tǒng)而言n 可以取值為2 的32次方，即 0*100000000，假設將一個二進制為1024位的大數(shù)轉化成0*10000000進制，就變成了32位，而每一位的取值圍不再是二進制的01或十進制的09，而是0-0*ffffffff，我們正好可以用一個32位的DWORD 如：無符號長整數(shù)，unsigned long 類型來表示該值。所以1024位的大數(shù)就變成一個含有32個元素的 DWORD數(shù)組，而針對 DWORD數(shù)組進展各種運算所需的循環(huán)規(guī)模至多32次而已。而且0*100000000 進制與二進制，對于計算機來說，幾乎是一回事

3、，轉換非常容易。例如：大數(shù)615，等于 0*ffffffff ffffffff，就相當于十進制的99：有兩位，每位都是0*ffffffff。而616等于0*00000001；00000000 00000000，就相當于十進制的100：有三位，第一位是1 ，其它兩位都是0 ，如此等等。在實際應用中，“數(shù)字數(shù)組的排列順序采用低位在前高位在后的方式，這樣，大數(shù)A 就可以方便地用數(shù)學表達式來表示其值：A=Sumi=0 to n(A*r*i)，r=0*100000000，0<=A<r其中Sum 表示求和，A表示用以記錄A 的數(shù)組的第i 個元素，*表示乘方。任何整數(shù)運算最終都能分解成數(shù)字與數(shù)字

4、之間的運算，在0*100000000 進制下其“數(shù)字最大到達0*ffffffff，其數(shù)字與數(shù)字之間的運算，結果也必然超出了目前32位系統(tǒng)的字長。在VC+中，存在一個_int64 類型可以處理64位的整數(shù)，所以不用擔憂這一問題。(二) 加減乘除設有大數(shù)A、B和C，其中A>=B：A=Sumi=0 to p(A*r*i)B=Sumi=0 to q(B*r*i)C=Sumi=0 to n(C*r*i)r=0*100000000，0<=A,B,C<r，p>=q則當C=A+B、C=A-B、C=A*B時，我們都可以通過計算出C來獲得C：C=A+B，顯然C不總是等于A+B，因為A+B可

5、能>0*ffffffff，而C必須<=0*ffffffff，這時就需要進位，當然在計算Ci-1時也可能產(chǎn)生了進位，所以計算C時還要加上上次的進位值。如果用一個64位變量result來記錄和，另一個32位變量carry來記錄進位，則有：carry=0FOR i FROM 0 TO presult=A+B+carryC=result%0*100000000carry=result/0*100000000IF carry=0 n=pELSE n=p+1C=A-B，同理C不總是等于A-B，因為A-B可能<0，而C必須>=0，這時就需要借位，同樣在計算Ci-1時也可能產(chǎn)生了借位，

6、所以計算C時還要減去上次的借位值：carry=0FOR i FROM 0 TO pIF A-B-carry>=0C=A-B-carrycarry=0ELSEC=0*100000000+A-B-carrycarry=1n=pWHILE Cn=0 n=n-1C=A*B，首先我們需要觀察日常做乘法所用的“豎式計算過程：A3 A2 A1 A0* B2 B1 B0-= A3B0 A2B0 A1B0 A0B0+ A3B1 A2B1 A1B1 A0B1+ A3B2 A2B2 A1B2 A0B2-= C5 C4 C3 C2 C1 C0可以歸納出：C=Sumj=0 to q(Ai-j*Bj)，其中i-j必

7、須>=0且<=p。當然這一結論沒有考慮進位，雖然計算Ai-j*Bj和Sum的時候都可能發(fā)生進位，但顯然這兩種原因產(chǎn)生的進位可以累加成一個進位值。最終可用如下算法完成乘法：n=p+q-1carry=0For i FROM 0 TO nresult=carryFor j FROM 0 TO qIF 0<=i-j<=p result=result+Ai-j*BjC=result%0*100000000carry=result/0*100000000IF carry!=0n=n+1Cn=carry對于C=A/B，由于無法將B 對A“試商，我們只能轉換成Bq對Ap的試商來得到一個

8、近似值，所以無法直接通過計算C來獲得C，只能一步步逼近C。由于：B*(Ap/Bq-1)*0*100000000*(p-q)<C，令：*=0，重復A=A-*B，*=*+(Ap/Bq-1)*0*100000000*(p-q)，直到A<B則：*=A/B，且此時的A=A%B，注意對于任意大數(shù)A*0*100000000*k，都等價于將A 的數(shù)組中的各元素左移k 位，不必計算；同樣，A/0*100000000*k則等價于右移。(三) 歐幾里得方程在RSA 算法中，往往要在A、N的情況下，求 B，使得 (A*B)%N=1。即相當于求解B、M都是未知數(shù)的二元一次不定方程 A*B-N*M=1 的最小

9、整數(shù)解。而針對不定方程a*-by=c 的最小整數(shù)解，有著名的歐幾里德算法，即輾轉相除法。事實上二元一次不定方程有整數(shù)解的充要條件是c為a、b的最大公約數(shù)。即當c=1時，a、b必須互質(zhì)。而在RSA算法里由于公鑰d為素數(shù)，素數(shù)與任何正整數(shù)互質(zhì)，所以可以通過歐幾里德方程來求解私鑰e。歐幾里德算法是一種遞歸算法，比較容易理解：例如：11*-49y=1，求*a 11 * - 49 y = 1 49%11=5 ->b 11 * - 5 y = 1 11%5 =1 ->c * - 5 y = 1令y=0 代入c得*=1令*=1 代入b得y=2令y=2 代入a得*=9同理可使用遞歸算法求得任意 a

10、*-by=1a、b互質(zhì)的解。實際上通過分析歸納將遞歸算法轉換成非遞歸算法就變成了大衍求一術：*=0,y=1WHILE a!=0i=yy=*-y*a/b*=ii=aa=b%ab=iIF *<0 *=*+bRETURN *(四) 模冪運算模冪運算是RSA 的核心算法，最直接地決定了RSA 算法的性能。針對快速模冪運算這一課題，西方現(xiàn)代數(shù)學家提出了大量的解決方案，通常都是先將冪模運算轉化為乘模運算。例如求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*C

11、2 % 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 個乘模運算，歸納分析以上方法可以發(fā)現(xiàn)對于任意E，都可采用以下算法計算D=C*E % N：D=1WHILE E>=0IF E%2=0C=C*C % NE=E/2ELSED=D*C % NE=E-1RETURN D繼續(xù)分析會發(fā)現(xiàn)，要知道E 何時能整除 2，并不需要反復進展減一或除二的操作，只需驗證E 的二進制各位是0 還是1 就可以了，從左至右或從右至左驗證都可以，從左至右會更簡潔，設E=Sumi

12、=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 的核心算法是模冪運算，模冪運算又相當于模乘運算的循環(huán)，要提高RSA 算法的效率，首要問題在于提高模乘運算的效率。不難發(fā)現(xiàn)，模乘過程中復雜度最高的環(huán)節(jié)是求模運算，因為一次除法實際上包含了屢次加法、減法和乘法，如果在算法中能夠盡量減少除法甚至防止除法，則算法的效率會大大提高。設A=Sumi=0 to k(A*2*i)，0<=A<=1，則：C= A*B = S

13、umi=0 to k(A*B*2*i)可用循環(huán)處理為：C=0FOR i FROM k TO 0C=C*2C=C+A*BRETURN C假設令 C'= A*B*2*(-k)，則：C'= Sumi=0 to k(A*B*2*(i-k)用循環(huán)處理即：C'=0FOR i FROM 0 TO kC'=C'+A*BC'=C'/2RETURN C'通過這一算法求A*B*2*(-k)是不準確的，因為在循環(huán)中每次除以2都可能有余數(shù)被舍棄了，但是可以通過這一算法求A*B*2*(-k) %N的準確值，方法是在對C'除2之前，讓C'加上C

14、'0*N。由于在RSA中N是兩個素數(shù)的積，總是奇數(shù)，所以當C'是奇數(shù)時，C'0=1，C'+C'0*N 就是偶數(shù)，而當C'為偶數(shù)時C'0=0，C'+C'0*N還是偶數(shù)，這樣C'/2 就不會有余數(shù)被舍棄。又因為C'+N %N = C' %N，所以在計算過程中加假設干次N，并不會影響結果的正確性?？梢詫⑺惴ㄕ砣缦拢篊'=0FOR i FROM 0 TO kC'=C'+A*BC'=C'+C'0*NC'=C'/2IF C'>=N

15、C'=C'-NRETURN C'由于在RSA中A、B總是小于N，又0<=A,C'0<=1，所以：C' = (C'+A*B+C'0*N)/2C' < (C'+2N)/22C' < C'+2NC' < 2N既然C'總是小于2N，所以求C' %N 就可以很簡單地在完畢循環(huán)后用一次減法來完成，即在求A*B*2*(-k) %N的過程中不用反復求模，到達了我們防止做除法的目的。當然，這一算法求得的是A*B*2*(-k) %N，而不是我們最初需要的A*B %N。但是利

16、用A*B*2*(-k)我們同樣可以求得A*E %N。設R=2*k %N，R'=2*(-k) %N，E=Sumi=0 to n(E*2*i)：A'=A*R %N*=A'FOR i FROM n TO 0*=*R' %NIF E=1 *=*A'*R' %N*=*1*R' %NRETURN *最初：* = A*R %N，開場循環(huán)時：* = *R' %N= A*R*A*R*R' %N = A*2*R %N反復循環(huán)之后：* = A*E*R %N最后：* = *1*R' %N= A*E*R*R' %N= A*E %N如

17、此，我們最終實現(xiàn)了不含除法的模冪算法，這就是著名的蒙哥馬利算法，而*Y*R' %N 則被稱為“蒙哥馬利模乘。以上討論的是蒙哥馬利模乘最簡單，最容易理解的二進制形式。蒙哥馬利算法的核心思想在于將求A*B %N轉化為不需要反復取模的A*B*R' %N，但是利用二進制算法求1024位的A*B*R' %N，需要循環(huán)1024次之多，必然希望找到更有效的計算A*B*R' %N的算法?？紤]將A表示為任意的r進制：A = Sumi=0 to k(A*r*i) 0<=A<=r我們需要得到的蒙哥馬利乘積為：C'= A*B*R' %N R'=r*(

18、-k)則以下算法只能得到C'的近似值C'=0FOR i FROM 0 TO kC'=C'+A*BC'=C'/rIF C'>=N C'=C'-NRETURN C'因為在循環(huán)中每次C'=C'/r 時，都可能有余數(shù)被舍棄。假設我們能夠找到一個系數(shù) 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'

19、;-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' %r =1，q=(C'0+A*B0)*(r-N0') %r，則：(C'0 + A*B0 + q*N0) %r= (C'0+A*B0 - (C'0+A*B0)*N0'*N0) %r) %r= 0于是我

20、們可以得出r為任何值的蒙哥馬利算法：m=r-N0'C'=0FOR i FROM 0 TO kq=(C'0+A*B0)*m %rC'=(C'+A*B+q*N)/rIF C'>=N C'=C'-NRETURN C'如果令 r=0*100000000，則 %r 和 /r 運算都會變得非常容易，在1024位的運算中，循環(huán)次數(shù)k 不大于32，整個運算過程中最大的中間變量C'=(C'+A*B+q*N)< 2*r*N < 1057位，算法效率就相當高了。唯一的額外負擔是需要計算 N0'，使N0*

21、N0' %r =1，而這一問題前面已經(jīng)用歐幾里德算法解決過了，而且在模冪運算轉化成反復模乘運算時，N是固定值，所以N0'只需要計算一次，負擔并不大。(六) 素數(shù)測試方法數(shù)論學家利用費馬小定理研究出了多種素數(shù)測試方法，目前最快的算法是拉賓米勒測試算法，其過程如下：1計算奇數(shù)M，使得N=(2*r)*M+12選擇隨機數(shù)A<N3對于任意i<r，假設A*(2*i)*M) % N = N-1，則N通過隨機數(shù)A的測試4或者，假設A*M % N = 1，則N通過隨機數(shù)A的測試5讓A取不同的值對N進展5次測試，假設全部通過則判定N為素數(shù)假設N 通過一次測試，則N 不是素數(shù)的概率為 2

22、5%，假設N 通過t 次測試，則N 不是素數(shù)的概率為1/4*t。事實上取t 為5 時，N 不是素數(shù)的概率為 1/128，N 為素數(shù)的概率已經(jīng)大于99.99%。在實際應用中，可首先用300500個小素數(shù)對N 進展測試，以提高拉賓米勒測試通過的概率，從而提高整體測試速度。而在生成隨機素數(shù)時，選取的隨機數(shù)最好讓r=0，則可省去步驟3 的測試，進一步提高測試速度。素數(shù)測試是RSA 選取秘鑰的第一步，奇妙的是其核心運算與加解密時所需的運算完全一致：都是模冪運算。而模冪運算過程中中所需求解的歐幾里德方程又恰恰正是選取密鑰第二步所用的運算。二、 系統(tǒng)功能描述與軟件模塊劃分CBIGINT類用以實現(xiàn)大素數(shù)的加、

23、減、乘、除CBigInt Add( CBigInt& A); /實現(xiàn)大素數(shù)加法CBigInt Sub(CBigInt& A); /實現(xiàn)大素數(shù)減法CBigInt Mul(CBigInt& A); /實現(xiàn)大素數(shù)乘法CBigInt Div(CBigInt& A); /實現(xiàn)大素數(shù)除法CBigInt Mod( CBigInt& A); /實現(xiàn)大素數(shù)模運算CBigInt Add(unsigned long A); CBigInt Sub(unsigned long A); CBigInt Mul(unsigned long A); CBigInt Div(unsig

24、ned long A);RSA類用以實現(xiàn)素數(shù)檢測、生成密鑰、加密解密CBigInt Euc(CBigInt& A) ;/素數(shù)檢測void GetKey(int len,CBigInt &p,CBigInt &q,CBigInt &n,CBigInt &_n,CBigInt &e,CBigInt &d);/獲得密鑰void RsaJiami(char* m,char *c,CBigInt e,CBigInt n);/加密void RsaJiemi(char* c,char *m,CBigInt d,CBigInt n);/解密三、 設計核心

25、代碼*include"BigInt.h"*include"time.h"*include"string"*include<iostream>using namespace std;const static 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,

26、 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, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499,

27、 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, 883, 887, 907,

28、 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,

29、1283, 1289, 1291, 1297, 1301, 1303, 1307, 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,

30、1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 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, 2021, 2021, 2027,

31、2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 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,

32、2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 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,

33、2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 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,

34、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, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623,

35、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, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001 ; const static long Primecount=sizeof

36、(PrimeTable)/sizeof(long);CBigInt:CBigInt() /構造大數(shù)對象并初始化為零 m_nLength=1; for(int i=0;i<BI_MA*LEN;i+)m_ulValuei=0; CBigInt:CBigInt() /解構大數(shù)對象 int CBigInt:Cmp(CBigInt& A) /大數(shù)比較，*>A返回1，*=A返回0，*<A返回-1 if(m_nLength>A.m_nLength)return 1; if(m_nLength<A.m_nLength)return -1; for(int i=m_nLen

37、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(CBigInt& A) /把A的值賦給* m_nLength=A.m_nLength; for(int i=0;i<BI_MA*LEN;i+)m_ulValuei=A.m_ulValuei; void CBigInt:Mov(unsigned _int64 A) if(A>0*ffffffff) m_nLength=2; m_

38、ulValue1=(unsigned long)(A>>32); m_ulValue0=(unsigned long)A; else m_nLength=1; m_ulValue0=(unsigned long)A; for(int i=m_nLength;i<BI_MA*LEN;i+)m_ulValuei=0; CBigInt CBigInt:Add(CBigInt& A) /加法 CBigInt *; *.Mov(*this); unsigned carry=0; unsigned _int64 sum=0; if(*.m_nLength<A.m_nLeng

39、th)*.m_nLength=A.m_nLength; for(unsigned i=0;i<*.m_nLength;i+) sum=A.m_ulValuei; sum=sum+*.m_ulValuei+carry; *.m_ulValuei=(unsigned long)sum; carry=(unsigned)(sum>>32); *.m_ulValue*.m_nLength=carry; *.m_nLength+=carry; return *; CBigInt CBigInt:Add(unsigned long A) CBigInt *; *.Mov(*this);

40、unsigned _int64 sum; sum=*.m_ulValue0; sum+=A; *.m_ulValue0=(unsigned long)sum; if(sum>0*ffffffff) unsigned i=1; while(*.m_ulValuei=0*ffffffff)*.m_ulValuei=0;i+; *.m_ulValuei+; if(m_nLength=i)m_nLength+; return *; CBigInt CBigInt:Sub(CBigInt& A) /減法 CBigInt *; *.Mov(*this); if(*.Cmp(A)<=0)

41、*.Mov(0);return *; unsigned carry=0; unsigned _int64 num; unsigned i; for(i=0;i<m_nLength;i+) if(m_ulValuei>A.m_ulValuei)|(m_ulValuei=A.m_ulValuei)&&(carry=0) *.m_ulValuei=m_ulValuei-carry-A.m_ulValuei; carry=0; else num=0*100000000+m_ulValuei; *.m_ulValuei=(unsigned long)(num-carry-A.

42、m_ulValuei); carry=1; while(*.m_ulValue*.m_nLength-1=0)*.m_nLength-; return *; CBigInt CBigInt:Sub(unsigned long A) CBigInt *; *.Mov(*this); if(*.m_ulValue0>=A)*.m_ulValue0-=A;return *; if(*.m_nLength=1)*.Mov(0);return *; unsigned _int64 num=0*100000000+*.m_ulValue0; *.m_ulValue0=(unsigned long)(

43、num-A); int i=1; while(*.m_ulValuei=0)*.m_ulValuei=0*ffffffff;i+; *.m_ulValuei-; if(*.m_ulValuei=0)*.m_nLength-; return *; CBigInt CBigInt:Mul( CBigInt& A) /乘法 if(A.m_nLength=1)return Mul(A.m_ulValue0); CBigInt *; unsigned _int64 sum,mul=0,carry=0; unsigned i,j; *.m_nLength=m_nLength+A.m_nLength

44、-1; for(i=0;i<*.m_nLength;i+) sum=carry; carry=0; for(j=0;j<A.m_nLength;j+) if(i-j)>=0)&&(i-j)<m_nLength) mul=m_ulValuei-j; mul*=A.m_ulValuej; carry+=mul>>32; mul=mul&0*ffffffff; sum+=mul; carry+=sum>>32; *.m_ulValuei=(unsigned long)sum; if(carry)*.m_nLength+;*.m_

45、ulValue*.m_nLength-1=(unsigned long)carry; return *; CBigInt CBigInt:Mul(unsigned long A) CBigInt *; unsigned _int64 mul; unsigned long carry=0; *.Mov(*this); for(unsigned i=0;i<m_nLength;i+) mul=m_ulValuei; mul=mul*A+carry; *.m_ulValuei=(unsigned long)mul; carry=(unsigned long)(mul>>32); i

46、f(carry)*.m_nLength+;*.m_ulValue*.m_nLength-1=carry; return *; CBigInt CBigInt:Div( CBigInt& A) /除法 if(A.m_nLength=1)return Div(A.m_ulValue0); CBigInt *,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; l

47、en=Y.m_nLength-A.m_nLength; if(div=num)&&(len=0)*.Mov(*.Add(1);break; if(div<=num)&&len)len-;div=(div<<32)+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;i-)Z.m_ulValuei=Z.m_ulValuei-len; for(i=0;i<len;i+)Z.m

48、_ulValuei=0; *.Mov(*.Add(Z); Y.Mov(Y.Sub(A.Mul(Z); return *; CBigInt CBigInt:Div(unsigned long A) CBigInt *; *.Mov(*this); if(*.m_nLength=1)*.m_ulValue0=*.m_ulValue0/A;return *; unsigned _int64 div,mul; unsigned long carry=0; for(int i=*.m_nLength-1;i>=0;i-) div=carry; div=(div<<32)+*.m_ulV

49、aluei; *.m_ulValuei=(unsigned long)(div/A); mul=(div/A)*A; carry=(unsigned long)(div-mul); if(*.m_ulValue*.m_nLength-1=0)*.m_nLength-; return *; CBigInt CBigInt:Mod(CBigInt& A) /求模 CBigInt *,Y; unsigned _int64 div,num; unsigned long carry=0; unsigned i,len; *.Mov(*this); while(*.Cmp(A)>=0) div=