原根与高次剩余

· · 算法·理论

阶:

使得 a^x \equiv 1 \pmod m 最小的正整数 x 被称为 a 模 m 的阶，记作 \delta_m(a) 。

充要条件：

### $1$ 的性质： 例如它和所有数互质，且 $1$ 的任何次幂均为 $1$ ，且 $1$ 是 $1$ 在模任何正整数意义下的乘法逆元，因此我们可以在同余方程的任意位置除以已经被证明等于 $1$ 的部分，而不需要担心不存在逆元。**（重要）** ### 阶的性质： **1.** 所有使得 $a^x \equiv 1 \pmod m$ 的 $x$ 一定为阶的倍数。 证明考虑反证法，则 $x$ 模 $\delta_m(a)$ 一定 $<\delta_m(a)$ ，矛盾。 **2.** $\delta_m(a^k)=\delta_m(a) /gcd(\delta_m(a),k)$ 。 证明：首先有 $(a^k)^x=a^{kx}$ ,那么一定有 $\delta_m(a) \mid kx$ ,满足条件的最小的 $x$ 为 $\delta_m(a) /gcd(\delta_m(a),k)$ 。可行性感性理解。 一个应用：**求 $a^x \equiv b \pmod m$ 的通解。** 首先有循环节 $\delta_m(a)$ 那么可以 $BSGS$ 求最小和次小解即可。 ### 求解 $\delta_m(a)$: **1.** $BSGS$ ,复杂度 $\mathcal O(\sqrt m)

2. 考虑通过赋初值为 \phi(m) ，逐步除质因子判断次数实现。加上 pollard-rho 可实现 \mathcal O(m^{0.25}) 。

原根：

使得 \delta_m(a)=\phi(m) 的 a 为 m 的原根。

人话:若干次幂取遍了所有与 m 互质的数的数，相当于可以用这个数生成出与 m 互质的数。（不一定存在）

判定:

若对于所有为 \phi(m) 的质因子 p ,均有 a^{\phi(m)/p} \not\equiv 1 \pmod m ，则 a 为原根。

性质：

若 m 存在原根，则考虑 \delta_m(a)=l 的 a 的个数，有:

若 l \nmid \phi(m) 为 0 ，否则为 \phi(l) 。

考虑证明后半部分：原根 g 的定义很重要，一次取遍了所有互质的数。

那么所有的数可以表示成 g^k 的形式，那么满足 \delta_m(g^k)=\delta_m(g) /gcd(\delta_m(g),k)=\phi(m)/gcd(\phi(m),k)=l 的 k 的个数为 \phi(\phi(m)/(\phi(m)/l))=\phi(l) 。

后半部分是这个：使得 gcd(n,x)=d 的 x 个数为 \phi(n/d) ，证明考虑同时除以 d 即可。

上式带入 \phi(m) 可得到原根的个数：\phi(\phi(m)) 。

求原根：

首先知道了一个原根 g ，那么 g^k \mod m(k \bot \phi(m)) 也为原根(gcd(\phi(m),k)=1)。

那么现在考虑求一个原根：枚举+判定！王元院士证明了最小原根大约为 m^{0.25} ,则可以在预处理最小质因数的前提下达成 \mathcal O(m^{0.25}\omega(m) \log m) 。

应用：

首先原根与 m 次单位根同构，所以可以用来求 NTT (略)。

当 m 为质数 or 质数幂次时可以生成任何数(将 x 用 g^k 代替)。

例题：

1.P5605

没什么好说的，学了基本能推出来:存在 x^a \equiv y \pmod m 的前提条件是 \delta_m(y) \mid \delta_m(x) ,条件为 y \mid m 。

拿个 Pollard-Rho 做完了。