Miller-rabin算法


费马素性检验

根据费马小定理,如果p是素数,则$a^{p-1}≡1(\ mod\ p)$ 对所有的 $a∈[1,n-1] $ 成立

。所以如果在 [1,n-1] 中随机取出一个 a,若发现不满足费马小定理,则证明n必为合数。

注意!!!如果整数 a 不是 p 的倍数,且 $ a^{p-1}\equiv 1\pmod p $,那么 p 也不一定是一个素数

一个反例就是著名的 Carmichael 数。这一类数可以通过所有的费马素性检验,但它们是合数。所以费马素性检验是概率性的。但 Carmichael 数是很稀少的(最小的是561),所以该种方法可以在大部分情况下做出正确的判断。
选择一些比较小的数作为 a ,并依次带入费马小定理中。注意要多选一些,以使得正确率更大。只要有一个不通过就判定为合数。如果全部通过,则将该数判定为素数。

bool primecheck(int p)
{
	for(int i=2;i<=10;i++)
		if(pow(i,p-1)%p!=1)//费马小定理
			return false;
	return true;
}

Miller-rabin算法

二次探测


  1. 1.对于质数 p 满足 $φ(p)=p-1$

如果本文帮助到了你,帮我点个广告可以咩(o′┏▽┓`o)


评论
  目录