离散对数阶原根剩余_算法

离散对数/阶/原根/剩余/数论科技

都是离散同余的内容。

离散对数

若 $a\perp p$，且 $a^x\equiv b\pmod p$，则 $x$ 称作离散对数 $\log_ab$。

BSGS 算法

对质数 $p$，给定 $a,b$ 求解 $x$ 需要用到 $\text{BSGS}$ 算法。

事实上求解离散对数是数论中的经典难题，其难解性产生了非对称 $\text{RSA}$ 加密算法。

$\text{BSGS}$ 算法的复杂度是 $\Theta(\sqrt p)$ 的。

考虑将这个 $\Theta(p)$ 规模的问题转化为求是否有两个 $\Theta(\sqrt p)$ 规模的数据相等，这样我们就可以查表解决。

考虑设阈值 $B=\sqrt p$，这样我们可以把 $x$ 写成 $uB-v(u\ge 1,v\in[1,p])$ 的形式。

也即 $a^{uB}\equiv a^{v}b$，而 $a^{uB}$ 与 $a^{v}b$ 分别只有 $\Theta(\sqrt p)$ 种，直接查表解决。

exBSGS

模数不一定为质数。

考虑能否沿用上述思路，这种情况下最大的坏处就是逆元不一定存在，所以上式的最后一步并不成立。

事实上取 $B=\sqrt {2\varphi(p)}$，先将所有 $a^{uB}$ 正序加入表中，注意有重复值的话要保留前两个，再查表 $a^{v}b$ 并检验 $a^{uB-v}\equiv b\pmod p$ 是否成立，检验可以使用 $a^{uB-v}=a^{(u-1)B}a^{B-v}$。

答案上界是 $2\varphi(p)$，证明考虑反证法，如果存在答案 $x>2\varphi(p)$，则根据扩展欧拉定理我们可以得到一个更小解 $x\bmod\varphi(p)+\varphi(p)$。

阶与原根

题外话：对于 $m>1$ 的简化剩余系 $\mathbb K_m$ 在乘法下封闭，满足结合律，存在逆元和单位元（是一个群），则我们可以从这个角度理解阶与原根（循环群的生成元）。

阶

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

理解这部分可能需要用到经典的一个结论：一个长为 $n$ 的环每次跳 $a$ 步则会产生 $\gcd(a,n)$ 个环，环长为 $\frac{n}{\gcd(a,n)}$。

阶就是一个环长，或者说步数，与之对应的是步长。

性质：

• 阶和字符串的最小正周期有异曲同工之妙，$a^x\equiv1\pmod m\iff\delta_m(a)\mid x$。

证明考虑反证法，若 $\delta_m(a)\nmid x$，由于 $a^x\equiv a^{\delta_m(a)}\equiv 1\pmod m$，所以不用担心没有逆元的情况，可以在等式两边任意乘除，也就是在指数上任意加减，根据裴蜀定理 $a^{x\bmod \delta_m(a)}\equiv 1\pmod p$，而 $x\bmod \delta_m(a)\in(0,\delta_m(a))$，与阶的定义矛盾。

• $\delta_m(a)$ 存在当且仅当 $a\perp m$，这个是常识。
• $\delta_m(a^k)=\frac{\delta_m(a)}{\gcd(\delta_m(a),k)}=\frac{\text{lcm}(\delta_m(a),k)}{k}$，运用步长来理解，这也告诉我们 $\exist k,x^k\equiv y\pmod p\iff \delta_p(y)\mid\delta_p(x)$，求解前者我们通常会选择离散对数 $\Theta(\sqrt p)$，而求解后者我们可以使用 $\text{Pollard-Rho}$ 算法分解 $\varphi(p)$ 的质因数然后试除法解决。

注意阶的环和置换环有一些区别，置换环上长度为 $x$ 的环有 $\frac n x$ 个，而阶中只有一个这样的环，因为阶的指数是 $x,2x,3x,\cdots$，没有 $x+1,2x+1$ 这种结构，阶越大步长越小环越长，能表示的东西越多。

群的理解下置换环因为可以转，所以关心子群和所有陪集，而阶是有固定的原点 $1$ 的，不含 $1$ 的陪集不关心，所以我们只关心子

由上面最后一条，求 $\delta_m(a)$ 我们只需要对 $\varphi(m)$ 分解质因数然后试除即可。

[ABC335G] Discrete Logarithm Problems

给定一个序列和质数 $p$，求有多少 $(i,j)$ 满足 $\exist k,a_i^k\equiv a_j\pmod p$。

$p\le 10^{13},n\le 2\times 10^5$。

应用上面的结论我们发现原数没用了，只需要求每个数的阶然后对阶统计即可，发现 $d(\varphi(m))\le 10^4$，所以直接 $\Theta(d^2)$ 暴力统计即可。

P6730 [WC2020] 猜数游戏

给定一个序列 $a$ 和奇质数幂 $p^k$，定义 $x$ 能生成 $y$ 当且仅当 $\exist r,x^r\equiv y\pmod {p^k}$，定义一个集合的权值是选出最少的集合中的数的个数，使得这个集合可以被生成，求所有子集的权值和。

$n\le 5000,p^k\le 10^8$。

考虑枚举每个数，统计每个数的贡献。

假定生成关系是单向的，若是双向则钦定编号小的生成编号大的。

所以一个数产生贡献当且仅当集合中所有的数都无法生成它，设 $c$ 个数可以生成它，则贡献为 $2^{n-c}$。

若 $a\perp p$，则使用阶的结论判断是否整除即可。

若 $a\not\perp p$，则生成它的数 $\Theta(\log V)$ 次幂以内必到达 $0$，暴力枚举所有 $b\not\perp p$ 能否生成它即可。

原根

若 $\delta_m(g)=\varphi(m)$，则称 $g$ 为 $m$ 的原根。

性质：

• $\forall p\in\mathbb P,i\in[1,p),g^i\bmod p$ 两两不同。

这是它最有用的性质，这意味着在求解同余方程时我们可以把所有非零数都换成原根的幂次，从而进一步化简求解。

• 原根判定：求阶即可。
• 原根的存在性：$m$ 存在原根当且仅当 $m=2,4,2p^k,4p^k$，其中 $p$ 是奇质数。
• 若 $m$ 存在原根，则 $|\{a|\delta_m(a)=l\}|=\left\{\begin{aligned}&0,&&l\nmid \varphi(m)\\&\varphi(l),&&l\mid \varphi(m)\end{aligned}\right.$，这同样可以用子环长来理解，相当于要求有多少个步数使得最终得到的环长为 $l$，任取 $\delta_m(a)=l$，则 $a^i(i\perp l)$ 取遍了所有 $\{a|\delta_m(a)=l\}$。
• 由上条，若 $m$ 存在原根，则 $m$ 的原根个数为 $\varphi(\varphi(m))$。
• 最小原根的数量级为 $\mathcal O(m^{\frac 1 4+\epsilon})$，求出任意一个原根 $g$，则其他原根可表示为 $g^i(i\perp\varphi(m))$。

原根与单位根基本等价，单位根有的性质原根基本都有，原根可以替代单位根来实现 $\text{NTT}$。

口胡题

给定 $n$ 个操作和一个初始为 $1$ 的变量 $x$，每个操作形如 $x\gets a_i$ 或 $x\gets x\cdot a_i$，求选出任意操作后任意排列后 $x\bmod p$ 有多少种不同的取值，每个操作只能执行一次。

$n\le 10^6,p\in \mathbb P\cap[2, 2\times 10^5]$。

首先由于 $p\le 2\times 10^5$，我们可以暴力找原根暴力求出原根的每个幂次对应的值，所以我们可以求出 $a_i=g^{b_i}$。

接下来我们发现一定是先赋值再乘，乘法已经被我们转化成了加法，于是我们接下来跑一个背包 $\Theta(\frac {nq}\omega)$，但过不了。

考虑哈希 + 二分，因为这是一个循环串，所以找到一个 $1$ 对应 $0$ 那么一定有一个 $0$ 对应 $1$。

二次剩余

对 $p\nmid a$，若存在 $x^2\equiv a\pmod p$，则 $a$ 是二次剩余，否则 $a$ 是二次非剩余。

若 $p\mid a$，则 $a$ 什么也不是。

$\text{Legendre}$（勒让德）符号：

$$\left(\frac{a}{p}\right)=\left\{\begin{aligned}&1,&&p\nmid a,\exist x\equiv a\pmod p\\&{-1},&&p\nmid a,\nexists x\equiv a\pmod p\\&0,&&p\mid a\end{aligned}\right.$$

其意义为 $\bmod\ p$ 意义下 $x^2\equiv a$ 的解的个数 $-\ 1$。

二次互反律：对不同奇素数 $p,q$，$\left(\frac p q\right)\left(\frac q p\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}$。

性质：

• 若奇素数 $p$ 有原根 $g$，$x=g^k(k\in[1,p))$，则 $x$ 是二次剩余当且仅当 $2\mid k$，证明就是反证法，若 $x^2\equiv g^k\pmod p$，则 $k\bmod p-1$ 一定是偶数，则 $k$ 一定是偶数。

从这一点可以看出，二次剩余和二次非剩余各占一半，数量都为 $\frac{p-1}{2}$，就像实数中的正数和负数一样。

• $\text{Euler}$ 判别准则：$a^{\frac{p-1}{2}}\equiv \left(\frac a p\right)\pmod p$，可以判断一个数是否为二次剩余，从这一点中可以看出 $p$ 固定时 $\left(\frac a p\right)$ 是完全积性函数。

求法：P5491 【模板】二次剩余

$T$ 组数据求解 $x^2\equiv a\pmod p$ 的所有解，$p$ 是奇质数。

$T\le 10^4,a<p\le 10^9+9$。

只需要找到其中一个 $x$，另一个即为 $-x$。

请出大名鼎鼎的 $\text{Cipolla}$ 算法。

我们先叙述一遍算法流程：

• 找到正整数 $b$ 使得 $\omega=b^2-a$ 为二次非剩余。
• 扩域，令 $i=\sqrt \omega$，则 $(b+i)^{p+1}\equiv a\pmod p$，则 $(b+i)^{\frac{p+1}{2}}$ 为二次剩余。

是不是觉得莫名其妙的。

首先我们先论证为什么 $(b+i)^{p+1}\equiv a\pmod p$，再说怎么找 $b$。

$$\begin{aligned}&(b+i)^{p+1}\equiv a\pmod p\\\iff&(b+i)(b+i)^p\equiv a\pmod p\\\iff&(b+i)(b^p+i^p)\equiv a\pmod p\\\iff&(b+i)(b+i\omega^{\frac{p-1}{2}})\equiv a\pmod p\\\iff&(b+i)(b-i)=b^2-\omega\equiv a\pmod p\end{aligned}$$

其中第二行到第三行在 $\text{Lucas}$ 定理中有证明。

由于二次非剩余占了一半，可以猜出枚举 $b$ 则 $b^2$ 的二次剩余性比较随机（不会证）。

所以直接暴力找即可，注意特判 $a=0$，此时找不到 $b$。