Miller-Rabin素性测试算法详解 ——定理

代码图片来自：https://blog.csdn.net/ECNU_LZJ/article/details/72675595

两个引理

证明过程：

代码不是完整的一道题目，只涉及了素数测试的部分

This is the code

typedef long long int ll;ll mod_mul(ll a, ll b, ll mod)//快速乘积求模
{ll res = 0;while (b){if (b & 1)res = (res + a) % mod;a = (a + a) % mod;b >>= 1;}return res;
}
ll mod_pow(ll a, ll n, ll mod)//快速幂求模
{ll res = 1;while (n){if (n & 1)res = mod_mul(res, a, mod);a = mod_mul(a, a, mod);n >>= 1;}return res;
}
bool Miller_Rabin(ll n) // Miller-Rabin随机算法检测n是否为素数
{if (n == 2)return true;if (n < 2 || !(n & 1))return false;ll m = n - 1, k = 0;while (!(m & 1)){k++;m >>= 1;}for (int i = 1; i <= 20; i++)  // 20为Miller-Rabin测试的迭代次数，10次左右就OK了{ll a = rand() % (n - 1) + 1;ll x = mod_pow(a, m, n);ll y;for (int j = 1; j <= k; j++){y = mod_mul(x, x, n);if (y == 1 && x != 1 && x != n - 1)return false;x = y;}if (y != 1)return false;}return true;
}