aks演算法

A. 如何知道一個很大的數是不是素數

高速判斷用 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 plainprint?

1. /*計算n^p*/
2. unsigned power(unsigned n,unsigned p)
3. {
4. for(int i=0;i<p;i++) n*=n;
5. return n;
6. }

/*計算n^p*/
unsignedpower(unsignedn,unsignedp)
{
for(inti=0;i<p;i++)n*=n;
returnn;
}

該死的乘法，是時候優化一下了！把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