阶与原根

阶与原根是数论中描述模 $m$ 乘法群 $\mathbf{Z}_m^*$ 结构的重要概念。它们在离散对数、NTT（快速数论变换）等算法中有着广泛应用。

阶 (Order)

定义

设 $m \in \mathbf{N}_+, a \in \mathbf{Z}$ 且 $\gcd(a, m) = 1$ 。满足同余式

a^n \equiv 1 \pmod m

的最小正整数 $n$ 称为 $a$ 模 $m$ 的阶，记作 $\delta_m(a)$ 或 $\operatorname{ord}_m(a)$ 。

基本性质

$a^0, a^1, \dots, a^{\delta_m(a)-1}$ 模 $m$ 两两不同余。
$a^n \equiv 1 \pmod m$ 的充要条件是 $\delta_m(a) \mid n$ 。由欧拉定理可知 $\delta_m(a) \mid \varphi(m)$ 。
设 $\delta_m(a) = \ell$ ，则 $\delta_m(a^k) = \frac{\ell}{\gcd(\ell, k)}$ 。

原根 (Primitive Root)

定义

设 $m \in \mathbf{N}_+, g \in \mathbf{Z}$ 。如果 $\gcd(g, m) = 1$ 且 $\delta_m(g) = \varphi(m)$ ，则称 $g$ 是模 $m$ 的一个原根。

当原根存在时，模 $m$ 的既约剩余系（与 $m$ 互素的余数集合）可以表示为 $\{g^1, g^2, \dots, g^{\varphi(m)}\}$ 。这在代数上意味着模 $m$ 乘法群是一个循环群。

存在性定理

模 $m$ 存在原根的充要条件是 $m \in \{1, 2, 4, p^k, 2p^k\}$ ，其中 $p$ 是奇素数。

原根判定定理

若 $g \perp m$ ，则 $g$ 是模 $m$ 的原根当且仅当对于 $\varphi(m)$ 的任意质因子 $p$ ，都有：

g^{\frac{\varphi(m)}{p}} \not\equiv 1 \pmod m

原根个数

若模 $m$ 存在原根，则原根共有 $\varphi(\varphi(m))$ 个。

求原根的算法

求模 $m$ 的最小原根通常采用暴力枚举配合判定定理的方法。由于最小原根通常很小，该算法在实践中效率很高。

步骤

判断 $m$ 是否存在原根。
求出 $\varphi(m)$ 及其所有不同的质因子 $p_1, p_2, \dots, p_k$ 。
从 $g=1$ $g = 1$ 开始枚举（通常从 2 开始）：
- 检查 $\gcd(g, m)$ 是否为 1。
- 对每个 $p_i$ ，检查 $g^{\varphi(m)/p_i} \bmod m$ 是否不等于 1。
- 若全部满足，则 $g$ 即为最小原根。
若需要所有原根：可以通过最小原根 $g$ 构造 $g^k \pmod m$ ，其中 $\gcd(k, \varphi(m)) = 1$ 。

实现 (C++)

cpp

#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

typedef long long ll;

struct PrimitiveRoot {
    ll power(ll a, ll b, ll m) {
        ll res = 1;
        a %= m;
        while (b) {
            if (b & 1) res = (ll)((__int128)res * a % m);
            a = (ll)((__int128)a * a % m);
            b >>= 1;
        }
        return res;
    }

    ll get_phi(ll n) {
        ll res = n;
        for (ll i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                res = res / i * (i - 1);
                while (n % i == 0) n /= i;
            }
        }
        if (n > 1) res = res / n * (n - 1);
        return res;
    }

    vector<ll> get_prime_factors(ll n) {
        vector<ll> factors;
        for (ll i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                factors.push_back(i);
                while (n % i == 0) n /= i;
            }
        }
        if (n > 1) factors.push_back(n);
        return factors;
    }

    bool has_primitive_root(ll m) {
        if (m == 1 || m == 2 || m == 4) return true;
        if (m % 2 == 0) m /= 2;
        if (m % 2 == 0) return false;
        // 此时 m 应该是 p^k 形式
        for (ll i = 3; i * i <= m; i++) {
            if (m % i == 0) {
                while (m % i == 0) m /= i;
                return m == 1;
            }
        }
        return true; // m 本身是奇素数
    }

    ll find_min_root(ll m) {
        if (!has_primitive_root(m)) return -1;
        ll phi = get_phi(m);
        vector<ll> factors = get_prime_factors(phi);
        
        for (ll g = 1; g < m; g++) {
            if (gcd(g, m) != 1) continue;
            bool ok = true;
            for (ll p : factors) {
                if (power(g, phi / p, m) == 1) {
                    ok = false;
                    break;
                }
            }
            if (ok) return g;
        }
        return -1;
    }
};

总结

阶与原根是模运算下指数性质的核心。掌握原根的判定定理及其求法，是处理离散对数及相关数论变换（如 NTT）的基础。

阶与原根 ​

阶 (Order) ​

定义 ​

基本性质 ​

原根 (Primitive Root) ​

定义 ​

存在性定理 ​

原根判定定理 ​

原根个数 ​

求原根的算法 ​

步骤 ​

实现 (C++) ​

总结 ​