跳转至

素性探测判质数

Miller-Rabin 素性测试

执行 \(k\) 论的「时间复杂度」为 \(O(klog^3n)\)。

注意

以下都是在同余 \(n\) 的情况下讨论。

二次探测定理

如果 \(n\) 是奇素数，则 \(x^2 = 1\) 的解只有 \(x = 1\) 或 \(x = n - 1\)。

要证明该定理，只需将 \(1\) 移项到左边：\((x + 1)(x - 1) = 0\)，在同余 \(n\) 的情况下 \(x = 1\) 或 \(x = n - 1\)。

费马小定理

如果 \(n\) 是一个素数，只要 \(a\) 不是 \(n\) 的倍数，则 \(a ^ {n - 1} = 1\)。

结合「二次探测定理」和 「费马小定理」的逆定理

逆定理不一定对，适当情况下可以提高它对的概率。

先引入一个推理：

原命题：若 \(x\ \%\ n = 1\)，则 \(x ^ 2\ \%\ n = 1\) 一定成立。| | \(x\ \%\ n = 1 \rightarrow x ^ 2\ \%\ n = 1\)

逆否命题：若 \(x ^ 2\ \%\ n \neq 1\)，则 \(x\ \%\ n \neq 1\) 一定成立。| | \(x ^ 2\ \%\ n \neq 1 \rightarrow x\ \%\ n \neq 1\)

若 \(n\) 是一个奇数，要有如下逻辑：

  • 为了要结合「费马小定理」，我们要选取不是 \(n\) 的倍数 \(a\)，只需在 \([2, n - 1]\) 中任意选取一个 \(a\) 作为底数就行；
  • 若 \(a ^ {n - 1} \neq 1\) 则 \(n\) 一定不是素数；
  • 若 \(a ^ {n - 1} = 1\) 满足，我们可以说 \(a\) 很可能是「素数」；
  • 我们在上面的基础上再结合「二次定理的逆定理」，只要 \(n - 1 = u \times 2 ^ t\)，则 \(a ^ {n - 1}\) 可以等于 \(a ^ u\) 的 \(t\) 次平方；
  • 我们也可以不断地对 \(a^{n - 1}\) 不断地开根直到 \(a^u\) 中的 \(u\) 为奇数为止；
  • 对 \(a ^ {n - 1}\) 开根之后的结果 \(a ^ {\frac{n - 1}{2}}\) 如果不是 \(1\) 或 \(n - 1\)，则 \(n\) 一定不是「质数」；
  • 若 \(a ^ {\frac{n - 1}{2}}\) 是 \(1\) 就可以再一次地使用「二次探测定理的逆定理」开根，开根使用后的结果也一定得是 \(1\) 或者 \(n - 1\)；
  • 若开根后的结果不是 \(1\) 或 \(n - 1\)，继续开根的结果也一定不可能是 \(1\)，并且这种情况是 \(n\) 绝对不是素数的情况；
  • 若开根后的结果是 \(n - 1\)，继续开根的结果也一定不可能是 \(1\)，但是这种情况下 \(n\) 是很有可能是素数的。

有了上面的意识型态之后，将 \(n - 1\) 分解成 \(u \times 2 ^ t\)：

在 \([2, n - 1]\) 中随意选取 \(a\)； (费马小定理结合)

若 \(a ^ u = 1\) 则 \(n\) 一定是「素数」，因为只有 \(a ^ {u^`}\) 一直等于 \(1\) 的情况下才能最终化到 \(a ^ u = 1\)；

若 \(a ^ u \neq 1\)，则 \(a ^ u\) 可能是由 \(a ^ {u^`} = n - 1\) 的情况下化下来的，若真是这样，则 \(n\) 也极大可能是素数，并且若 \(a ^ u\) 经过几次平方之后等于 \(n - 1\)，则继续向上面平方，直到等于原值 \(a ^ {n - 1}\) 之后的结果都会是 \(1\)，所以能推出 \(a ^ {n - 1} = 1\)，符合「费马小定理的逆定理」的要求，\(n\) 也极大可能是素数。\((n - 1) ^ 2 = n ^ 2 - 2n + 1\) 在模 \(n\) 的情况下是 \(1\) ，然后由 \(1\) 不断平方模 \(n\) 之后的结果一直都会是 \(1\)；

若 \(a^u \neq 1\) ，且不断向上平方直到变为原值的情况下都没有出现 \(n - 1\) 的情况下一定不会是素数 ，若 \(a^u \neq 1\) 经过几次平方后的取值为 \(1\) ，这种情况是有可能出现的，则之后平方的所有结果都不可以出现 \(n - 1\)，并且从头顶往下面思考的过程中，若 \(a ^ {n - 1}\) 经过几次开根之后的结果由 \(1\) 变成了不是 \(1\) 或 \(n - 1\) 的情况，\(n\) 就一定不是素数。

底数 a 的选取：

在 int 范围内，\(a\) 选取 \(2、7、61\)，素性探测的准确率提高到 100%。

在 long long 范围内，\(a\) 选取 \(2, 325, 9375, 28178, 450775, 9780504, 1795265022\)，素性探测的准确率提高到 100%。

头顶向下与底部向上可行性的说明

从头顶开始，请读者自行按照下面的思路构建一颗树：

  • 一开始，若 \(a ^ {u \times 2 ^ t} = 1\)，由「费马小定理」可知，\(n\) 有可能是素数；
  • 若 \(a ^ {u \times 2 ^ {t - 1}} = n - 1\)，则 \(n\) 有可能是素数；
  • 若 \(a ^ {u \times 2 ^ {t - 1}} \neq n - 1 \neq 1\)，则 \(n\) 不可能是素数；
  • 若 \(a ^ {u \times 2 ^ {t - 1}} = 1\)，再一次使用「二次探测定理」开向下开根；
  • 若 \(a ^ {u \times 2 ^ {t - 2}} = n - 1\)，则 \(n\) 有可能是素数；
  • 若 \(a ^ {u \times 2 ^ {t - 2}} \neq n - 1 \neq 1\)，则 \(n\) 不可能是素数；
  • 若 \(a ^ {u \times 2 ^ {t - 2}} = 1\)，再一次使用「二次探测定理」开根；
  • ··· ···
  • ··· ···
  • 若 \(a ^ u = n - 1\)，则 \(n\) 有可能是素数；
  • 若 \(a ^ u \neq n - 1 \neq 1\)，则 \(n\) 不可能是素数；
  • 若 \(a ^ u = 1\)，则 \(n\) 有可能是素数；

补充说明，如果 \(a ^ {u \times 2 ^ s} \neq 1\) ，则经过不断地开根直到 \(s = 0\) 时，\(a ^ u\) 是一定无法变为 1 的。

但是若 \(a ^ u\) 虽然不是 1，但是经过 \(s\) 次平方之后 \(a ^ {u \times 2 ^ s}\) 是由可能等于 1 的，举例：\(2 \bmod 3 = 2\) 但 \(2 ^ 2 \bmod 3 = 1\)；

若 \(a ^ {u \times 2 ^ s}\) 等于 \(n - 1\)，则平方之后的取值一定会是 1，因为 \((n - 1) ^ 2 = n ^ 2 - 2n + 1 = 1\)， 并且从此开始不断平方之后还会一直保持 1，所以平方到达头顶 \(a ^ {u \times 2 ^ t}\) 次方后还会是 1，满足「费马小定理」。

若从头顶往下开了几次根之后发现 \(a ^ {u \times 2 ^ {t - k}}\) 模 \(n\) 的取值为 \(n - 1\)，则从底部 \(a ^ u\) 向上平方几次之后得到 \(n - 1\) 可以归为一类情况，都能说明 \(n\) 很可能是质数。

若从头顶往下开了 \(t\) 次根之后发现 \(a ^ {u \times 2 ^ {t - t}} = a ^ u\) 模 \(n\) 的取值一直都不是 \(n - 1\)，而一直都是 \(1\) 的情况下，也能说明 \(n\) 很可能是质数。

若从头顶往下开了 \(k\) 次根之后发现 \(a ^ {u \times 2 ^ {t - k}}\) 并不是 \(1\) 和 \(n - 1\) ，则继续先下开根直到值为 \(a ^ u\) 次方时，模 \(n\) 的结果是一直都不可能出现 \(1\) 的，换句话说，只要 \(a ^ u = 1\)，则 \(n\) 很可能是质数；否则，得从 \(a ^ u\) 开始向上平方多次，若平方到 \(a ^ {u \times 2 ^ {t}}\) 为止都未能出现 \(n - 1\)，则一定不可能是素数；若出现 \(n - 1\)，继续平方就会出现 \(1\)，并且一直向上平方都会是 \(1\)，满足费马小定理，\(n\) 很可能是质数；若向上平方的过程中出现了 \(1\)，则也能说明 \(n\) 一定不是素数了。

写的很啰嗦，希望未来的自己能够耐心看看过去的自己留下的「百感交集」。

从底部向上思考，为什么要从底部向上？因为取模运算对于加、减、乘可以随便、随处、随意取模：

  • 从 \(2 ^ u\) 开始
  • 若 \(2 ^ u\) 等于 1，则 \(n\) 极大可能是素数；
  • 若 \(2 ^ u\) 不等于 1，若等于 \(n - 1\)，则 \(n\) 极大可能是素数；
  • 若都不满足，就不断的执行平方；
  • 若执行了 \(s\) 次平方操作之后，\(2 ^ {u \times 2 ^ s}\) 的结果为 \(n - 1\)，则 \(n\) 极大可能是素数；
  • 若执行了 \(t\) 次平方操作都未能找到 \(n - 1\)，则 \(n\) 一定不可能是素数；

代码设计：

miller-rabin 代码模板
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
typedef long long ll;
typedef __int128_t int128;

inline ll qmul(int128 a, int128 b, int128 p)
{
    return a * b % p;
}

ll qpow(ll a, ll n, ll p)
{
    ll ans = 1, i = 1, j = a;
    while (i <= n)
    {
        if (n & i) ans = qmul(ans, j, p);
        i <<= 1; j = qmul(j, j, p);
    }
    return ans;
}

ll la[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}; // long long 范围内
// ll la[] = {2, 7, 61}; // int 范围内

bool mrq(ll n)
{
    if (n < 3 || n % 2 == 0) return n == 2;
    ll u = n - 1, t = 0;
    while (u % 2 == 0) u /= 2, ++ t;
    for (ll a : la)
    {
        ll v = qpow(a, u, n);
        if (v == 1 || v == n - 1 || v == 0) continue;
        for (int j = 1; j <= t; j ++)
        {
            v = qmul(v, v, n);
            if (v == n - 1 && v != t) { v = 1; break; }
            if (v == 1) return 0;
        }
        if (v != 1) return 0;
    }
    return 1;
}