miller_rabin大素数随机检测模板

用到两个定理：

1. 费马小定理
2. 二次探测定理

如果 是一个素数, ,则方程 的解为 或 。

对于待检测数 在 中随机选取 次 判断 是否成立 一旦发现不成立则可判定 不是素数 为了提高正确的概率在求 的过程中用到定理二 令 (其中k是奇数) 然后 就相当于 也就是将 平方t次 用 来表示平方i次的结果 如果发现 而 既不等于 也不等于 那么就可以判定 不是素数了 求 的过程用的是快速幂 在用快速幂的过程中还用到了一个大数相乘取模的优化 即化乘法为加法 即模拟两个数相乘的二进制运算过程 每次相加取模 如果

Code：

ll x[1005];
ll multi(ll a, ll b, ll p)
{ //      化乘法为加法
  ll temp = 0;
  while (b)
  {
    if (b & (ll)1)
      temp = (temp + a) % p;
    a = (a << 1) % p;
    b >>= 1;
  }
  return temp;
}
ll qpow(ll a, ll b, ll p)
{ //      快速幂
  ll temp = 1;
  while (b)
  {
    if (b & (ll)1)
      temp = multi(temp, a, p);
    b >>= 1;
    a = multi(a, a, p);
  }
  return temp;
}
int miller_rabin(ll n)
{
  if (n == 0 || n == 1)
    return 0;
  if (n == 2)
    return 1;
  int s = 10;
  ll k = n - 1;
  int t = 0;
  while (!(k & (ll)1))
  {
    t++;
    k >>= 1;
  }; //    k如果不是奇数将k转化为奇数
  while (s--)
  {
    ll a = rand() % (n - 2) + 2; //        随机取值
    x[0] = qpow(a, k, n);
    for (int i = 1; i <= t; i++)
    {
      x[i] = multi(x[i - 1], x[i - 1], n); //     记录平方i次的结果
      if (x[i] == 1 && x[i - 1] != 1 && x[i - 1] != n - 1)
        return 0;
    }
    if (x[t] != 1)
      return 0;
  }
  return 1;
}