判断素数的方法(Miller_Rabin)

大家好，我是讯享网，很高兴认识大家。

序言

willson定理：https://blog.csdn.net/fengqiyuka/article/details/
普通篇：https://blog.csdn.net/fengqiyuka/article/details/

背景

“还有没有判断素数的方法？”
“当然有，那就是Miller_Rabin！”
这个算法能做到 $O (l o g n)$ 级别，但是相较于普通的 $O(\sqrt n)$ 以及willson定理所需要的神奇的快速求阶乘相比，它的优势也是十分明显的。
但，这一个算法有一个局限性。就是它不能做到判断所有的素数。
这时候就有人开始担心了——这么个正确性玄学的算法，用起来都觉得不安心！
可是，我们要知道，在一般的题目中，我们最多就只会判断大小在long long（大约在 $1,10^{19}]$ ）范围内的素数。在一个这么小的范围内，它的正确性可以达到100%。

必备的定理

费马小定理

若 $p$ 是质数， $\mod p \neq 0$ ，那么 $a^{p-1} \equiv 1(\mod p)$ 。
具体的证明可以考虑用剩余系，把 $[1, p - 1]$ 的数用形如 $k * a$ 的数来代替。
而 $k$ 的集合本身也是 $[1, p - 1]$ 。

二次探测定理

若存在 $a$ ，使 $a^2 \equiv 1 (\mod p)$ , $\mod p \ne -1$ 且 $a\mod p\ne 1$ ，则 $p$ 是质数。
证明可以考虑反证法， $\equiv 0(\mod p)$ ，发现这样是与 $p$ 为质数矛盾。故定理成立。

Miller_Rabin

我们可以用费马小定理和二次探测定理的“逆定理”来做。
这里之所以要打双引号，是因为它们的条件只具备必要性，是没有逆定理的。
但这样正确性不就玄学了吗？
上面已经说过了，在小范围内正确的概率就会升到100%。
关键是如何提升概率。
显而易见的，我们可以选取多个 $a$ ，但注意一定要是素数，不然的话有可能不会满足费马小定理中 $a$ 与 $p$ 不是倍数关系的条件。
对于每一个 $a$ ，我们就用“逆定理”来反过来推断该数是不是素数。
具体流程是这样的：
选取素数{2,3,5,7,…}
对于待测数 $p$ ，设 $p - 1$ = $2^s*t$ ， $t$ 为奇数，先求出 $d=a^t$ 。
不断平方，若平方到 $- 1$ ，则二次探测定理已经无效了，直接用费马小定理判断。
若在没有出现过 $- 1$ 的情况下平方到 $1$ ，则说明 $p$ 为合数。
若知道平方到 $a^{p-1}$ 也没有出现1，则不符费马小定理， $p$ 为合数。
其余情况，则说明 $p$ 有可能数素数，选取下一个 $a$ 判断。
若所有 $a$ 都试过，没有出现能说明 $p$ 一定为合数的情况是，认定 $p$ 为素数。

其它

一般来说，a选9个就绝对没有问题了。
如果待测数太大，要用快速乘，则时间复杂度退化到 $O(log^2n)$ ，但跑的还是不错的。

代码

#include<cstdio> #include<cstring> using namespace std; typedef long long ll; int a[10]={2,3,5,7,11,13,17,19,23,29}; ll mi(ll x,ll t,ll mod){ ll d=1; while(t){ if(t%2) d=d*x%mod; x=x*x%mod;t/=2; } return d; } bool check(ll x){ if(x==1) return false; ll t=x-1;int p=0; while(t%2==0) t/=2,p++; for(int i=0;i<=9;i++){ if(a[i]==x) return true; ll t2=mi(a[i],t,x); for(int j=1;j<=p;j++){ if(t2==x-1) {t2=mi(a[i],x-1,x);break;} ll t3=mi(t2,2,x); if(t3==1&&t2!=1&&t2!=x-1) return false; t2=t3; } if(t2!=1) return false; } return true; } int main() { ll n;scanf("%lld",&n); if(check(n)) printf("YES\n"); else printf("NO\n"); return 0; }

讯享网

总结

素数的世界如此精彩，我们的探索将会一直继续！

（完）

讯享网

判断素数的方法(Miller_Rabin)

序言

背景

必备的定理

费马小定理

二次探测定理

Miller_Rabin

其它

代码

总结

相关推荐