• 小鸥定理与扩展小鸥定理
  • 小鸥定理：$a^{phi(m)} \equiv 1 \pmod m$，其中 $\gcd(m,a) = 1$
  • 扩展小鸥定理：$a^b \equiv a^{\varphi(m) + b \mod \varphi(m)} \pmod m$
  • 扩鸥定理应用：
    • 上帝与集合的正确用法扩展：求 $x$ 满足 $a^{a^{a^{a^{\cdots}}}} = x \pmod p$
    • $a^{x \mod \varphi(p) + \varphi(p)} = x$，递推即可。
    • 结论：$a^{a^{a^{a^{\cdots}}}}$ 只要递推 $O(\log p)$ 次即可求出
• BSGS
  • BSGS 是一种将 找答案分解成小步和大步的做法。（废话）
  • 流程（以求解 $a^x \equiv b \pmod p$ 为例子）：先将 x 拆成 $i \sqrt p + j$ 。然后枚举 $i$ ，查找是否存在 $j$ 使得 $b a^j \equiv a^{i \sqrt p}$。如果存在，则 $x = i \sqrt p - j$ 是一组解。判断存不存在用哈希表即可。
• miller rabin & pollard rho
  • 二探定理：$p \in \text P$ 则 $x^2 = 1 \pmod p \Rightarrow x \equiv 1 \lor x \equiv -1 \pmod p$
  • 实例水母：

bool miller_rabin(ll n, ll a) {
 
    ll d = n - 1, r = 0;
 
    while (!(d & 1)) d >>= 1, r++;
 
    ll z = f_pow(a, d, n);
 
    if (z == 1)
 
        return 1;
 
    for (ll i = 0; i < r; i++) {
 
        if (z == n - 1)
 
            return 1;
 
        z = (z * z) % n;
 
    }
 
    return 0;
 
}
 
 
 
bool prime(ll n) {
 
    if (n <= 1)
 
        return 0;
 
    for (ll i : p2) {
 
        if (n == i)
 
            return 1;
 
        if (n % i == 0)
 
            return 0;
 
        if (!miller_rabin(n, i))
 
            return 0;
 
    }
 
    return 1;
 
}
 
 
 
ll rho(ll n) {
 
    ll x, y, z, c, g, i, j;
 
    while (1) {
 
        x = y = rng() % n;
 
        z = 1;
 
        c = rng() % n;
 
        i = 0, j = 1;
 
        for (;; i++) {
 
            x = (x * x % n + c) % n;
 
            z = (z * max(y - x, x - y)) % n;
 
            if (x == y or !z)
 
                break;
 
            if (i % 127 == 0 or i == j) {
 
                g = __gcd(n, z);
 
                if (g > 1)
 
                    return g;
 
                if (i == j) {
 
                    y = x;
 
                    j <<= 1;
 
                }
 
            }
 
        }
 
    }
 
}

• 原根
  • 原根定义：满足 $1, g, g^2, g^3, \cdots, g^{phi(p)}$ 都不相同的 g。
  • 判断法：枚举 $\varphi(p)$ 的每个质因数，设当前枚举的是 c。如果 $a^{\frac{\varphi(p)}{c}} \equiv 1 \pmod p$，则 a 不是原根。
  • 原根一定小于 $n^{0.25 + \epsilon}$，求最小原根暴力枚举即可。
  • 原根存在条件：$(\exists p \in \text P \land p \mod 2 = 1, k \in \text Z), n = 2 \lor n = 4 \lor n = p^k \lor n = 2p^k$
• 二次剩余
  • https://oi-wiki.org/math/number-theory/quad-residue/