【学习笔记】原根与指标

1. 阶

1.1 定义

• 设正整数 \(n>1\)，\(a\) 是满足 \(a\perp n\) （\(a\) 与 \(n\) 互质）的整数，则必有一个正整数 \(r\in [1,n]\)，使得 \(a^r\equiv 1\pmod n\)。
• 满足条件的最小的正整数 \(r\)，称为 \(a\) 模 \(n\) 的阶，记作 \(Ord_n(a)\)。
• 注意，若 \((a,n)\neq 1\)，则不存在 \(a\) 模 \(n\) 的阶。

1.2 阶的性质

1. 设 \(a\perp n\)，\(a^N\equiv 1\pmod n \Leftrightarrow Ord_n(a)|N\)。
2. 设 \(a\perp n\)，\(Ord_n(a)|\varphi(n)\)。

2. 原根

2.1 定义

• 设正整数 \(n>1\)，\(a\) 是满足 \(a\perp n\) 的整数，若 \(Ord_n(a)=\varphi(n)\)，则称 \(a\) 为模 \(n\) 的一个原根。

2.2 解性

• 设正整数 \(n>1\)，\(n\) 的原根是一些关于 \(n\) 的剩余类（原根可以不止一个）。
• 所以研究原根时，我们只需要研究 \([1,n)\) 范围内的解即可。

2.3 原根的性质

1. 只有 \(2,4,p^k,2p^k(p是奇素数)\) 有原根。
2. 一个数 \(n\) 若存在原根，则它有 \(\varphi(\varphi(n))\) 个原根。
3. 记 \(\delta=Ord_n(a)\)，则 \(a^0,a^1,\dots,a^{\delta-1}\) 模 \(n\) 两两不同余，当 \(a\) 是 \(n\) 的原根时，\(a^0,a^1,\dots,a^{\delta-1}\) 构成模 \(n\) 的简化剩余系。特别地，当 \(n\) 是质数时，\(a^0,a^1,\dots,a^{\delta-1}\) 对 \(n\) 取模后对应为 \(\{1,2,\dots,n-1\}\)。

2.4 求一个数原根的方法

• 我们已知一个数 \(n\) 存在原根。
• 我们现在要找到 \(n\) 最小的原根。
• 假设我们现在枚举到一个 \(g\)，并且 \((g,n)=1\)，要验证 \(g\) 是否是 \(n\) 的原根。
• 根据 \(Ord_n(g)|\varphi(n)\)，我们只需要验证对于每个 \(d|\varphi(n)(d\neq \varphi(n))\)，是否均满足 \(g^d\not\equiv 1\pmod n\)。
• 我们设 \(\varphi(n)=\prod_{i=1}^cp_i^{k_i}\)（\(p_i\) 是质数）。
• 因为若 \(g^d\equiv 1\pmod n\)，则 \(g^{dk}\equiv 1\pmod n\)，所以我们只需要验证，对于每个 \(i\)，均满足 \(g^{\frac{n}{p_i}}\not\equiv1\pmod n\) 即可。
• 只需要暴力枚举验证即可。
• 最小原根的范围都很小。

//mod是指需要求mod的最小原根，phi是mod的phi函数值
inline int find_root(const int &mod, const int &phi)
{
    static int p[MaxCnt];
    static int cnt;
    cnt = 0;

    int x = phi;
    for (int i = 2; i * i <= phi; ++i)
        if (x % i == 0)
        {
            p[++cnt] = i;
            while (x % i == 0)
                x /= i;
        }
    if (x > 1)
        p[++cnt] = x;

    for (int g = 1; g <= mod; ++g)
    {
        if (std::__gcd(g, mod) > 1) continue;
        bool flg = true;
        for (int i = 1; i <= cnt; ++i)
            if (qpow(g, phi / p[i], mod) == 1)
            {
                flg = false;
                break;
            }
        if (flg)
            return g;
    }
    return -1;
}

3. 指标

3.1 定义

• 设 \(g\) 是 \(n\) 的一个原根，整数 \(a \perp n\)，则在模 \(\varphi(n)\) 意义下有唯一的整数 \(x\)，使得 \(g^x\equiv a\pmod n\)，则称 \(x\) 为以 \(g\) 为底对模 \(n\) 的一个指标，记作 \(x=ind_ga\)。

3.2 指标的性质

1. \(a\equiv b~\pmod n\Leftrightarrow ind_ga\equiv ind_gb~\pmod {\varphi(p)}\)
2. \(ind_g(ab)\equiv ind(a)+ind(b)~\pmod {\varphi(p)}\)
3. \(ind_g(a^n)\equiv n\times ind(a)~\pmod {\varphi(p)}\)

3.3 求指标的方法

• 求指标的运算也叫做离散对数。
• 求指标即求 \(g^x\equiv a\pmod p\) 的最小自然数解。
• 使用 \(BSGS\) 算法即可。

4. N次剩余问题

• 问题：求解 \(x^N\equiv a\pmod p\) 在模 \(p\) 意义下的所有解，\(p\) 是质数。
• 首先我们知道，当 \(a\equiv 0\pmod p\) 时，方程只有 \(x=0\) 一个解。
• 否则 \(x\in[1,p)\)。
• 我们先找到 \(p\) 的最小原根 \(g\)。
• 因为 \(p\) 是质数且 \(p\nmid a\)，所以每个 \(x\in[1,p)\)，我们都能找到 \(y=ind_gx\) 和 \(t=ind_ga\)。
• 那么原方程等价于 \(yN\equiv t\pmod {(p-1)}\)。
• 那么我们只需要用 \(exgcd\) 解这个简单的同余方程即可。
• 当 \((N,p-1)\nmid t\) 时，原方程无解。
• 否则我们求出最小自然数解 \(y_0\)，然后将在 \([1,p)\) 内的 \(y=y_0+k·\frac{p-1}{(N,p-1)}(k\in \mathbb Z)\) 的 \(y\) 记录下来。
• 然后所有的 \(g^y\) 即为答案。
• 代码：（BZOJ1319）

#include <bits/stdc++.h>

int p, K, a, g, t;
int anscnt, ans[1000010];

inline int qpow(int a, int b, const int &p)
{
    int res = 1;
    for (; b; b >>= 1, a = 1LL * a * a % p)
        if (b & 1)
            res = 1LL * res * a % p;
    return res;
}

inline int find_root(const int &p)
{
    int n = p - 1, x = p - 1;
    static int div[1000010], cnt;

    cnt = 0;
    for (int i = 2; i * i <= n; ++i)
        if (x % i == 0)
        {
            div[++cnt] = i;
            while (x % i == 0)
                x /= i;
        }
    if (x > 1)
        div[++cnt] = x;
    for (int g = 1; g <= p; ++g)
    {
        bool flg = true;
        for (int i = 1; i <= cnt; ++i)
            if (qpow(g, (p - 1) / div[i], p) == 1)
            {
                flg = false;
                break;
            }
        if (flg)
            return g;
    }
    return -1;
}

inline int solve_BSGS(const int &a, const int &b, const int &p)
{
    std::map<int, int> ha;
    ha.clear();

    int t = ceil(sqrt(p)), x = 1;
    for (int i = 1; i <= t; ++i)
    {
        x = 1LL * x * a % p;
        ha[1LL * x * b % p] = i;
    }
    int y = x;
    for (int i = 1; i <= t; ++i)
    {
        if (ha.find(y) != ha.end())
            return i * t - ha[y];
        y = 1LL * y * x % p;
    }
    return -1;
}

inline int exgcd(const int &a, const int &b, int &x, int &y)
{
    if (!b)
        return x = 1, y = 0, a;
    int res = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return res;
}

int main()
{
    scanf("%d%d%d", &p, &K, &a);
    if (a == 0)
        return puts("1\n0"), 0;

    g = find_root(p);
    t = solve_BSGS(g, a, p);

    int x, y;
    int d = exgcd(p - 1, K, x, y);

    if (t % d)
        return puts("0"), 0;

    int mod = (p - 1) / d;
    y = (1LL * y * (t / d) % mod + mod) % mod;

    for (; y < p; y += mod)
        ans[++anscnt] = qpow(g, y, p);

    std::sort(ans + 1, ans + anscnt + 1);
    printf("%d\n", anscnt);
    for (int i = 1; i <= anscnt; ++i)
        printf("%d\n", ans[i]);

    return 0;
}