Miller-Rabin 素数测试

首先，强烈推荐阅读这篇文章。（看懂了就不用来了）

Miller-Robin 算法包括两个部分，一个是费马测试，还有一个就是二次探测。这两个东西听上去非常的玄学（的确也是），我来讲清楚，并附上代码。我们现在要进行测试的数是\(p\)。

费马测试与迈克尔数

费马小定理告诉我们，如果一个数\(a\)为质数，那么\(\forall x, x^{a-1} \equiv 1 \; (mod \; a\)。直觉告诉我们我们可以尝试用\([1,a)\)中的数一个一个进行费马测试来检验是否为质数。第一，这样的复杂度仍然是上天的；第二，有一类合数可以通过费马测试，叫做迈克尔数。所以，费马测试存在不正确性。

那么我们怎么进行高效的测试呢？

二次探查

但是我们还可以用到一个这样的定理：

\[\forall x, x^2 \equiv 1 (\mod\; p)\\如果p为质数 \\ 则x的解集只包含x \equiv 1或x \equiv p-1 \\ 否则p是合数。\]

所以，我们可以设\(p – 1 = 2^k x\)。之后，我们可以通过调整\(k\)的值来进行测试，用的就是二次探查和费马测试。我们来用代码具体讨论如何进行这些测试：

bool isPrime(ll p)
{
    // 把 p - 1 设为我们需要的值形式
    ll x = p - 1, k = 0, j;
    while (!(x & 1))
        x >>= 1, k++;
    // 进行随机的素数测试，这是 Miller-Rabin 的核心部分
    for (int i = 0; i <= 4; i++)
    {
        // 用于减少常数的判断
        if (p == bs[i])
            return true;
        // 算出本身的基底以便后期运算
        ll r = quick_pow(bs[i], x, p);
        // 常数判断
        if (r == 1 || r == p - 1)
            continue;
        for (j = 1; j <= k; j++)
        {
            // 重点：
            // 在二次探查中，p - 1 = 2^(kx)，如果
            // 这个出现了意外解，那么 p 就是合数
            r = r * r % p;
            if (r == p - 1)
                break;
        }
        // 判断
        if (j > k)
            return false;
    }
    return true;
}

Pollard-Rho 质因数分解

这个算法也是一个非常毒瘤、随机化的玄学算法。一般的质因数分解算法是试除法，它的时间复杂度为\(O(\sqrt{n})\)。Pollard-Rho 这个算法用随机化用更小的时间复杂度解决分解问题。Crazydave 博客上有一个非常优秀的讲稿（by BigBallon），大家可以去看一看。

这个算法的基础其实是一种玄学算法：随机枚举质因数。对，没错，就是瞎××取随机数来进行试除，也叫作“自我良好算法”。这个算法主要是通过枚举因子进行试除。恩，这个算法的复杂度\(O(上天)\)。

那么如何才能优化这个看上去无法优化的算法呢？玄学算法当然需要玄学优化，这里给大家介绍一个玄学定理，以便加速。

生日悖论

其实这个悖论整篇只说明了一点：

单纯的瞎××取数的概率是\(\frac{1}{n}\)，但是如果我们通过枚举\(k=i-j\)，那么这个取数概率会大大增加。

是的，下面我来描述这个理论。

如果我们进行随机取数，那么我们的取到数概率是\(\frac{1}{n}\)。这个概率太小，但是我们可以枚举两个变量，使得\(k=i-j\)，那么我们取得一个数的可能性就会大大增加，这个可以通过计算机模拟得出（实验数据在讲稿中）。结论就是，当我们进行\(\sqrt{n}\)次枚举，我们的概率就会增大到\(\sqrt{\frac{1}{n}}\)。这是一个非常重要的发现。

回到 Pollard-Rho 算法

我们可以设随机函数\(f(x)=(x^2+c) \mod \; n\)，然后做两个变量\(x,y\)，之后我们可以初始化\(x\)的值，然后以\(x\)做种子对\(y\)进行生成，然后把\(x\)赋值为\(y\)，亦复如是，然后每次循环的时候我们进行差值运算，计算\(gcd(|y-x|,n)\)。代码太毒瘤，我就不放了（被卡常卡的心态很崩）。

Miller-Rabin & Pollard-Rho 算法笔记