数论笔记-原根

时间:2024-02-19 13:01:40

目录
  • 原根
      • 阶的定义与基本性质
    • 原根
      • 原根的定义与基本性质
      • 原根判定性定理
      • 原根存在性定理
      • 原根的求法
        • 枚举法(最小原根)
        • 枚举法(所有原根)
    • 指标
      • 指标的定义与基本性质
      • 指标的求法
        • 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\) 的最小原根大致分为以下几步:

  1. \(n\) 质因数分解,根据原根存在性定理判断 \(n\) 是否有原根,复杂度 \(O(\sqrt n)\)
  2. \(\varphi(n)\) 及其质因数集合,复杂度 \(O(\sqrt n)\)
  3. 枚举 \(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)\)

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

int exgcd(int a, int b, int &x, int &y) {
    if (!b) { x = 1, y = 0; return a; }
    int d = exgcd(b, a % b, x, y);
    x -= (a / b) * y, swap(x, y);
    return d;
}
int inv(int a, int P) {
    int x, y;
    exgcd(a, P, x, y);
    return (x % P + P) % P;
}
int BSGS(int a, int b, int P) {
    if (1 % P == b) 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;
}
int exBSGS(int a, int b, int P) {
    if (1 % P == b) return 0;
    int d = gcd(a, P);
    if (d == 1) return BSGS(a, b, P);
    if (b % d) return -2e9;
    int ans = exBSGS(a, 1LL * b / d * inv(a / d, P / d) % (P / d), P / d);
    return ans + (ans != -1);
}