高次剩余问题：
给定正整数 $a, y, p$，其中 $p$ 是质数，求 $x \in [0, p)$ 满足：
$$
x^a \equiv y \pmod p
$$
此处的 $x$ 被称为一个高次剩余，有时也译作离散根（discrete root）。
前置知识 - 原根：
定义 1（阶）： 满足模方程 $a^d \equiv 1 \pmod p$ 的最小正整数 $d$ 被称为模 $p$ 意义下 $a$ 的一个阶（order），常用 $\textrm{ord}_p a$ 或 $\delta_p(a)$ 表示。
定理 1.1： $\textrm{ord}_p a | \varphi(p)$。
证明：令 $d = \textrm{ord}_p a$，假设 $d \not | \varphi(p)$，设 $\varphi(p) = \alpha \times d + b$，其中 $b \in [1, d)$。
由欧拉定理 $a^{\varphi(p)} \equiv 1 \pmod p$，故 $a^{\alpha \times d + b} \equiv 1 \pmod p$，可推得 $a^b \equiv 1 \pmod p$
由于 $b < d$ 且 $a^b \equiv 1 \pmod p$，故我们推出了一个更小的阶 $b$，出现矛盾，得证！
定理 1.2： 令模 $p$ 意义下 $a$ 的一个阶为 $d’$，则 $a^0 \bmod p, a^1 \bmod p, \cdots a^{d’-1} \bmod p$ 互不相同。
证明： 若存在 $i, j \in [0, d’)$ 使得 $i > j$，$a^i \equiv a^j \pmod p$，则移项后有 $a^{i-j} \equiv 1 \pmod p$。
由于 $i > j$ 故 $i-j>0$，且易证 $i-j < d’$，故我们找到了一个更小的阶 $i-j$，出现矛盾，得证！
定义 2（原根）：若存在整数 $g \in [0, p)$，使得模 $p$ 意义下，$g$ 的阶等于 $\varphi(p)$，则称 $g$ 为模 $p$ 意义下的一个原根（primitive root）。
下面不加证明的给出三个定理。
定理 2.1： 对于任何大于 $2$ 的质数 $p$ 与所有正整数 $e$，当 $n = 2, 4, p^e, 2p^e$ 时，存在模 $n$ 意义下的原根。
定理 2.2： 若存在模 $n$ 意义下的原根，则模 $n$ 大小不超过 $n$ 的原根有 $\varphi(\varphi(n))$ 个。
**定理 2.3： **$g^0 \pmod p, g^1 \pmod p, \cdots, g^{p-2} \pmod p$ 这 $p-1$ 个数互不相同。
事实上定理 2.3 = 定义 2 + 定理 1.2
关于离散对数，指标的定义说法不一，本文使用如下定义：
定义 3（离散对数）： $p > 1$，正整数 $a, b \in [0, p)$，若存在 $k$ 使得 $a^k \equiv b \pmod p$，则称 $k$ 为模 $p$ 意义下到基 $a$ 上 $b$ 的一个离散对数（discrete logarithm）。
定义 4（指标）： 令 $p$ 原根为 $g$，$b \in [0, p)$，则指标（index）为模 $p$ 意义下到基 $g$ 上 $b$ 的离散对数，记作 $\textrm{ind}_g b$。
容易看出离散对数，指标可以使用 Shank 的大步小步算法计算。
怎么求原根？
设 $\varphi(p)$ 的唯一分解式为 ${p_1}^{x_1} {p_2}^{x_2} \cdots p_{cnt}^{x_{cnt}}$。
则由原根的定义，可知：$\forall i \in [1, cnt]$，$g^{\frac{\varphi(p)}{p_i}} \not\equiv 1 \pmod p$
质因数分解 $\varphi(p)$ 后，暴力枚举 $g$ 即可。
原根的密度很大，最小原根一般很小，所以不必特别担心复杂度。
怎么求模质数意义下的高次剩余？
重新审视这个式子。
$$
x^a \equiv y \pmod p
$$
注意到 $p$ 是质数，模 $p$ 意义下，一定有原根 $g$。
由性质 2.3 可知，$g^0 \pmod p, g^1 \pmod p, \cdots, g^{p-2} \pmod p$ 这 $p-1$ 个数互不相同。
设 $x \equiv g^{\lambda} \pmod p$，$y \equiv g^{\beta} \pmod p$，则有：
$$
g^{a\lambda} \equiv g^{\beta} \pmod p
$$
注意到 $\beta$ 可以使用大步小步算法求出。
由性质 2.3 可知 $a\lambda \equiv \beta \pmod {p-1}$
证明： 设 $a \lambda - \beta \equiv k \pmod {p-1}$，其中 $k \in [1, p-2]$。
则 $g^{a\lambda} \equiv g^{\beta} \pmod p \rightarrow g^{k} \equiv 1 \pmod p$
由性质 2.3 可知，$g^0 \pmod p, g^1 \pmod p, \cdots, g^{p-2} \pmod p$ 这 $p-1$ 个数互不相同。因为 $g^0 \equiv 1 \pmod p$，且 $k \neq 0$，可知 $g^k \not \equiv 1 \pmod p$，出现矛盾！得证！
注意到上式是一个不定方程，可以使用扩展欧几里得算法求解出 $\lambda$。
最后使用快速幂计算 $x = g^{\lambda} \bmod p$ 即可。
代码
1 |
|