素性测试

判断一个数$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

总结

以上是生活随笔为你收集整理的素性测试的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。