Miller-Rabin & Pollard-Rho 算法笔记

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)\)。代码太毒瘤,我就不放了(被卡常卡的心态很崩)。

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

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