Miller Rabin 判素算法

未分类
1.2k 词

引入

给出 $t(t\le500)$ 个正整数 $x(x\le2^{63}-1)$，判断 $x$ 是否为质数。

Miller Rabin 素性检验

显然在这个 $x$ 的范围下，试除法判断质数是不行的。

$\mathbf{Miller Rabin}$ 素性检验就是一种用来 判断大数是否为质数 的 随机性 算法。
它在计算机科学中的用途是用来判断工业质数 $(\ge2^{1024}的质数)$，在这个范围下它的判断是否正确存在随机性，但是在 $OI$ 范围下 $(\le 2^{63}-1)$ 确是一种 错误率极低 的 确定性 算法。

在 引入 的问题中，我们可以考虑使用 $\mathbf{Miller Rabin}$ 素性检验来判断质数。
在 $\mathbf{Miller Rabin}$ 素性检验中，我们要先了解它判断素数的理论基础：

  • 费马素性检验
  • 二次探测定理

费马素性检验

费马小定理：

证明：

$考虑P=\{m_1,m_2,m_3,\cdots ,m_{p-1}\}，m_i<p，显然有 m_i\not\equiv m_j\pmod p\\\because \gcd(a,p)=1\\\therefore 对于Q=\{a\cdot m_1,a\cdot m_2,a\cdot m_3,\cdots,a\cdot m_{p-1}\},也有 a\cdot m_i\not\equiv a\cdot m_j\pmod p\~\\利用同余式的性质，我们对这两个两两元素之间不同余的集合联利，得\\\prod\limits_{i=1}^{p-1}a\cdot m_i\equiv \prod\limits_{i=1}^{p-1} m_i\pmod p\\a^{p-1}\prod\limits_{i=1}^{p-1} m_i\equiv \prod\limits_{i=1}^{p-1}m_i\pmod p\\a^{p-1}\equiv 1\pmod p\\证毕$

若对证明中的同余性质仍有不理解，可以看这里

利用费马小定理这个有力的工具，在判断 $x$ 是否为质数时，我们或许会有这么一种思路：对于要判定的 $x$ ，我们随机选择一个与 $x$ 互质的底数 $a$ ，若 $a^{x-1}\equiv 1\pmod x$，则 $x$ 为质数。

此方法被称为费马素性检验。

稍微尝试，好像真的可行诶！但是别着急，这个想法是错误的，因为存在这么一类伪质数 （卡迈克尔数）$x$，也有 $a^{x-1}\equiv 1\pmod x$，但 $x$ 是合数！

因此，单独使用费马素性检验，在小部分情况下会对合数进行误判，所以我们还需要一个关于质数的定理进行二次判断。

二次探测定理

因此，对于每个要判断的 $x$ ,我们都随机选取一个底数 $a<x$，若 $a^2\equiv 1\pmod x$，则判断 $a$ 是否为 $1$ 或 $x-1$，是则 $x$ 大概率是个质数，否则 $x$ 一定不是个质数。

然而，二次探测定理也仍然会出现 “漏洞”，依旧存在一类合数 $x$ 使得任意 $a^2\equiv 1\pmod x$ 时 $a\ne 1$ 且 $a\ne x-1$

那么，费马素性检验和二次探测定理都不可行，是否说明我们要找到第三种 确定性 的定理来判断质数呢？也不需要。

我们可以考虑将费马素性检验与二次探测定理一起使用，对这个数是否为质数进行双重判断。

那么，只有同时满足费马素性检验和二次探测定理的 $x$ 是个质数。这是否一定正确呢？也是无法保证的，存在那么极少的合数，同时满足这两个定理。

但是显然，这种同时满足两个定理的合数，要比满足单一定理的合数要少的多。通俗的说，若一个数 $x$ 满足同时满足两个定理，那么它是质数的概率可以达到 $99\%$。而如果我们对同一个 $x$ 都使用多个不同的底数 $a$ 进行定理验证，那么这个误判的概率将进一步缩小，可以直接忽略。

因此，同时使用费马素性检验和二次探测定理 进行判素在 $OI$ 数据范围内是个正确性保证的确定性算法，同时它也是 $\mathbf{Miller Rabin}$ 素性检验的原理所在。

Miller Rabin 算法

$\mathbf{Miller Rabin}$ 算法，即在程序上实现 $\mathbf{Miller Rabin}$ 素性检验，本质上也是在实现费马素性检验的判断中同时进行二次探测检验。

考虑判断 $x$ 是否为质数，先将 $x-1$ 分解为 $2^k\cdot t，k,t\in \N$
选择一个 $a$ 作为费马和二次探测的底数，然后使 $a^t$ 不断平方，在这个过程中运用二次探测定理检验，即判断是否当 $(a^t)^2\equiv 1\pmod x$ 时 $a^t\equiv \pm 1\pmod x$，否则 $x$ 不是质数。
很显然平方的过程执行 $k$ 次后， $a$ 的指数将变为 $x-1$，此时再运用费马素性检验判断是否 $a^{x-1}\equiv 1\pmod x$,否则 $x$ 不是质数

若 $x$ 在上述过程中都没被 $pass$ 掉，则 $x$ 一定 大概率是个质数。

如果担心算法被卡，我们可以进一步降低误判的概率，使用多组底数 $a$ 进行如上操作验证，只有当所用的所有的底数 $a$ 都可以使得 $x$ 满足两条定理时，$x$ 才是质数。

底数 $a$ 到底怎么取，$\color{Red}wangrx\color{balck}$ 大佬给出了答案：

  • 当 $x\le 2^{32}$ 时，选取 $2,7,612,7,61$ 三个底数即可
  • 当 $x\le 2^{63}$ 时，选取$2,325,9375,28178,450775,9780504,17952650222,325,9375,28178,450775,9780504,1795265022$七个底数即可。

至此，$\mathbf{Miller Rabin}$ 素性检验本是一个带有不确定性的检验方法，但在 $OI$ 数据范围内，我们可以通过增加底数的方式使其成为了一个确定性的算法，因此可以运用于实践当中。

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
#define int __int128
using namespace std;
long long t,x;
long long prime[9]={0,2,3,5,7,11,13,17,37}; //底数取值
int ksm(int a,int b,int mod)
{
	int sum=1;
	while(b)
	{
		if(b&1) sum=sum*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return sum%mod;
}
bool Miller_Rabin(int p,int a)
{
	int k=0,t=p-1,cnt;
	while(!(t&1)) t>>=1,k++;  //找到上述算法流程中的 t 和 k
	a=ksm(a,t,p);
	for(int i=1;i<=k;i++)
	{
		if(a*a%p==1)
		  if(a!=1&&a!=p-1) return false;  //二次探测定理
		 a=a*a%p;
	}
	if(a!=1) return false;  //费马素性检验判断
	return true;
}
bool isprime(int x)
{
	for(int i=1;i<9;i++)  //多次 Miller Rabin 验证
	{
		if(x==prime[i]) return true;
		if(x%prime[i]==0) return false;  //特判掉一些简单情况
		if(!Miller_Rabin(x,prime[i])) return false;
	}
	return true;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	while(t)
	{
		t--;
		cin>>x;
		if(isprime(x)) cout<<"YES"<<'\n';
		else cout<<"NO"<<'\n';
	}
	return 0;
}