蒟蒻的数论笔记——素数

Posted on 2018-09-01 Views:

定义：只能被和自身整除的数。

素数的判定

试除法

如果不是素数那么它必定有一个不大于 $\sqrt n$ 的因子，因此我们枚举 $[1, \sqrt n]$ 中的所有数挨个试除即可，时间复杂度 $O(\sqrt n)$ ，虽然慢但是保证正确。

费马判定法

逆用费马小定理，即若为素数则 $a^{n - 1} \equiv 1 \pmod n$ ，对于一个可能的我们尝试不同的并判断是否符合定理，如果不是那么一定不是素数，如果是，那么对于单个的我们正确的概率约为 $1 \over 4$ ，因此我们可以多试几次（比如次），这样基本上就可以保证正确性了。时间复杂度就是快速幂的复杂度 $O(\log n)$ 。

缺点：会被卡迈克尔数干死。如果合数是卡迈克尔数，那么对于所有和互素的，也有 $a^{n - 1} \equiv 1 \pmod n$ ，简而言之就是费马小定理逆定理的反例。最小的卡迈克尔数是 $561 = 3 \times 11 \times 17$ 。虽然这种数很稀少但是，在 $[1, 1 \times 10^8]$ 之间总共有 255 个卡迈克尔数，出题人想干死你还是很简单。

Miller-Rabin 判定法

引理：模素数意义下的平方根模为 $\pm 1$ 。

证明：设此时的平方根为：

$\begin{aligned} x^2 &\equiv 1 &\pmod n\\ x^2 - 1 &\equiv 0 &\pmod n\\ (x + 1)(x - 1) &\equiv 0 &\pmod n\\ \end{aligned}$

因此 $n\mid (x + 1)$ 或 $n\mid (x - 1)$ ，即 $x \equiv \pm1 \pmod n$ ，得证。

对于一个奇素数，偶数 n - 1 一定可以写成 2^sd 的形式，其中是奇数。我们断言对于所有和某个以下两个不等式必有一个成立：

$\begin{aligned} a^d &\equiv 1 &\pmod n \\ a^{2^rd} &\equiv -1 &\pmod n \end{aligned}$

其中 $0 < a < n, 0 \le r < s$ 。

证明：由费马小定理可得 $a^{2^sd} \equiv 1 \pmod n$ ，我们不断地对这个式子两边开根，由引理，如果开出，那么下式成立，如果开了次没开出，则上式成立。

Miller-Rabin 判别法基于以上命题的逆否命题，即如果存在一个，使得 $a^d \not \equiv 1 \pmod n$ 且对于所有的 $0 \le r < s$ 都有 $a^{2^rd} \not\equiv -1 \pmod n$ ，那一定不是素数。反之，就很有可能是素数。

因此，Miller Rabin的工作流程如下：

bool millerRabin(int n) { // n > 3
    int s = 0, d = n - 1;
    while (!(d & 1)) s++, d >>= 1; // 分解s, d
    for (int i = 1; i <= K; i++) { // K 越大越准
        int a = rand() % (n - 3) + 2; // 随机一个[2, n - 2]的a
        int x = qpow(a, d, n); // a^d mod n, qpow快速幂
        if (x == 1 || x == n - 1) continue; // 不满足逆否命题, n - 1是r = 0时的下式
        bool flag = false;
        for (int j = 1; j <= s - 1; j++) {
            x = x * x % n;
            if (x == n - 1) {
                flag = true; // 不满足逆否命题
                break;
            }
        }
        if (flag) continue;
        return false;
    }
    return true;
}

要我说还是蛮复杂的，但是这个测试就已经不会被卡迈克尔数干死了。而且在 K = 1 时就已经很准了。

时间复杂度为 $O(n\log n)$ 。

自己的判定法？

可以通过研究素数的更多性质，例如高次剩余的特性等等发明自己的判别法，如果在复杂度允许的情况下能够在int范围内没问题也可以用。

计算的所有素数

如何快速获得 [1, n] 的所有素数呢？如果对于个数都进行以上的素数判定肯定是非常慢的，因此我们需要筛法，顾名思义，就是把不是素数的全部筛掉，那么剩下的就都是素数了。

埃拉托色尼筛法

最朴素的筛法，基于的思想是如果我把每一个素数的倍数都标记成合数的话那么剩下没有标记的就是素数了，代码非常简洁，如下：

bool v[N]; // 不是质数
int prime[P], tot = 0;
for (int i = 2; i <= n; i++) {
    if (v[i]) continue;
    prime[++tot] = i;
    for (int j = 2; j <= n / i; j++)
        v[i * j] = true;
}

其复杂度应该为 $\sum_{素数p \le n} \left\lfloor \frac{n}{p} \right\rfloor$ 。由麦腾斯定理，这个式子在 $n \to \infty$ 时逼近 $n\ln\ln n$ ，因此埃拉托色尼筛法的时间复杂度为 $O(n\ln\ln n)$ ，一般可以达到 10^7 。这个筛法有一个小优化我也在之前的笔记中有提到。

埃拉托色尼筛法的精髓在于它利用了约数和倍数的关系是成对的这一点，将素数判断这一个枚举约数的问题转化为了枚举倍数的问题并加快了速度，这一思想十分重要，在计算狄利克雷卷积和反演的时候也会用到（把对因数求和转化为对倍数算贡献）。

欧拉筛

虽然 $\ln\ln n$ 这个因子已经很小了，但是面对 n = 10^8 的时候还是会跪掉。因此我们需要一种筛法能够在 O(n) 的时间内筛出所有的素数。

我们发现埃氏筛效率欠佳的一点是：一个合数会被每一个它的素因数筛掉共计好几次。我们能不能让一个合数只被筛一次呢？

bool v[N]; // 不是质数
int prime[P], tot = 0;
for (int i = 2; i <= n; i++) {
    if (!v[i]) prime[++tot] = i;
    for (int j = 1; i * prime[j] <= n; j++) {
        v[i * prime[j]] = true;
        if (i % prime[j] == 0) break;
    }
}

欧拉筛的精髓在于那句if (i % prime[j] == 0) break;。

结论：在欧拉筛中每个合数会且仅会被它的最小素因子筛去。

证明：设合数的最小素因子为 p_o ，因为 $\frac{N}{p_0}$ 不可能被 p_0 更小的素数所整除，因此在循环到 $i = \frac{N}{p_0}$ 时，内循环一定会在break之前筛到 $\frac{N}{p_0} \cdot p_0 = N$ 。而假设有有另外一个素因子 p_1 > p_0 ，则显然 $p_0 \mid \frac{N}{p_1}$ ，因此在循环到 $i = \frac{N}{p_1}$ 时，内循环一定会在筛到（prime[j]为） p_0 之后就立刻break，因此一定不会再筛到 $\frac{N}{p_1} \cdot p_1$ 。

推论：因为合数的数量少于，因此欧拉筛的复杂度为 O(n) 。

欧拉筛原名线性筛，冠以欧拉之名纯粹是因为我们不仅用它筛素数，还可以顺便计算以欧拉函数为首的一票积性函数。

素因数分解

试除法

如果为合数那么一定有一个不大于 $\sqrt n$ 的素因子，因此我们枚举 $[1, \sqrt n]$ 中的所有数挨个试除即可，时间复杂度 $O(\sqrt n)$ ，是最常用的方法。

Pollard's-Rho方法

引理（生日悖论）：在 [1, N] 当中随机选出若干个数，平均需要抽出 $O(\sqrt N)$ 个数才会抽到两个相同的数。

简介：抽前 k - 1 个数两两不同的概率为：

$\frac{P(N, k - 1)}{N^{k - 1}} = \frac{N!}{(N - k+1)!N^{k-1}}$

如果你抽第

个数，与之前

个数相同的概率为 $\frac{k - 1}{N}$ ，因此你恰巧在刚刚抽完第

个数后得到两个相同的数的概率为：

$\frac{N!}{(N - k+1)!N^{k-1}} \cdot \frac{k - 1}{N} = \frac{(k - 1)N}{(N - k +1)!N^k}$

因此为了得到两个相同的数你需要抽出的数的期望是：

$\sum_{k = 2}^{N+1} \frac{k(k - 1)N}{(N - k +1)!N^k}$

它也等价于TAOCP中的：

$1 + \sum_{k = 1}^N \frac{N!}{(N-k)!N^k}$

神奇的数学家拉马努金曾对该函数进行过研究，并指出它渐进逼近 $\sqrt {\frac{\pi N}{2}}$ 。

好的，现在假设我们需要分解出 n = pq 的一个非平凡因子，假设我们有一个多项式同余函数（例如 $g(x) = (x^2 + 1) \bmod n$ ）。我们使用来迭代生成一个伪随机序列 $\{x_n\}$ ，它和其模的序列 $\{x_n \bmod p\}$ 相关联。由之前的生日悖论引理，前者平均在 $O(\sqrt n)$ 次迭代后产生循环，而后者只需要 $O(\sqrt p) < O(\sqrt n)$ 次。我们可以在迭代中检测这个循环，从而完成对于素因数的分解。

我们知道 $\{x_n \bmod p\}$ 产生循环当且仅当存在 x_i, x_j ，有 $x_i \equiv x_j \pmod p$ ，此时 x_i 和 x_j 之间就是这个序列的一个循环节，但是我们预先是不知道的，那怎么判断以上条件是否成立呢？我们发现以上条件等价于 $p \mid |x_i - x_j|$ ，因为同时 $p \mid n$ ，所以此时最大可以为 $\gcd(n, |x_i - x_j|)$ ，因此如果我们发现 $\gcd(n, |x_i - x_j|) \neq 1$ 我们就已经找到了一个 $p = \gcd(n, |x_i - x_j|)$ ，非常巧妙！

在算法实现中，我们使用弗洛伊德判圈算法，其精髓就是环上的追及问题，我们维护两个指针 x_i, x_j ，从出发点开始 x_i 一个一个地跳， x_j 两个两个地跳，他们的速度差为，只要出现了了一个环那么在某一时刻 x_j 总是可以套 x_i 一圈！每一轮过后我们检测$(n, |x_i - x_j|) $，如果不为那说明我们找到一个因子，但是如果为的话就是 $\{x_n\}$ 和 $\{x_n \bmod p\}$ 一起循环了，我们的算法就GG了，需要重新选定一个出发点（给的种子）。

这个启发式算法的复杂度取决于 $O(\sqrt p)$ ，但是因为一般来说 $p \le \sqrt n$ ，因此算法的复杂度平均下来是 $O(n^{1 \over 4})$ 的，实测在int范围内快得飞起。