判断一个数$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$：
大数相乘的复杂度为$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测试的复杂度还能被再次降低：
原文：http://www.cnblogs.com/barrier/p/6607668.html