Miller-Rabin素性测试和Pollard-Rho因子分解

\(\text{Miller-Rabin}\)素性测试

\(\text{Miller-Rabin}\)素性测试分为两步,分别是费马小定理逆定理和二次探查。(算法导论中文版567页,英文版968页)

首先把偶数去掉,下文中的探查对象\(p\)均为奇数。

对于任意整数\(a\)和素数\(p\),有费马小定理:\[a^{p-1}\equiv 1\pmod p\]按照其逆否命题可知如果上式不成立则\(p\)一定不是素数,可是对于一些被称为“伪素数”的数\(n\),\(a\)取遍\(1\cdots n-1\)上式都成立,但是它们是合数。换言之,费马小定理的逆定理不一定成立。

对于通过上述测试的数,\(\text{Miller-Rabin}\)素性测试要追加一步,称为二次探查。

考虑方程 \(x^{2k}\equiv 1\pmod p\) 的解,可以化为 \((x^k+1)(x^k-1)\equiv 0\pmod p\),在\(p\)为素数时解只能为 \(x^k\equiv 1\) 或 \(x^k\equiv p-1\pmod p\),在\(p\)为合数时则有其它解。

所以在 \(a^{p-1}\equiv 1\pmod p\) 成立时,Miller-Rabin会令 \(u=\frac{p-1}{2}\),然后判断是否通过二次探查:即判断 \(a^u\bmod p\) 的值是否等于\(1\)或\(p-1\),或是把\(u\)再提出一个\(2\)的因子变成\(\frac{u}{2}\),然后再进行上述的探查。实际上在实现时会先把\(p-1\)的\(2\)的因子全提出来然后再通过一次次平方来进行分步探查,只要遇到一步满足条件即判断为素数。

素数一定会通过这样的判断;一个合数有\(\frac{1}{4}\)的概率通过这个判断。但是实践证明:对于\(\text{int32}\)范围中的数,使用\(2,7,61\)探测即不会出错;对于\(\text{int64}\)范围中的数,使用前十个素数探测即可。结合代码理解:

ll qpow(ll base, ll exp, ll mod);   // 快速幂,计算 (base^exp)%mod

bool check(ll a, ll p) {
    ll t = 0, k = p - 1;
    while (!(k & 1)) {
        t++;
        k >>= 1;
    }
    ll x = qpow(a, k, p);
    if (x == 1 || x == p - 1)
        return true;
    while (t) {
        x = (x*x) % p;
        if (x == p - 1)
            return true;
        t--;
    }
    return false;
}

bool millerrabin(ll x) {
    return x == 2 || x == 7 || x == 61 || ((x > 2) && (x & 1) && check(2, x) && check(7, x) && check(61, x));
}

\(\text{Pollard-Rho}\)因数分解

\(\text{Pollard-Rho}\)分解算法期望复杂度为\(O(n^{\frac{1}{4}})\),适用于int64范围内的数的分解。它使用一种神秘的随机方法来枚举因子,尝试进行分解。

设被分解数为\(p\),首先运行\(\text{Miller-Rabin}\),如果被分解数是素数则停止。现在我们要枚举一些\(a\)然后计算它们的\(\text{gcd}\),判断这个数是否不是\(1\)。如果可以分解则分成两半继续递归。

考虑一种奥妙重重的枚举方法。先随机一个数,设为 \(x_0\)。递推计算 \(x_i=x_{i-1}*x_{i-1}+c\bmod p\),每次枚举的 \(a\) 即为 \(x_i-x_{0}\)​。观察发现,几次递推后会出现 \(x_i=x_j\) 的情况,此时就停止枚举,返回失败。

为了优化,我们要限制它的递推步数\(k\),而且每\(k\)次递推后就把\(k\)乘以二,然后重新指定新的随机\(x_0\)。由于某种神秘的原因,这个过程很快。

发表评论

电子邮件地址不会被公开。 必填项已用*标注