个很多世纪没有解决的基本问题OAKS算法的最重要之处就是
它是相当简单的,不需要特殊的椭圆曲线数学及类似知识。
AKS算法不是其他人工作的简单推广,它摒弃了把已有的方法
集中到一起的想法,而是探素使用简单的代数概念来解决问题
的方法。尽管思想是简单的,但是非常有创造性。然而,这个算
法目前可能不会有太多的实际应用。这是因为算法的运行时间
是0((log n)}),与Miller和Rabin设计的概率测试的0(log rz)
运行时间相比是相形见咄的。研究者们注意到如果某个猜想被
证明,算法可以在0((logn)')时间内运行,这样的改善将促进
实际的应用。研究者们还证明如果Sophie Germain素数具有期
望的分布,那么在时间估计中的指数12可以减少到5。当然如
果发现素数的分布并非如此,那将会有很大区别。
AKS算法最重要的意义是作为一个理论结果,为这一领域
的研究奠定了基础。之后在技术上将会进行改进与完善,使之
更为实用。
高速判断用 miller-rabin算法或者 aks 算法
1.约定x%y为x取模y,即x除以y所得的余数,当x<y时,x%y=x,所有取模的运算对象都为整数。
x^y表示x的y次方。乘方运算的优先级高于乘除和取模,加减的优先级最低。
见到x^y/z这样,就先算乘方,再算除法。
A/B,称为A除以B,也称为B除A。
若A%B=0,即称为A可以被B整除,也称B可以整除A。
A*B表示A乘以B或称A乘B,B乘A,B乘以A……都一样。
2.费马小定理:有N为任意正整数,P为素数,且N不能被P整除(显然N和P互质),则有:N^P%P=N(即:N的P次方除以P的余数是N)。
但是我查了很多资料见到的公式都是这个样子:
(N^(P-1))%P=1后来分析了一下,两个式子其实是一样的,可以互相变形得到。
原式可化为:(N^P-N)%P=0(即:N的P次方减N可以被P整除,因为由费马小定理知道N的P次方除以P的余数是N)把N提出来一个,N^P就成了你N*(N^(P-1)),那么(N^P-N)%P=0可化为:
(N*(N^(P-1)-1))%P=0
请注意上式,含义是:N*(N^(P-1)-1)可以被P整除
又因为N*(N^(P-1)-1)必能整除N(这不费话么!)
所以,N*(N^(P-1)-1)是N和P的公倍数,小学知识了^_^
又因为前提是N与P互质,而互质数的最小公倍数为它们的乘积,所以一定存在
正整数M使得等式成立:N*(N^(P-1)-1)=M*N*P
两边约去N,化简之:N^(P-1)-1=M*P
因为M是整数,显然:N^(P-1)-1)%P=0即:N^(P-1)%P=1
2.费马小定理:有N为任意正整数,P为素数,且N不能被P整除(显然N和P互质),则有:N^P%P=N(即:N的P次方除以P的余数是N)。
但是我查了很多资料见到的公式都是这个样子:
(N^(P-1))%P=1后来分析了一下,两个式子其实是一样的,可以互相变形得到。
原式可化为:(N^P-N)%P=0(即:N的P次方减N可以被P整除,因为由费马小定理知道N的P次方除以P的余数是N)把N提出来一个,N^P就成了你N*(N^(P-1)),那么(N^P-N)%P=0可化为:
(N*(N^(P-1)-1))%P=0
请注意上式,含义是:N*(N^(P-1)-1)可以被P整除
又因为N*(N^(P-1)-1)必能整除N(这不费话么!)
所以,N*(N^(P-1)-1)是N和P的公倍数,小学知识了^_^
又因为前提是N与P互质,而互质数的最小公倍数为它们的乘积,所以一定存在
正整数M使得等式成立:N*(N^(P-1)-1)=M*N*P
两边约去N,化简之:N^(P-1)-1=M*P
因为M是整数,显然:N^(P-1)-1)%P=0即:N^(P-1)%P=1
2.费马小定理:有N为任意正整数,P为素数,且N不能被P整除(显然N和P互质),则有:N^P%P=N(即:N的P次方除以P的余数是N)。
但是我查了很多资料见到的公式都是这个样子:
(N^(P-1))%P=1后来分析了一下,两个式子其实是一样的,可以互相变形得到。
原式可化为:(N^P-N)%P=0(即:N的P次方减N可以被P整除,因为由费马小定理知道N的P次方除以P的余数是N)把N提出来一个,N^P就成了你N*(N^(P-1)),那么(N^P-N)%P=0可化为:
(N*(N^(P-1)-1))%P=0
请注意上式,含义是:N*(N^(P-1)-1)可以被P整除
又因为N*(N^(P-1)-1)必能整除N(这不费话么!)
所以,N*(N^(P-1)-1)是N和P的公倍数,小学知识了^_^
又因为前提是N与P互质,而互质数的最小公倍数为它们的乘积,所以一定存在
正整数M使得等式成立:N*(N^(P-1)-1)=M*N*P
两边约去N,化简之:N^(P-1)-1=M*P
因为M是整数,显然:N^(P-1)-1)%P=0即:N^(P-1)%P=1
3.积模分解公式先有一个引理,如果有:X%Z=0,即X能被Z整除,则有:(X+Y)%Z=Y%Z
设有X、Y和Z三个正整数,则必有:(X*Y)%Z=((X%Z)*(Y%Z))%Z
想了很长时间才证出来,要分情况讨论才行:
1.当X和Y都比Z大时,必有整数A和B使下面的等式成立:
X=Z*I+A(1)
Y=Z*J+B(2)
不用多说了吧,这是除模运算的性质!
将(1)和(2)代入(X*Y)modZ得:((Z*I+A)(Z*J+B))%Z乘开,再把前三项的Z提一个出来,变形为:(Z*(Z*I*J+I*A+I*B)+A*B)%Z(3)
因为Z*(Z*I*J+I*A+I*B)是Z的整数倍……晕,又来了。
概据引理,(3)式可化简为:(A*B)%Z又因为:A=X%Z,B=Y%Z,代入上面的式子,就成了原式了。
2.当X比Z大而Y比Z小时,一样的转化:
X=Z*I+A
代入(X*Y)%Z得:
(Z*I*Y+A*Y)%Z
根据引理,转化得:(A*Y)%Z
因为A=X%Z,又因为Y=Y%Z,代入上式,即得到原式。
同理,当X比Z小而Y比Z大时,原式也成立。
3.当X比Z小,且Y也比Z小时,X=X%Z,Y=Y%Z,所以原式成立。
=====================================================
4.快速计算乘方的算法如计算2^13,则传统做法需要进行12次乘法。
[cpp] view plaincopyprint? /*计算n^p*/ unsigned power(unsigned n,unsigned p) { for(int i=0i<pi++) n*=n return n } /*计算n^p*/unsigned power(unsigned n,unsigned p)
{
for(int i=0i<pi++) n*=n
return n
}
该死的乘法,是时候优化一下了!把2*2的结果保存起来看看,是不是成了:
4*4*4*4*4*4*2
再把4*4的结果保存起来:16*16*16*2
一共5次运算,分别是2*2、4*4和16*16*16*2
这样分析,我们算法因该是只需要计算一半都不到的乘法了。
为了讲清这个算法,再举一个例子2^7:2*2*2*2*2*2*2
两两分开:(2*2)*(2*2)*(2*2)*2
如果用2*2来计算,那么指数就可以除以2了,不过剩了一个,稍后再单独乘上它。
再次两两分开,指数除以2: ((2*2)*(2*2))*(2*2)*2
实际上最后一个括号里的2 * 2是这回又剩下的,那么,稍后再单独乘上它 现在指数已经为1了,可以计算最终结果了:16*4*2=128