Miller_Rabin整理笔记

问题

一个数到底是不是素数

别的

首先列一下我们可以求素数的东西
根号暴力求
\(O(nloglogn)\)的埃氏筛
\(O(n)\)的欧拉筛
还有我们要学习的Miller_Rabin算法
对了，还有神奇的6倍法(也许叫这个吧)

bool pd(int x) {
    if(x==2||x==3) return 1;
    if(x==1||x%6!=1&&x%6!=5) return 0;
    for(int i=5;i*i<=x;i+=6)
        if(x%i==0||x%(i+2)==0) return 0;
    return 1;
}

正事

先去掉偶合数和2吧，现在剩下奇数了吧
费马小定理对素数一定成立，但合数是不一定成立的，多试几次成立几率还是挺

大的，没啥说的
\(Carmichael\)数本身是合数,而且\(1\)到\(n-1\)都满足飞马小定理,suah as:561
着重说一下二次探测吧
考虑\(x^{2}≡1(mod n)\)的根，如果n为奇素数，那跟就只有1和-1两个根(移项之后显然)
设\(n-1=2^{r}*d\),d是奇数，如果存在\(0≤k＜r，a^{2^{k}*d}≠1，-1(mod n)\)
但是\(a^{2^{k+1}*d}≡1（mod n）\),那就不满足费马小定理，那么n就是合数了
凭借着二次探测和费马小定理，我们出错的几率就大大降低了
但只测一次错误还是不够(应该是一次失败的几率是四分之一)
我们用前10个素数，在OI界就可以无忧了
复杂度\(O(k*logn)\)
不知道百度百科搞得什么鬼,好多log

使用快速傅里叶变换能够将这个时间推进到\(O(klognlog lognlog log logn) ="O"(klogn).\)

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL q_pow(LL a, LL k, LL p) {//calc a^k % p
    LL res = 1;
    for (; k ; k >>= 1, a = a * a % p)
        if (k & 1) res = a * res % p;
    return res;     
}
int prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
bool detective(LL a, LL n) {
    int r = 0; LL d = n - 1; // n - 1 = 2 ^ r * d
    while (d % 2 == 0) d >>= 1, ++r;
    for (LL x = q_pow(a, d, n), y; r ; r--) {
        y = x * x % n;
        if (y == 1) {
            if (x == 1) return true;
            if (x == n - 1) return true;
            return false;
        }
        x = y;
    }
    return false;
}
bool miller_rabin(LL n) {
    for (int i = 0; i < 10; i++) {
        if (n == prime[i]) return true;
        if (n % prime[i] == 0) return false;
        if (!detective(prime[i], n)) return false;
    }
    return true;
}
int main() {
    LL wo,n,x;
    cin>>wo>>n;
    while(n--) {
    cin>>x;
        if (miller_rabin(x)) printf("Yes\n");
        else printf("No\n");
    }
}