Miller-Rabin算法本质上是一种概率算法存在误判的可能性，但是出错的概率非常小出错的概率到底是多少，存在严格的理论推导

• 当然反过来不一定成立。即当ap?1%p=1时p未必是质数。但是这个概率比较小所以利用费尔马小定理来检测素数的判定及素数嘚相关定理，不能保证时刻都对只能保证出错的概率比较小。
  给定正整数n问n是否为质数（显然只需判断正奇数），最基本的做法就是計算2n?1%n是否为1如果不是1，n肯定为合数；否则n可能为质数。

• 如果p是一个奇质数且e≥1则方程
  
  仅有两个根x=1或者x=?1，注意到在模p的意义下x=?1等价于x=p?1，±1也称为1的平凡平方根
• 很容易有一个推论如果对模n存在1的非平凡平方根，n一定是合数

利用上面两个定理就可以构造出Miller-Rabin算法。考虑到n肯定是奇数(偶数的情况自己想去)则n一定可以表示为n?1=2s?d，其中s≥1且d是奇数则

的情况进行说明（所有运算都是在模n的意义下，以下的文字说明省略了这一点）任取一个

的平方根（废话），根据平方根定理的推论如果

肯定是合数。最后根据费尔马小定理，洳果

为了增加得到正确判断的概率可以将

重复取不同的值，对每一个

的过程不过，考虑到ACM的特殊性测试数据应该不会选择伪素数的判定及素数的相关定理特别是强伪素数的判定及素数的相关定理。所以很多题目的AC程序实际上只来一次即可