蒙特卡罗(费尔马小定理二次探测联合算法判定1-200内的素数)算法的思想、原理和步内容假如p是质数，且gcd(a,p)=1，那么a(p-1)≡1（mod p）。
证明先证两个引理：①：若a,b,c为任意3个整数,m为正整数,且(m,c)=1,则当ac≡bc(mod m)时,有a≡b(mod m)（这个很显然吧。
）②：设m是一个整数,且m>1,b是一个整数且(m,b)=1.如果a[1],a[2],a[3],a[4],…a[m]是模m的一个完全剩余系,则ba[1],ba[2],ba[3],ba[4],…ba[m]也构成模m的一个完全剩余系.证明：若存在ba[i]、ba[j]使得bai≡baj(mod m)bai≡baj(mod m)，则ai≡aj(mod m)ai≡aj(mod m)。
然而根据完全剩余系的定义可知这并不存在。
然后再来证明费马小定理：构造P的完全剩余系：{1,2,3…,p−1}{1,2,3…,p−1}因为(a,p)=1(a,p)=1，根据引理②可得{a,2a,3a…,n}{a,2a,3a…,n}也是P的完全剩余系。
由完全剩余系的性质可得：(p−1)!≡(p−1)!ap−1(mod p)(p−1)!≡(p−1)!ap−1(mod p)两边同时除以(p−1)!(p−1)!，得ap−1≡1(mod p)ap−1≡1(mod p)证毕。
应用费马小定理是逆元的求解方法之一。
还可以快速计算形如ab≡c (mod p)ab≡c (mod p)这样的东西（当然p要是质数）还有就是MR素数判断MR素数判断一般的素数判断用的是筛法。
但是当素数比较大时，可能就无能为力了（判单个数最快是n−−√n）这时我们就可以考虑MR素数判断。
全名：Miller-Rabin素数测试，利用费马小定理判断一个数是否是质数。
当p为素数时，ap−1≡1(mod p)ap−1≡1(mod p)，而当p不为素数时，上式有很大概率不成立。
