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的素数