【学习笔记】原根与指标

1. 阶

1.1 定义

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

1.2 阶的性质

1. 设 $a\perp n$a⊥n，$a^N\equiv 1(mod~n) \Leftrightarrow Ord_n(a)|N$aN≡1(mod n)⇔Ordn​(a)∣N。
2. 设 $a\perp n$a⊥n，$Ord_n(a)|\varphi(n)$Ordn​(a)∣φ(n)。

2. 原根

2.1 定义

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

2.2 解性

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

2.3 原根的性质

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

2.4 求一个数原根的方法

• 我们已知一个数 $n$n 存在原根。
• 我们现在要找到 $n$n 最小的原根。
• 假设我们现在枚举到一个 $g$g，并且 $(g,n)=1$(g,n)=1，要验证 $g$g 是否是 $n$n 的原根。
• 根据 $Ord_n(g)|\varphi(n)$Ordn​(g)∣φ(n)，我们只需要验证对于每个 $d|\varphi(n)(d\neq \varphi(n))$d∣φ(n)(d̸​=φ(n))，是否均满足 $g^d\not\equiv 1(mod~n)$gd̸​≡1(mod n)。
• 我们设 $\varphi(n)=\prod_{i=1}^cp_i^{k_i}$φ(n)=∏i=1c​piki​​（$p_i$pi​ 是质数）。
• 因为若 $g^d\equiv 1(mod~n)$gd≡1(mod n)，则 $g^{dk}\equiv 1(mod~n)$gdk≡1(mod n)，所以我们只需要验证，对于每个 $i$i，均满足 $g^{\frac{n}{p_i}}\not\equiv1(mod~n)$gpi​n​̸​≡1(mod 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$g 是 $n$n 的一个原根，整数 $a \perp n$a⊥n，则在模 $\varphi(n)$φ(n) 意义下有唯一的整数 $x$x，使得 $g^x\equiv a(mod~n)$gx≡a(mod n)，则称 $x$x 为以 $g$g 为底对模 $n$n 的一个指标，记作 $x=ind_ga$x=indg​a。

3.2 指标的性质

1. $a\equiv b~(mod~p)\Leftrightarrow ind_ga\equiv ind_gb~(mod~\varphi(p))$a≡b (mod p)⇔indg​a≡indg​b (mod φ(p))
2. $ind_g(ab)\equiv ind(a)+ind(b)~(mod~\varphi(p))$indg​(ab)≡ind(a)+ind(b) (mod φ(p))
3. $ind_g(a^n)\equiv n\times ind(a)~(mod~\varphi(p))$indg​(an)≡n×ind(a) (mod φ(p))

3.3 求指标的方法

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

4. N次剩余问题

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