????? 費馬小定理是初等數論四大定理（威爾遜定理，歐拉定理（數論中的歐拉定理，即歐拉函數），中國剩余定理和費馬小定理）之一，在初等數論中有著非常廣泛和重要的應用。實際上，它是歐拉定理的一個特殊情況。

????? 其內容為： 假如p是質數，且GCD(a,p)=1，那么 a^(p-1) ≡1（mod p）（假如p是質數，且a,p互質，那么 a的(p-1)次方除以p的余數恒等于1）

????? 證明：大數取余的公式 (a*b)%mod =(a%mod * b%mod) %mod, 設P為素數 那么? (a*k) %p =(a%p*k) % P?? [1<=k<=p-1]? ;a%p=c是個定值，由于p是個素數，所以(a%p*k) % P的值互不相同，如果存在 (c*i) %p == (c*j) %p? (i<j) 那么 c*i +p*t == c*j ,? 說明 c = a%p 可以被 p 整除 ，顯然不成立； (a*k) %p的值在[1,p-1]中取，既然互不相同，所以 (a*k) %p的值覆蓋了 [1,p-1] 中的所有數，則 (a*1) %p * (a*2) %p * (a*3) %p * ... * (a*(p-1)) %p = 1*2*3*...*(p-1) =(a^(p-1))%p *1*2*3*...*(p-1)? ==> (a^(p-1))%p=1 證畢。

???? 用費馬小定理的逆命題可以來判定素數，但是其逆命題不一定成立，所以有一定的概率，需要多次測試來減小出錯的概率。每次測試隨機取一個正整數a,要保證 GCD(a,p)=1; 用快速冪來計算a^(p-1) 看是否為 1，如果為1則通過這次測試。???? 但是這樣也可能出錯，因為存在稱做Carmichael數的合數，使得對這些合數進行多次測試都能通過，但是它們不是素數。前3個Carmichael數是561,1105,1729。Carmichael數是非常少的。在1~100000000范圍內的整數中，只有255個Carmichael數。利用二次探測定理可以對上面的素數判定算法作進一步改進，以避免將Carmichael數當作素數。

???? 二次探測定理 如果p是一個素數，且0<x<p,則方程x^2≡1(mod p)的解必為 x=1或p-1。

?

1 long long gcd(long long a,long long b) 2 { 3 if (b==0) return a; 4 return gcd(b,a%b); 5 } 6 long long Qpower(long long a,long long b,long long mod) 7 { 8 if (b==1) return a%mod; 9 if (b&1) return ((a%mod)*Qpower(a,b-1,mod))%mod; 10 long long t=Qpower(a,b>>1,mod); 11 long long tt=(t*t)%mod; 12 if (tt==1) // 二次探測 13 { 14 if (t!=1 && t!=mod-1) iff=false; 15 } 16 return tt; 17 } 18 bool ifp(long long p) 19 { 20 int T=30; 21 iff=true; 22 while (T--) 23 { 24 long long a=rand()%10000*rand()+1; //不能取0 25 while (gcd(a,p)!=1){ if (a<p || a%p!=0) return false;a=rand()%1000*rand()+1;} 26 if (Qpower(a,p-1,p)!=1|| !iff) return false; 27 } 28 return true; 29 } 素數判定代碼

?

還有更高效的方法來判定素數。

?

轉載于:https://www.cnblogs.com/wuminye/p/3253078.html

總結

以上是生活随笔為你收集整理的费马小定理与素数判定的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。