判斷一個數$n$是否為素數有很多做法，最常見的是枚舉$i$從$2$到$\lfloor \sqrt{n} \rfloor$，判斷$n$是否都不能被$i$整除，代碼如下：

bool isPrime(long long p){if(p==1)return 0;for(long long i=2;i*i<=p;++i)if(p%i==0)return 0;return 1; }

然而上述算法的復雜度為$O(\sqrt{n})$，對于大數來說，這個時間是無法接受的.

為了解決大數的素性判斷，有了下面的RP算法：Fermat測試.

根據Fermat小定理，若$p$為素數，則對任意$a$必有$a^{p-1} \equiv 1(mod p)$.

故對于一個$a$，若$a^{p-1} \not\equiv 1(mod p)$，則$p$為合數；若$a^{p-1} \equiv 1(mod p)$，則$p$有可能為素數，實際上當$p$為奇數時，$p$是合數的概率小于$\frac{1}{2}$.

于是對于一個奇數$p(p\geqslant 3)$和安全參數$k$：

• 隨機取一個數$n(2 \leqslant n \leqslant p-1)$
• 若$(n,p)\neq 1$，則$p$為合數
• 若$n^{p-1} \not\equiv 1(mod p)$則$p$為合數，否則假定$p$為素數
• 重復上述過程$k$次

假定大數相乘的復雜度為$O(lgn \times lglgn)$，故算法復雜度為$O(k \times lg^2n \times lglgn)$，若測試得到$p$為素數，則準確率為$1-\frac{1}{2^k}$.代碼如下（為了方便高精度運算，用python編寫）：

1 import random 2 3 4 def GCD(a, b): 5 while b: 6 a, b = b, a % b 7 return a 8 9 10 def PowMod(a, n, p): 11 r, t = 1, a 12 while n: 13 if n & 1: 14 r = (r * t) % p 15 t = (t * t) % p 16 n >>= 1 17 return r 18 19 20 def FermatTest(p): 21 if p == 1: 22 return False 23 if p == 2: 24 return True 25 if p % 2 == 0: 26 return False 27 k = 20 28 while k: 29 a = random.randint(2, p - 2) 30 if GCD(a, p) != 1: 31 return False 32 if PowMod(a, p - 1, p) != 1: 33 return False 34 k -= 1 35 return True 36 37 print(FermatTest(int(input())))

Fermat測試的復雜度還能被再次降低。

若$p$為奇數，則有$p-1=2^st$，其中$t$為奇數，則有以下分解式：

$n^{p-1}-1=(n^t-1)(n^t+1)(n^{2t}+1)\times ...\times (n^{s-1}t+1)$

因此，如果有$n^{p-1} \equiv 1(mod p)$，則必有$n^t \equiv 1(mod p)$或者$n^{kt} \equiv -1(mod p)(1 \leqslant k \leqslant s-1)$成立。

故有了Miller-Rabin算法：

• 將$p-1$表示成$2^st$
• 隨機取一個數$n(2 \leqslant n \leqslant p-1)$
• 計算$n^t(mod p)$，若其等于$\pm1$，則假定$p$為素數
• 計算$n^{kt}(mod p)(2 \leqslant k \leqslant s-1)$，若其中有一個等于$-1$，則假定$p$為素數。否則$p$為合數
• 重復上述過程$k$次

若測試得到$p$為素數，則準確率為$1-\frac{1}{4^k}$.代碼如下：

?

1 import random 2 3 4 def GCD(a, b): 5 while b: 6 a, b = b, a % b 7 return a 8 9 10 def PowMod(a, n, p): 11 r, t = 1, a 12 while n: 13 if n & 1: 14 r = (r * t) % p 15 t = (t * t) % p 16 n >>= 1 17 return r 18 19 20 def MillerRabin(p): 21 if p == 1: 22 return False 23 if p == 2: 24 return True 25 if p % 2 == 0: 26 return False 27 s, t = 0, p - 1 28 while t % 2 == 0: 29 t >>= 1 30 s += 1 31 k = 10 32 while k: 33 a = random.randint(2, p - 2) 34 if GCD(a, p) != 1: 35 return False 36 m = PowMod(a, t, p) 37 npass = 1 38 if m == 1 or m == p - 1: 39 npass = 0 40 q = s - 1 41 while npass and q: 42 m = (m * m) % p 43 if m == p - 1: 44 npass = 0 45 q -= 1 46 if npass: 47 return False 48 k -= 1 49 return True 50 51 print(MillerRabin(int(input())))

?

轉載于:https://www.cnblogs.com/barrier/p/6607668.html

總結

以上是生活随笔為你收集整理的素性测试的全部內容，希望文章能夠幫你解決所遇到的問題。

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