rabin演算法
1. 非對稱加密的代表例子有哪些
非對稱加密主要演算法：RSA、Elgamal、背包演算法、Rabin、D-H、ECC（橢圓曲線加密演算法）。
使用最廣泛的是RSA演算法，Elgamal是另一種常用的非對稱加密演算法。
經典的非對稱加密演算法如RSA演算法等安全性都相當高.
非對稱加密的典型應用是數字簽名。
2. Miller Rabin演算法的演算法比較
Miller-Rabin演算法在基於Fermat定理的演算法中是最優秀的，無論從誤判概率還是從速度上看，它都優於其它 Fermat 類演算法，例如 ： Fermat 演算法 、 Lehmann 演算法、 Solovay- Strassen演算法等。Lucas 測試是Pomerance、Selfridge 和 Wagstaff 提出的一種基於Lucas序列的概率素數測試演算法，該演算法一輪消耗的 時間大概相當於6輪Miller-Rabin測試。一輪Lucas 的誤判概率 為4/15，該演算法經過一些改進,一輪的誤判概率達到1/8。這 種演算法在誤判概率和速度的權衡考慮上不如Miller-Rabin 演算法。Grantham-Frobenius 測 試(QFT) 是 Grantham 提出的基於 Frobenius概率素數和Frobenius強概率素數理論的演算法，給定 一組參數(b,c)，誤判概率可以被控制在1/7710以下。時間復雜度是(3+O(1))log2(n)( 以模n乘法為基本操作)，大概相當於3輪Miller-Rabin演算法。這種演算法理論比較艱深，目前只停留在理論研究階段，還不適合現實應用。Adams 和Shanks 提出了一種基於Perrin 序列的演算法，他們演算法的Q和I兩種情況下還沒發現偽素數，沒有考慮演算法 的速度，只是就誤判概率來進行研究，他們的工作主要是側 重數學理論研究，演算法目前還不適合現實應用。
3. Miller Rabin演算法的優化實現
Miller-Rabin演算法最為耗時的步驟在2.2模冪操作和2.3.2 循環。對演算法的優化實現主要集中在對這兩部分運算的優 化。對模冪操作的優化有兩種途徑：減少模冪演算法中的模乘 操作和優化模乘操作。在求模冪的過程中不能先求冪最後一次求模，這樣會產生一個十分巨大的中間結果，造成實際的 不可操作，所以在求模冪的演算法中用模乘代替乘法，使得中 間結果的長度不超過模的長度。對模冪演算法的優化，我們使 用改進的滑動窗口演算法結合Montgomery模乘和模平方演算法。表1給出模冪演算法的比較。 模冪演算法 預先計算 模平方 模乘法 模平方 模乘法 最壞情況 平均情況 平方乘演算法滑動窗口類演算法 改進的滑動窗口演算法 011 02k -32k-1-1 tt-(k-1)≤次數≤t t-(k-1)≤次數≤t t (t/k)-1 (t/k)-1 t/2 t/k(2k-1)/ 2kk≤t/k(2 -1)/ * 模冪演算法比較，其中k是窗口大小，根據情況 選擇以達到最優，t是指數的二進制位數。 優化的模冪演算法描述：輸入： x，e=(e tet-1?e1e0)2，其中et=1，k≥1( 窗口大小)輸出： xe mod n1、預計算1.1、x1← MontMul(x， R2，n)，x2←MontSqu(x 1， n)1.2、對i 從1 到2k-1-1計算x2i+1←MontMul(x2i-1， x2，n)2、A←R，i ←t3、 當i≥ 0時作下面的操作： 3.1、如果ei=0，A←MontSqu(A ，n)，i← i-13.2、否則找到最長的位串eiei-1?es使得i-s+1≤k並且es=1,計算3.2.1、A <－A2i-s+1 ， (利 用MontSqu函數計算)3.2.2、A <－A*X(ee ...e )2 ，(利 用MontMul函數計算)3.2.3、i ←s-14、A←MontMul(A ，1 ，n)5、返回A其中MontMul(x,y,n) 是Montgomery模乘函數，函數輸出 結果為x*y*R-1 mod n，MontSqu(x,n) 是Montgomery模平方函 數，輸出結果為x2R-1 mod n。模乘演算法如果採用大整數乘法 和除法求模乘，因為涉及耗時的除法操作，所以要相對較 慢，結合大整數乘法和Barrett求模演算法可以用2(n2+3n+1) 步 單精度乘法完成。使用Montgomery求模演算法結合大整數乘法 演算法，可以 在 2n(n+1) 步單精度乘法內完成演算法。 Montgomery模平方的操作可以在3n(n+1) /2步單精度乘法內 完成，而Barrett模平方需要(3n(n+3)/2+1) 步單精度乘法。結 合改進的滑動窗口演算法和Montgomery類演算法，可以得到目前 非特殊情況下的最優的模冪演算法。在Miller-Rabin演算法的2.3.2循環中的模平方操作我們沒有 使用Montgomery模平方演算法，因為該演算法給出的結果帶有R-1這個參數，在2.3.2循環中處理掉這個參數將占整個循環運 行時間中的很大部分，尤其是在循環的控制參數s 相對較小的時候。我們在這里使用大整數平方演算法結合Barrett求模算 法，2.3.2的循環最壞情況需要(s-1)(3n(n+3)/2+1)步單精度乘法。
4. 什麼是公鑰加密
什麼是公鑰加密
公鑰加密，也叫非對稱（密鑰）加密（public key encryption），屬於通信科技下的網路安全二級學科，指的是由對應的一對唯一性密鑰（即公開密鑰和私有密鑰）組成的加密方法。它解決了密鑰的發布和管理問題，是目前商業密碼的核心。在公鑰加密體制中，沒有公開的是明文，公開的是密文，公鑰，演算法。
常見演算法
RSA、ElGamal、背包演算法、Rabin(Rabin的加密法可以說是RSA方法的特例)、Diffie-Hellman (D-H) 密鑰交換協議中的公鑰加密演算法、Elliptic Curve Cryptography(ECC,橢圓曲線加密演算法)。使用最廣泛的是RSA演算法(由發明者Rivest、Shmir和Adleman姓氏首字母縮寫而來)是著名的公開金鑰加密演算法，ElGamal是另一種常用的非對稱加密演算法。
緣起
該思想最早由雷夫·莫寇(Ralph C. Merkle)在1974年提出，之後在1976年。狄菲(Whitfield Diffie)與赫爾曼(Martin Hellman)兩位學者以單向函數與單向暗門函數為基礎，為發訊與收訊的兩方創建金鑰。
非對稱
是指一對加密密鑰與解密密鑰，這兩個密鑰是數學相關，用某用戶密鑰加密後所得的信息，只能用該用戶的解密密鑰才能解密。如果知道了其中一個，並不能計算出另外一個。因此如果公開了一對密鑰中的一個，並不會危害到另外一個的秘密性質。稱公開的密鑰為公鑰;不公開的密鑰為私鑰。
如果加密密鑰是公開的，這用於客戶給私鑰所有者上傳加密的數據，這被稱作為公開密鑰加密(狹義)。例如，網路銀行的客戶發給銀行網站的賬戶操作的加密數據。
如果解密密鑰是公開的，用私鑰加密的信息，可以用公鑰對其解密，用於客戶驗證持有私鑰一方發布的數據或文件是完整准確的，接收者由此可知這條信息確實來自於擁有私鑰的某人，這被稱作數字簽名，公鑰的形式就是數字證書。例如，從網上下載的安裝程序，一般都帶有程序製作者的數字簽名，可以證明該程序的確是該作者(公司)發布的而不是第三方偽造的且未被篡改過(身份認證/驗證)。
5. 關於素數檢驗的米勒拉賓演算法的C++實現
Miller-Rabin演算法是基於費馬定理的：
如果n為質數，(a,n)=1 那麼 a^(n-1)=1 (mod n)
Miller-Rabin演算法就是費馬定理反向的使用：
如果有足夠多的a，(a,n)=1 使a^(n-1)=1 (mod n)都成立
那麼n為質數
但是並不是一個完美的演算法，
如果以2,3,5,7為底，在2.5*10^13以內只有3215031751這一個數是判斷錯誤的
因為A^B可以在logB的時間復雜度內運算完
所以Miller-Rabin演算法的復雜度O(logn)比起樸素O(sqrt(n))快上了非常多
程序：(你可以讓p數組隨機，不一定要用2,3,5,7為底）
const
p:array[1..4] of integer=(2,3,5,7);
var
n,i:longint;
f:boolean;
function exp(a,b:longint):longint; //計算a^b除以n的余數
var
t:qword;
begin
if b=0 then exit(1);
if b=1 then exit(a mod n);
t:=sqr(exp(a,b div 2)) mod n;
if b mod 2=1 then t:=t*a mod n;
end;
begin
readln(n);
f:=true;
for i:=1 to 4 do
if exp(p[i],n-1)<>1 then
begin
f:=false;
break;
end;
if f then writeln('YES') else writeln('NO');
end.
其中，需要自行判斷n為1,2,3,5,7的情況（一開始加個if就行）
這個程序能處理出longint內所有>7的素數