Miller_rabin 素数测试
一种用来判断素数的算法。
前置芝士
威尔逊定理
若 \(p\) 为素数，\((p-1)! \equiv -1 (\mod p)\)。
证明：
充分性证明：
如果 \(p\) 不是素数，那么他的因数必定存在于$ 1,2,3,\dots,p−1$ 之中，所以 \(\gcd((p-1)!,p)\)，那么 \((p-1)! \not\equiv -1\)。
必要性证明：
首先，我们知道 $$p-1\equiv -1 (\mod p)$$
那么我们只需要证明 \((p-2)! \equiv 1 (\mod p)\) 就可以了。
设 \(A=\{2,3\dots,p-2\}\)
对于 \(x\in A\)，肯定存在一个 \(a \in A\)，使得 \(ij\equiv 1(\mod p)\)
当 \(x=a\) 时，考虑二次剩余 \(x^2 \equiv 1(\mod p)\)。
移项就可以得到 \((x+1)(x-1) \equiv 0 (\mod p)\)，
那么只有两个解，\(x \equiv 1(\mod p)\),\(x \equiv p-1(\mod p)\)，不成立。
所以其他情况都可以找到对应的 \(a\)。
所以 \((p-2)!\equiv 1(\mod p)\)，\((p-1)!\equiv p-1(\mod p)\)。
费马小定理
若 \(p\in\mathbb{P},\gcd(a,p)=1\)，则 \(a^{p-1}\equiv 1(\mod p)\)，
证明：
因为 \(1,2,3,\dots ,p-1\) 是 \(p\) 的完全剩余系，\(a,p\) 互质，
所以 \(a,2* a,3* a,4* a, \dots (p-1)* a\) 也是 \(\mod p\) 的完全剩余系。
所以 \(1 * 2 * 3 * \dots * (p-1) \equiv a * 2a * 3a * \dots * (p-1)a (\mod p)\)。
就是 \((p-1)! \equiv (p-1)!a^{p-1} (\mod p)\)。
由威尔逊定理得出，\((p-1)! \equiv -1(\mod p)\)，
两边同时约去 \((p-1)!\)，
所以可以得出 \(a^{p-1} \equiv 1(\mod p)\)。
二次探测定理
若 \(p\) 为素数，\(x^2 \equiv 1(\mod p)\)，那么\(x \equiv \pm 1(\mod p)\)。
证明：
原式移项就可以得到 \((x+1)(x-1) \equiv 0 (\mod p)\)，
那么只有两个解，\(x \equiv 1(\mod p)\),\(x \equiv p-1(\mod p)\)。
但是这些又和 Miller_rabin 有什么关系呢？
我们把 \(p-1\) 分解为 \(2^k* t\)，当 \(p\) 是素数时，则有 \(a^{2^k* t} \equiv 1(\mod p)\)。
然后随机出一个数 \(a\)，可以算出 \(a^t\)，然后再自乘，就可以得到 \(a^{2^k* t}\) ，也就是 \(a^{p-1}\)。
但如果我们在自乘之后 \(\equiv 1(\mod p)\)，而之前 \(\not\equiv 1(\mod p)\)，那么就违背了二次探测定理，则 \(p\) 不是素数。
else
\(Zwad\) 告诉我，若 \(p\) 通过一次测试，则p不是素数的概率仅为25%。
那么用 \(2,325,9375,28178,450775,9780504,1795265022\) 这几个数进行判断,在 $long long $ 范围内能保证正确。
Code
例题：SP288 PON - Prime or Not
[code]#include#define int __int128#define N_4 10004#define N_5 100005#define N_6 1000006#define Mod 1000000007#define FOR(i,j,k) for(long long i=j;i=k;--i)using namespace std;inline int read(){ int x=0,f=1; char ch; ch=getchar(); while(ch'9'){ if(ch=='-') f=-f; ch=getchar(); } while(ch>='0'&&ch=1; for(register int i=1;i |
