数论笔记-原根

原根
- 阶
  - 阶的定义与基本性质
- 原根
  - 原根的定义与基本性质
  - 原根判定性定理
  - 原根存在性定理
  - 原根的求法
    - 枚举法（最小原根）
    - 枚举法（所有原根）
- 指标
  - 指标的定义与基本性质
  - 指标的求法
    - BSGS算法
    - 扩展BSGS算法

原根

阶

阶的定义与基本性质

定义设 $a \in \Z, m \in \N^*$ 且 $\gcd(a,m) = 1$ ，那么满足 $a^{x} \equiv 1 \pmod m$ 的最小正整数 $x$ 称为 $a$ 模 $m$ 的阶，记作 $\delta_m(a)$ 或 $\text{ord}_m(a)$ 。

阶是群论的概念， $a$ 模 $m$ 的阶即 $a$ 在模 $m$ 缩系下生成的乘法群大小。

性质1 $a, a^2, \cdots , a^{\delta_m(a)}$ 模 $m$ 互不相同。

性质2 正整数 $n$ 满足 $a^n \equiv 1 \pmod m$ ，当且仅当 $\delta_m(a) \mid n$ 。

性质3 $\delta_m(a)$ 一定存在，且 $\delta_m(a) \mid \varphi(m)$ 。

性质4 设 $a,b \in \Z$ ，有 $\gcd(\delta_m(a),\delta_m(b)) = 1 \iff \delta_m(ab) = \delta_m(a)\delta_m(b)$ 。

性质5 设 $k \in \N$ ，有 $\delta_m(a^k) = \dfrac{\delta_m(a)}{\gcd(\delta_m(a), k)}$ 。

性质1的证明：

假设存在不同的两个数 $i,j$ ，满足 $a^i \equiv a^j \pmod m$ ，那么有 $a^{|i - j|} \equiv 1 \pmod m$ ，其中 $|i - j| < \delta_m(a) $ ，与定义相悖，因此原命题成立。

性质2的证明：

必要性：

使用带余数除法， $n$ 除以 $\delta_m(a)$ 得 $n = q \delta_m(a) + r$ ，其中 $r \in [0, \delta_m(a))$。

那么， $a^n \equiv a^{q\delta_m(a) + r} \equiv a^r \equiv 1 \pmod m$ ，根据阶的定义，$r \geq \delta_m(a)$ 或 $r = 0$ 。

因此 $r = 0$ ，即 $\delta_m(a) \mid n$ 。

充分性：

显然。

性质3的证明：

根据欧拉定理，有 $a^{\varphi(m)} \equiv 1 \pmod m$ ，又根据性质2，阶一定存在，且是 $\varphi(m)$ 的因数。

性质4的证明：

必要性：

由 $a^{\delta_m(a)} \equiv b^{\delta_m(a)} \equiv 1 \pmod m$ ，可得 $(ab)^{\text{lcm}(\delta_m(a),\delta_m(b))} \equiv 1 \pmod m$ ，因此 $\delta_m(ab) \mid \text{lcm}(\delta_m(a),\delta_m(b))$ 。又 $\delta_m(ab) = \delta_m(a) \delta_m(b)$ ，因此 $ \delta_m(a) \delta_m(b) \mid \text{lcm}(\delta_m(a),\delta_m(b))$ ，所以 $\gcd(\delta_m(a),\delta_m(b)) = 1$ 。

充分性：

由 $(ab)^{\delta_m(ab)} \equiv 1 \pmod m$ ，得 $(ab)^{\delta_m(ab)\delta_m(b)} \equiv 1 \pmod m$ ，因此 $a^{\delta_m(ab)\delta_m(b)} \equiv 1 \pmod m$ ，所以 $\delta_m(a) \mid \delta_m(ab)\delta(b)$ ，又 $\gcd(\delta_m(a), \delta_m(b)) = 1$ ，根据整除的基本性质4，有 $\delta_m(a) \mid \delta_m(ab)$ 。

同理有 $\delta_m(b) \mid \delta_m(ab)$ 。

又因为 $\gcd(\delta_m(a), \delta_m(b)) = 1$ ，所以 $\delta_m(a) \delta_m(b) \mid \delta_m(ab)$ 。

同时 $(ab)^{\delta_m(a)\delta_m(b)} \equiv 1 \pmod m$ ，所以 $\delta_m(ab) \mid \delta_m(a)\delta_m(b)$ 。

综上，根据整除的基本性质7， $\delta_m(ab) = \delta_m(a)\delta_m(b)$ 。

性质5的证明：

由 $(a^k)^{\delta_m(a)} \equiv 1 \pmod m$ ，因此 $\delta_m(a) \mid k\delta_m(a^k)$ ，所以 $\dfrac{\delta_m(a)}{\gcd(\delta_m(a),k)} \mid \delta_m(a^k)$ 。

同时 $(a^k)^{\frac{\delta_m(a)}{\gcd(\delta_m(a),k)}} \equiv (a^{\delta_m(a)})^{\frac{k}{\gcd(\delta_m(a),k)}} \equiv 1 \pmod m$ ，所以 $ \delta_m(a^k) \mid \dfrac{\delta_m(a)}{\gcd(\delta_m(a),k)}$ 。

综上，根据整除的基本性质7，$ \delta_m(a^k) = \dfrac{\delta_m(a)}{\gcd(\delta_m(a),k)}$ 。

原根

原根的定义与基本性质

定义设 $g \in \Z, m \in \N^*$ 且 $\gcd(g, m) = 1$ ，若 $\delta_m(g) = \varphi(m)$ ，则称 $g$ 为模 $m$ 的原根。

原根即群论中的生成元。“根”表示方程 $x ^{\varphi(m)} \equiv 1 \pmod m$ 的一个解，“原”表示能生成模 $m$ 缩系的所有元素。因此，模数 $m$ 存在原根，也代表模 $m$ 缩系的乘法群是一个循环群。

性质1 若 $m$ 存在原根 $g$ ，那么 $g,g^2, \cdots ,g^{\varphi(m)}$ 构成模 $m$ 的简化剩余系。

性质2 若 $m$ 存在原根，那么对于任意 $\varphi(m)$ 的因子 $d$ ，模 $m$ 的 $d$ 阶元素个数为 $\varphi(d)$ 。

推论1（性质2的推论，原根个数） 若 $m$ 存在原根，那么原根的个数为 $\varphi(\varphi(m))$ 。
推论2（性质2的推论） 若 $m$ 存在原根，那么对于任意 $\varphi(m)$ 的因子 $d$ ， $x^d \equiv 1 \pmod m$ 的解恰好有 $\varphi(d)$ 个。

性质3 素数 $p$ 的最小原根 $g$ ，满足 $g = \Omega(\log p) = O(p^{0.25 + \varepsilon}), \varepsilon > 0$ 。

性质4 若素数 $p$ 的原根是 $g$ ，那么 $p$ 和 $g + p$ 中必有一个是 $p^{\alpha}$ 的原根，$g$ 和 $g + p^{\alpha}$ 中的奇数是 $2p^{\alpha}$ 的原根。

性质1的证明：

由于 $\delta_m(g) = \varphi(m)$ ，因此 $g,g^2, \cdots ,g^{\varphi(m)}$ 互不相同且都与 $m$ 互质，因此其构成模 $m$ 的简化剩余系。

性质2的证明：

设 $d' = \dfrac{\varphi(m)}{d}$ ，那么 $\delta_m(g^{d'}) = \dfrac{\varphi(m)}{\gcd(d',\varphi(m))} = d$ 。

设正整数 $k$ 满足 $k \leq d$ ，根据阶的性质5，当且仅当 $\gcd(k, d) = 1$ 时， $\delta_m(g^{kd'}) = \delta_m(g^{d'}) = d$ ，这样的 $k$ 有 $\varphi(d)$ 个。

而根据性质1， $g^{kd'}$ 一定模 $m$ 互不相同，所以模 $m$ 的 $d$ 阶的元素至少有 $\varphi(d)$ 个。

当 $k > d$ 时，$kd' \equiv (k \bmod d)d' \pmod{\varphi(m)}$ ，与 $k \leq d$ 时的情况重复。

综上模 $m$ 的 $d$ 阶元素个数为 $\varphi(d)$ 。

推论1的证明：

根据性质2，模 $m$ 的 $\varphi(m)$ 阶元素共有 $\varphi(\varphi(m))$ 个。

推论2的证明：

根据性质2，模 $m$ 的 $d$ 阶元素有 $\varphi(d)$ 个。

同时，仅对于满足 $d' \mid \varphi(d)$ 的正整数 $d'$ ，$d'$ 阶元素都是方程的解，显然这些元素各不相同。

因此，满足方程解的个数恰好为 $\displaystyle \sum_{d' \mid \varphi(d)} \varphi(d') = \varphi(d)$ 个。

性质3的证明：

出自论文，详见 OI-wiki 。

性质4的证明：

~~不会qwq~~

原根判定性定理

定理1（原根判定性定理） $g$ 是模 $m$ 的原根，当且仅当对于任意 $\varphi(m)$ 的素因数 $p$ ，满足 $g^{\frac{\varphi(m)}{p}} \not\equiv 1 \pmod m$ 。

定理1的证明：

必要性：显然。

充分性：

假设 $g$ 不是模 $m$ 的原根，即存在 $t < \varphi(m)$ 满足 $g^t \equiv 1 \pmod m$ 。

根据裴蜀定理，存在一组整数 $x,y$ 使得 $xt = y\varphi(m) + \gcd(t, \varphi(m))$ 。

此时，有 $1 \equiv g^{xt} \equiv g^{\gcd(t,\varphi(m))} \pmod m$ ，而 $\gcd(t,\varphi(m)) \mid \varphi(m)$ 且 $\gcd(t,\varphi(m)) \leq t < \varphi(m)$ 。

因此，存在 $\varphi(m)$ 的素因数 $p$ ，使得 $\gcd(t,\varphi(m)) \mid \dfrac{\varphi(m)}{p}$ ，所以 $g^{\frac{\varphi(m)}{p}} \equiv 1 \pmod m$ ，矛盾。

因此 $g$ 是模 $m$ 的原根。

原根存在性定理

定理1（原根存在性定理） 模数 $m$ 的原根存在，当且仅当 $m = 2,4,p^{\alpha},2p^\alpha$ ，其中 $p$ 为奇素数，$\alpha \in \N^*$。

定理1的证明：

可参考 OI-wiki 。

原根的求法

枚举法（最小原根）

求 $n$ 的最小原根大致分为以下几步：

对 $n$ 质因数分解，根据原根存在性定理判断 $n$ 是否有原根，复杂度 $O(\sqrt n)$ 。
求 $\varphi(n)$ 及其质因数集合，复杂度 $O(\sqrt n)$ 。
枚举 $g \in [1, n]$ 中与 $n$ 互质的数，根据原根判定性定理判定，得到最小原根 $g$ ，复杂度 $O(n^{\frac{1}{4}} \log^2 n)$ 。

第三步根据性质3的估计得到。

前两步可以换成筛法预处理，复杂度更大但常数小，时间上差不多，按需求改即可。

代码在求所有原根中给出。

时间复杂度 $O(\sqrt n)$

空间复杂度 $O(\sqrt n)$

枚举法（所有原根）

先求出最小原根，根据性质2的证明，枚举 $k \in [1, \varphi(n)]$ 中与 $\varphi(n)$ 互质的数，$g^k$ 即为原根。

可以换成 bitset 进行 $[1,n]$ 递推，常数会小很多。

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

空间复杂度 $O(\sqrt n)$

int one_euler(int n) {
    int ans = n;
    for (int i = 2;i * i <= n;i++) {
        if (!(n % i)) {
            ans = ans / i * (i - 1);
            while (!(n % i)) n /= i;
        }
    }
    if (n > 1) ans = ans / n * (n - 1);
    return ans;
}
void get_pfactor(int n, vector<int> &pfactor) {
    for (int i = 2;i * i <= n;i++) {
        if (!(n % i)) {
            pfactor.push_back(i);
            while (!(n % i)) n /= i;
        }
    }
    if (n > 1) pfactor.push_back(n);
}
int qpow(int a, ll k, int P) {
    int ans = 1;
    while (k) {
        if (k & 1) ans = 1LL * ans * a % P;
        k >>= 1;
        a = 1LL * a * a % P;
    }
    return ans;
}
bool exist_proot(int n) {
    if (n == 2 || n == 4) return true;
    vector<int> pfactor;
    if (n & 1) get_pfactor(n, pfactor);
    else get_pfactor(n / 2, pfactor);
    return pfactor.size() == 1;
}
int min_proot(int n) {
    if (!exist_proot(n)) return 0;
    int phi_n = one_euler(n);
    vector<int> pfactor;
    get_pfactor(phi_n, pfactor);
    for (int i = 1;i <= n;i++) {
        if (gcd(i, n) != 1) continue;
        bool ok = 1;
        for (auto j : pfactor) ok &= qpow(i, phi_n / j, n) != 1;
        if (ok) return i;
    }
    return 0;
}
void get_proot(int n, vector<int> &proot) {
    int g = min_proot(n);
    if (!g) return;
    int phi_n = one_euler(n);
    for (int i = 1;i <= phi_n;i++) {
        if (gcd(i, phi_n) != 1) continue;
        proot.push_back(qpow(g, i, n));
    }
}

指标

指标的定义与基本性质

定义设 $g$ 为模 $m$ 的原根，存在唯一整数 $x \in [0,\varphi(m))$ 满足 $a \equiv g^x \pmod m$ ，称这个 $x$ 是 $a$ 模 $m$ 关于 $g$ 的指标（离散对数、指数），记作 $\text{ind}_g(a)$ 。

离散对数和实数对数运算规则几乎没有区别，但注意离散对数建立在模 $m$ 的简化剩余系，域内元素都是可逆的。

设正整数 $a,b$ ，满足 $\gcd(a,m) = \gcd(b,m) = 1$ ，$g$ 是模 $m$ 的原根。

性质1（唯一性） $a \equiv b \pmod m \iff \text{ind}_g(a) = \text{ind}_g(b)$ 。

性质2（加法） $\text{ind}_g(a) + \text{ind}_g(b) \equiv \text{ind}_g(ab) \pmod{\varphi(m)}$ 。

性质3（减法） $\text{ind}_g(a) - \text{ind}_g(b) \equiv \text{ind}_g \left(\dfrac{a}{b} \right) \pmod{\varphi(m)}$ 。

性质4（乘法） 对于任意整数 $n$ ， $n \cdot \text{ind}_g(a) \equiv \text{ind}_g(a^n) \pmod{\varphi(m)}$ 。

性质5（除法） 若整数 $n$ 满足 $\gcd(n, \varphi(m)) = 1$ ，那么 $\dfrac{1}{n} \cdot\text{ind}_g(a) \equiv \text{ind}_{g^n}(a) \pmod{\varphi(m)}$ 。

性质6（逆元） 若 $g'$ 也是模 $m$ 的原根，则 $\text{ind}_g(g')$ 模 $\varphi(m)$ 的逆元是 $\text{ind}_{g'}(g)$ 。

性质7（换底公式） 若 $g'$ 也是模 $m$ 的原根，那么 $\dfrac{\text{ind}_{g'}(a)}{\text{ind}_{g'}(g)} \equiv \text{ind}_g(a) \pmod{\varphi(m)}$ 。

性质1的证明：

\[\begin{aligned} a \equiv b \pmod m &\mathrm{\iff} g^{\text{ind}_g(a)} \equiv g^{\text{ind}_g(b)} \pmod m \\ &\mathrm{\iff} \text{ind}_g(a) \equiv \text{ind}_g(b) \pmod{\varphi(m)}\\ &\mathrm{\iff} \text{ind}_g(a) = \text{ind}_g(b) \\ \end{aligned} \]

性质2的证明：

显然， $g^{\text{ind}_g(a) + \text{ind}_g(b)} \equiv g^{\text{ind}_g(a)} g^{ \text{ind}_g(b)} \equiv ab \equiv g^{\text{ind}_g(ab)} \pmod m$ 。

根据性质1得 $\text{ind}_g(a) + \text{ind}_g(b) \equiv \text{ind}_g(ab) \pmod{\varphi(m)}$ 。

性质3的证明：

显然 $b$ 有模 $m$ 的逆元，那么 $g^{\text{ind}_g(a) - \text{ind}_g(b)} \equiv g^{\text{ind}_g(a)} g^{ -\text{ind}_g(b)} \equiv \dfrac{a}{b} \equiv g^{\text{ind}_g \left(\frac{a}{b} \right)} \pmod m$ 。

根据性质1得 $\text{ind}_g(a) - \text{ind}_g(b) \equiv \text{ind}_g\left(\dfrac{a}{b} \right) \pmod{\varphi(m)}$ 。

性质4的证明：

根据性质1，且 $a$ 具有模 $m$的逆元，显然得证。

性质5的证明：

显然 $n$ 具有模 $\varphi(m)$ 的逆元。

根据性质4和定义， $\dfrac{1}{n} \cdot \text{ind}_g(a) \equiv \text{ind}_g(a^{\frac{1}{n}}) \equiv \text{ind}_{g^n}(a) \pmod{\varphi(m)}$ 。

性质6的证明：

根据性质4和定义，得 $\text{ind}_{g}(g') \cdot \text{ind}_{g'}(g) \equiv \text{ind}_g({g'}^{\text{ind}_{g'}(g)}) \equiv \text{ind}_g(g) \equiv 1 \pmod{\varphi(m)}$ ，符合逆元定义。

性质7的证明：

根据性质6， $\text{ind}_{g'}(g)$ 模 $\varphi(m)$ 的逆元存在。

设 $\dfrac{\text{ind}_{g'}(a)}{\text{ind}_{g'}(g)} \equiv x \pmod{\varphi(m)}$ ，那么 $a \equiv {g'}^{x \cdot \text{ind}_{g'}(g)} \equiv g^x \pmod{m}$ 。

根据定义 $x = \text{ind}_g(a)$ 。

指标的求法

BSGS算法

BSGS算法求解该类问题：给定 $a,b,m \in \Z^+$ ，满足 $\gcd(a,m) = 1$ ，求 $a^x \equiv b \pmod m$ 的最小非负整数解 $x$ 。

根据阶的相关性质，我们知道 $a$ 的次方的最小循环节是 $\delta_m(a) \leq \varphi(m) < m$ 。而循环节最坏情况为 $m-1$ ，为了方便，我们直接在 $x \in [0, m)$ 中找最小解即可，不影响复杂度。

我们考虑用分块代替直接枚举，设块大小为 $B = \left\lceil \sqrt m \right\rceil$ ，令 $x = iB - j$ ，其中 $i \in [1,B],j \in[0,B-1]$ ，那么 $x \in [1,B^2]$ 。显然 $B^2 \geq m$ ，可以覆盖除了 $0$ 的所有情况，我们一开始特判 $0$ 即可。

此时，原方程变为 $a^{iB - j} \equiv b \pmod m$ ，进一步变形 $a^{iB} \equiv b \cdot a^{j} \pmod m$ 。此时，我们枚举 $i$ ，只要找到 $j$ 使得方程成立，即可得到一个解。注意到 $j \in [0, B-1]$ ，可以将 $b \cdot a^j \to j$ 的映射存下来，每次枚举 $i$ 的时候查询等于 $a^{iB}$ 对应的 $j$ 即可。

需要注意的是，我们要求最小的非负整数解，那么在保证 $i$ 尽可能小之后，还要保证 $j$ 尽可能大，因此在存映射的时候，遇到 $b \cdot a^j$ 值相同的，我们存 $j$ 较大的。

使用前确保 $a,b < m$ 。

时间复杂度 $O(\sqrt m)$

空间复杂度 $O(\sqrt m)$

int BSGS(int a, int b, int P) {
    if (1 % P == b % P) return 0;
    unordered_map<int, int> ump;
    int B = sqrt(P) + 1;
    int aB = 1;
    for (int i = 0;i <= B - 1;i++) {
        ump[1LL * aB * b % P] = i;
        aB = 1LL * aB * a % P;
    }
    for (int i = 1, val = aB;i <= B;i++) {
        if (ump.count(val)) return 1LL * i * B - ump[val];
        val = 1LL * val * aB % P;
    }
    return -1;
}

扩展BSGS算法

考虑方程 $a^x \equiv b \pmod m$ ，其中 $\gcd(a,m)$ 不一定为 $1$ ，求解最小非负整数解。

如果 $\gcd(a,m) = 1$ ，直接使用BSGS算法即可。

否则，设 $d = \gcd(a,m)$ ，那么 $a$ 模 $m$ 的乘法群中都是 $d$ 的倍数，因此 $b$ 要满足 $d \mid b$ 才有解，否则无解。

现在，根据同余基本性质的同除性，方程等价于 $\dfrac{a}{d} a^{x-1} \equiv \dfrac{b}{d} \pmod{\dfrac{m}{d}}$ 。

显然 $\dfrac{a}{d}$ 存在逆元，因此我们得到新的方程 $a^{x-1} \equiv \dfrac{b}{d} \left(\dfrac{a}{d}\right)^{-1} \pmod{\dfrac{m}{d}}$ ，对这个方程递归做上面步骤即可，每层递归要将答案加 $1$ 。这里加 $1$ 可以证明不影响解是最小的。

时间复杂度 $O(\sqrt m + \log^2 m)$