素数判定法——MR素性测试

这是一个随机性算法，有可能会被卡！！！

素数是数论中地位突出的一个环节，对于素数的判断同样是研究不断，在我之前的博文中已经简单的说过了欧拉筛，这是一种确定性算法，可以保证得到的结果是准确的，并且在多组数据的判断中很占优势，但其本身的空间复杂度仍是难以处理的一点

而MR素性测试则是很好的处理了这一点，在针对离散型数据的素数判断中在时间与空间上有很大的优势，因为其本身是是从结论的角度去进行的验证性算法。

先说理论，本质是小费马定理的逆运用

/*
 * @Author: Gehrychiang
 * @LastEditors  : Please set LastEditors
 * @Website: www.yilantingfeng.site
 * @E-mail: gehrychiang@aliyun.com
 */
#include <bits/stdc++.h>
using namespace std;

long long fastMul(long long a, long long b, long long mod) //a*b % mod
{
    long long res = 0;
    while (b)
    {
        if (b & 1)
        {
            res = (res + a) % mod;
        }
        a = (a + a) % mod;
        b >>= 1;
    }
    return res;
}

long long fastPowMod(long long a, long long n, long long mod) //a^n % mod
{
    if (n == 0 && a != 0)
        return 1;
    if (n != 0 && a == 0)
        return 0;
    long long base = a;
    long long res = 1;
    while (n)
    {
        if (n & 1)
        {
            res = fastMul(res, base, mod);
        }
        base = fastMul(base, base, mod);
        n >>= 1;
    }
    return res % mod;
}

bool mr_test(long long n, long long a, long long d)
{
    if (n == 2) //n是2
        return true;
    if (n % 2 == 0) //n为偶数
        return false;
    if (n == a) //二者相等了，其实这种情况并不会出现，已经在组测试中得到了True的返回值
        return false;
    //  存在某个i使得a^(d*2^i) mod n=n-1  i>=0
    while (!d & 1) //确保d为奇数
    {
        d >>= 1; // d/=2
    }
    long long t = fastPowMod(a, d, n);
    while (d != n - 1 && t != n - 1 && t != 1)
    {
        t = fastMul(t, t, n);
        d <<= 1; // d*=2  这里用来还原前面的取成奇数的过程也就是把d朝n-1复原的过程
    }
    return t == n - 1 || t == 1; //如果最后我们的可以等于n-1或是为1那么就是通过了这一组测试
}

bool mr_test_grp(long long n)
{
    if (n == 1)
        return false;
    int a[10] = {2, 3, 5, 7, 11, 13, 17, 19, 47, 61};
    for (int i = 0; i < 10; i++)
    {
        if (n == a[i])
            return true;
        if (!mr_test(n, a[i], n - 1)) //有一组没通过素性测试
            return false;
    }
    //更多的随机数样本测试，一般来说，工业级代码需要要求通过1k组以上的测试才能保证判断的准确性
    // srand(5201314);
    // for (int i = 0; i < 33; i++)
    // {
    //     long long r=rand()%(n-1)+1;
    //     if(n==r)
    //     return true;
    //     if(!mr_test(n,r,n-1))
    //     return false;
    // }

    return true; //全部通过  此时大概率是素数
}
int main()
{
    long long n;
    cin >> n;
    if (mr_test_grp(n))
    {
        cout << "yes" << endl;
    }
    else
    {
        cout << "no" << endl;
    }

    return 0;
}