?? rsahelpdlg.cpp
字號:
m_Text+=" C=Sum[i=0 to q](A*B[i]*0x100000000**i)";
m_Text+="\r\n";
m_Text+=" 而(A*B[i]*100000000**i)=Sum[j=0 to p](A[j]*B[i]*0x100000000**(i+j))";
m_Text+="\r\n";
m_Text+=" 所以C=Sum[i=0 to q](Sum[j=0 to p](A[j]*B[i]*0x100000000**(i+j)))";
m_Text+="\r\n";
m_Text+="";
m_Text+="\r\n";
m_Text+="因此：";
m_Text+="\r\n";
m_Text+=" C[i]=Sum[j=0 to q](A[i-j]*B[j])+carry[i-1]-carry[i]*0x100000000";
m_Text+="\r\n";
m_Text+=" 其中carry[-1]=0";
m_Text+="\r\n";
m_Text+=" carry[i]=(Sum[j=0 to q](A[i-j]*B[j])+carry[i-1])/0x100000000";
m_Text+="\r\n";
m_Text+=" n=p+q-1，若carry[n]>0，則n=n+1，C[n]=carry";
m_Text+="\r\n";
m_Text+="\r\n";
m_HelpRsa.SetWindowText(m_Text);
break;
case 6:
m_Text="";
m_Text+="\r\n";
m_Text+="設：";
m_Text+="\r\n";
m_Text+=" A=Sum[i=0 to p](A[i]*0x100000000**i)";
m_Text+="\r\n";
m_Text+=" B=Sum[i=0 to q](B[i]*0x100000000**i)，p>=q";
m_Text+="\r\n";
m_Text+=" C=Sum[i=0 to n](C[i]*0x100000000**i)=A/B";
m_Text+="\r\n";
m_Text+="";
m_Text+="\r\n";
m_Text+="由于無法將B 對A “試商”，我們只能轉換成B[q]對A[p]的試商來得到一個近似值，";
m_Text+="\r\n";
m_Text+="所以我們不能夠直接計算C。但是，我們可以一步一步地逼近C";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+="顯然：";
m_Text+="\r\n";
m_Text+=" (A[p]/B[q]-1)*0x100000000**(p-q)<C";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+="令：";
m_Text+="\r\n";
m_Text+=" X=0";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+="重復：";
m_Text+="\r\n";
m_Text+=" A=A-X*B，X=X+(A[p]/B[q]-1)*0x100000000**(p-q)，直到A<B";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+="則有：";
m_Text+="\r\n";
m_Text+=" X=C";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+="注意：";
m_Text+="\r\n";
m_Text+=" 由于大數可理解為0x100000000進制，所以對于任意大數A*0x100000000**k";
m_Text+="\r\n";
m_Text+=" 都等價于將A 的數組中的各元素左移k 位，不必計算；同樣，除法則等價于右移";
m_Text+="\r\n";
m_Text+="\r\n";
m_HelpRsa.SetWindowText(m_Text);
break;
case 7:
m_Text="";
m_Text+="\r\n";
m_Text+="設：";
m_Text+="\r\n";
m_Text+=" A=Sum[i=0 to p](A[i]*0x100000000**i)";
m_Text+="\r\n";
m_Text+=" B=Sum[i=0 to q](B[i]*0x100000000**i)，p>=q";
m_Text+="\r\n";
m_Text+=" C=Sum[i=0 to n](C[i]*0x100000000**i)=A%B";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+="求模與求商的過程一致，只是由于不需要記錄商而更加簡單：";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+="重復：";
m_Text+="\r\n";
m_Text+=" A=A-(A[p]/B[q]-1)*0x100000000**(p-q)*B，直到A<B";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+="則有：";
m_Text+="\r\n";
m_Text+=" A=C";
m_Text+="\r\n";
m_Text+="\r\n";
m_HelpRsa.SetWindowText(m_Text);
break;
case 8:
m_Text="";
m_Text+="\r\n";
m_Text+=" 在RSA 算法中，往往要在已知A、M的情況下，求 B，使得 (A*B)%M=1。即相當于";
m_Text+="\r\n";
m_Text+="求解B、N都是未知數的二元一次不定方程 A*B-M*N=1，的最小整數解。";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+=" 而針對不定方程ax-by=1 的最小整數解，古今中外都進行過詳盡的研究，西方有";
m_Text+="\r\n";
m_Text+="著名的歐幾里德算法，即輾轉相除法，中國有秦九韶的“大衍求一術”。歐幾里德算";
m_Text+="\r\n";
m_Text+="法是一種遞歸算法，比較容易理解：";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+=" 例如：11x-49y=1，求x";
m_Text+="\r\n";
m_Text+=" （a） 11 x - 49 y = 1 49%11=5 ->";
m_Text+="\r\n";
m_Text+=" （b） 11 x - 5 y = 1 11%5 =1 ->";
m_Text+="\r\n";
m_Text+=" （c） x - 5 y = 1";
m_Text+="\r\n";
m_Text+=" 令y=0 代入（c）得x=1";
m_Text+="\r\n";
m_Text+=" 令x=1 代入（b）得y=2";
m_Text+="\r\n";
m_Text+=" 令y=2 代入（a）得x=9";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+=" 同理可使用遞歸算法求得任意 ax-by=1（a、b互質）的解，實際上通過分析歸納";
m_Text+="\r\n";
m_Text+="將遞歸算法轉換成非遞歸算法就變成了大衍求一術。";
m_Text+="\r\n";
m_Text+="\r\n";
m_HelpRsa.SetWindowText(m_Text);
break;
case 9:
m_Text="";
m_Text+="\r\n";
m_Text+=" 冪模運算是RSA 核心算法，最直接地決定了RSA 算法的性能，針對快速冪模運算";
m_Text+="\r\n";
m_Text+="這一課題，許多西方現代數學家提出了大量的解決方案。通常都是先將冪模運算化簡";
m_Text+="\r\n";
m_Text+="為乘模運算。";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+=" 例如求D=C**15 % N，由于：";
m_Text+="\r\n";
m_Text+=" a*b % n = (a % n)*(b % n) % n";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+=" 所以：";
m_Text+="\r\n";
m_Text+=" C1=C*C % N =C**2 % N";
m_Text+="\r\n";
m_Text+=" C2=C1*C % N =C**3 % N";
m_Text+="\r\n";
m_Text+=" C3=C2*C2 % N =C**6 % N";
m_Text+="\r\n";
m_Text+=" C4=C3*C % N =C**7 % N";
m_Text+="\r\n";
m_Text+=" C5=C4*C4 % N =C**14 % N";
m_Text+="\r\n";
m_Text+=" C6=C5*C % N =C**15 % N ";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+=" 即：";
m_Text+="\r\n";
m_Text+=" 對于E=15的冪模運算可分解為6個乘模運算";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+=" 歸納分析以上方法可以發現對于任意E，可采用以下算法計算D=C**E % N：";
m_Text+="\r\n";
m_Text+=" D=1";
m_Text+="\r\n";
m_Text+=" WHILE E>=0";
m_Text+="\r\n";
m_Text+=" IF E為奇數";
m_Text+="\r\n";
m_Text+=" D=D*C % N";
m_Text+="\r\n";
m_Text+=" D=D*D % N";
m_Text+="\r\n";
m_Text+=" E=E-1";
m_Text+="\r\n";
m_Text+=" IF E為偶數";
m_Text+="\r\n";
m_Text+=" D=D*D % N";
m_Text+="\r\n";
m_Text+=" E=E/2";
m_Text+="\r\n";
m_Text+=" RETURN D";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+=" 再加以分析會發現，要知道D 何時需乘 C，不需要反復對E 進行減一或除二的操";
m_Text+="\r\n";
m_Text+="作，只需要驗證E 的二進制各位是0 還是1 就可以了，而且從左至右驗證和從右至左";
m_Text+="\r\n";
m_Text+="驗證都行，反而從左至右驗證更簡單：";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+=" 若E=Sum[i=0 to n](E[i]*2**i)，0<=E[i]<=1";
m_Text+="\r\n";
m_Text+=" D=1";
m_Text+="\r\n";
m_Text+=" FOR i=n TO 0";
m_Text+="\r\n";
m_Text+=" D=D*D % N";
m_Text+="\r\n";
m_Text+=" IF E[i]=1";
m_Text+="\r\n";
m_Text+=" D=D*C % N";
m_Text+="\r\n";
m_Text+=" RETURN D";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+=" 剩下的問題就是乘模運算了，對于A*B % N，如果A、B 都是1024位的大數，先計";
m_Text+="\r\n";
m_Text+="算A*B，再% N，就會產生2048位的中間結果，如果不采用動態內存分配技術就必須將";
m_Text+="\r\n";
m_Text+="大數定義中的數組空間增加一倍，這樣會造成大量的浪費，因為在絕大多數情況下不";
m_Text+="\r\n";
m_Text+="會用到那額外的一倍空間，而采用動態內存分配技術會使大數存儲失去連續性而使運";
m_Text+="\r\n";
m_Text+="算過程中的循環操作變得非常繁瑣。所以計算的首要原則就是要避免計算A*B。";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+=" 由于：";
m_Text+="\r\n";
m_Text+=" A*B=A*(Sum[i=0 to n](B[i]*0x100000000**i))";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+=" 所以：";
m_Text+="\r\n";
m_Text+=" A*B % N = (Sum[i=0 to n]((A*B[i])*0x100000000**i)) % N";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+=" 可以用一個循環求得：";
m_Text+="\r\n";
m_Text+=" C=0;";
m_Text+="\r\n";
m_Text+=" FOR i=0 to n";
m_Text+="\r\n";
m_Text+=" C=C+A*B[i]*0x100000000 % N";
m_Text+="\r\n";
m_Text+=" RETURN C";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+=" 事實上，有一種蒙哥馬利算法能夠更快地完成多次循環的乘模運算，但是其原理";
m_Text+="\r\n";
m_Text+="涉及較多的數論知識，且實現起來比較麻煩，對速度雖有提高，經測試也不會超過一";
m_Text+="\r\n";
m_Text+="個數量級，所以暫且不予考慮。";
m_Text+="\r\n";
m_Text+="\r\n";
m_HelpRsa.SetWindowText(m_Text);
break;
case 10:
m_Text="";
m_Text+="\r\n";
m_Text+=" 數論學家利用費馬小定理研究出了多種素數測試方法，目前最快的算法是拉賓米";
m_Text+="\r\n";
m_Text+="勒測試算法，其過程如下：";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+="（1）計算奇數M，使得N=(2**r)*M+1";
m_Text+="\r\n";
m_Text+="（2）選擇隨機數A<N";
m_Text+="\r\n";
m_Text+="（3）對于任意i<r，若A**((2**i)*M) MOD N = N-1，則N通過隨機數A的測試";
m_Text+="\r\n";
m_Text+="（4）或者，若A**M MOD N = 1，則N通過隨機數A的測試";
m_Text+="\r\n";
m_Text+="（5）讓A取不同的值對N進行5次測試，若全部通過則判定N為素數";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+=" 若N 通過一次測試，則N 不是素數的概率為 25%，若N 通過t 次測試，則N 不是";
m_Text+="\r\n";
m_Text+="素數的概率為1/4**t。事實上取t 為5 時，N 不是素數的概率為 1/128，N 為素數的";
m_Text+="\r\n";
m_Text+="概率已經大于99.99%。";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+=" 在實際應用中，可首先用300—500個小素數對N 進行測試，以提高拉賓米勒測試";
m_Text+="\r\n";
m_Text+="通過的概率，從而提高測試速度。而在生成隨機素數時，選取的隨機數最好讓 r=0，";
m_Text+="\r\n";
m_Text+="則可省去步驟（3） 的測試，進一步提高測試速度。";
m_Text+="\r\n";
m_Text+="\r\n";
m_HelpRsa.SetWindowText(m_Text);
break;
case 11:
m_Text="";
m_Text+="\r\n";
m_Text+=" 大數的輸入輸出是通過字符串來完成的，事實上很容易實現，例如按照十進制格";
m_Text+="\r\n";
m_Text+="式進行處理，則：";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+=" 輸入：";
m_Text+="\r\n";
m_Text+=" X=0";
m_Text+="\r\n";
m_Text+=" FOR i=0 TO n";
m_Text+="\r\n";
m_Text+=" X=X*10";
m_Text+="\r\n";
m_Text+=" X=X+(int)(str[n]-48)";
m_Text+="\r\n";
m_Text+=" RETURN X";
m_Text+="\r\n";
m_Text+="\r\n";
m_Text+=" 輸出：";
m_Text+="\r\n";
m_Text+=" str=""";
m_Text+="\r\n";
m_Text+=" WHILE(X>0)";
m_Text+="\r\n";
m_Text+=" str=(char)(X%10-48)+str";
m_Text+="\r\n";
m_Text+=" RETURN str ";
m_Text+="\r\n";
m_Text+="\r\n";
m_HelpRsa.SetWindowText(m_Text);
break;
}
*pResult = 0;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -