二次同余式与平方剩余
二次同余式与平方剩余
定义
一般二次同余式是形如 $ax^2+bx+c \equiv 0 \pmod m$ 的方程，需要在 $\log$ 时间内求出方程的解。
接下来我们分类讨论一下这个方程的解法。
首先由中国剩余定理得对于 $m=p_1^{c_1}p_2^{c_2}\dots p_k^{c_k}$，如果 $ax^2+bx+c \equiv 0 \pmod {p^k}$ 都有解，那就可以合并出来一组合法的 $x$。
处理
首先我们只需要解决 $ax^2+bx+c \equiv 0 \pmod {p^k}$ 的问题，如果 $p^{\alpha} \le p_k$ 并且 $p^{\alpha} \mid \gcd(a,b,c)$ 那么我们可以得到另外一个方程 $\frac a {p^{\alpha}}x^2+\frac b {p^{\alpha}}x+c \equiv 0 \pmod {p^{k-\alpha}}$，这两个方程完全等价，故问题缩小到了 $p \not\mid \gcd(a,b,c)$ 的问题。
如果 $p \mid a$ 且 $p \mid b$，那么 $p \not\mid c$，所以方程无解。
如果 $p \mid a$ 并且 $p \not\mid b$，那么 $f’(x)=2ax+b \equiv 0 \pmod p$ 无解，根据同余式的一些性质，它有解的充分必要条件是 $ax^2+bx+c \equiv 0 \pmod p$ 有解，因为 $\gcd(b,p)=1$，所以此方程一定有解。
还有 $p \not\mid a$ 和 $p=2$ 的时候的情况，这些情况最终可以归约成 $x^2 \equiv a \pmod {p^k}$ 的情况，具体推导就不展开了，留作以后补充或者复习。
再优化
因为问题缩小到了 $x^2 \equiv a \pmod {p^k}$，如果 $p^k$ 很大，那么我们可以使用 BSGS 求解。
下面我们假设 $k=1$，并且介绍一种 $\log$ 的解法，下面的 $p$ 都是任意奇质数。
Euler 判别法
如果 $a^{\frac {p-1}2} \equiv 1 \pmod p$，那么 $a$ 在模 $p$ 意义下有二次剩余，否则没有。
先有一个引理：
如果 $n \le p$，那么方程 $x^n+\sum_{i=0}^{n-1} a_ix^i \equiv 0 \pmod p$ 有 $n$ 个解当且仅当存在整系数多项式 $q(x),r(x)(\deg r<n)$ 使得 $x^p-x=f(x)q(x)+pr(x)$。
这个引理的证明参见 OI-wiki。
证明如下：
如果 $\gcd(a,p) \not= 1$，那么显然不可能满足上式，也不可能有二次剩余。（$a=0$）
否则 $\gcd(a,p)=1$，那么由费马小定理得 $a^{p-1} \equiv 1 \pmod p$，那么 $(a^{\frac {p-1}2}-1)(a^{\frac {p-1}2}+1) \equiv 0 \pmod p$。
所以因为 $x^2 \equiv a \pmod p$，所以 $x^{p-1}-a^{\frac {p-1}2}=(x^2)^{\frac {p-1}{2}}-a^{\frac {p-1}2}=(x^2-a)P(x)$，其中 $P(x)$ 是某整系数多项式，就有：
- $x^p-x=x(x^{p-1}-a^{\frac {p-1}{2}})+x(a^{\frac {p-1}2}-1)=(x^2-a)xP(x)+(a^{\frac {p-1}2}-1)x$。
由引理得 $a$ 是模 $p$ 的二次剩余当且仅当 $a^{\frac {p-1}2} \equiv 1 \pmod p$，所以 $a$ 是模 $p$ 的非二次剩余当且仅当 $a^{\frac {p-1}{2}} \not \equiv 1 \pmod p$。
相关定理
设 $n \not \mid p-1,p \not\mid a$，那么方程 $x^n \equiv a \pmod p$ 有解当且仅当 $a^{\frac {p-1}n} \equiv 1 \pmod p$，且解数为 $n$。
证明如下（很像上面的证明）：
充分性：
因为 $x^n \equiv a \pmod p$，所以 $x^{p-1}-a^{\frac {p-1}n}=(x^n)^{\frac {p-1}{n}}-a^{\frac {p-1}n}=(x^n-a)P(x)$，其中 $P(x)$ 是某整系数多项式，就有：
- $x^p-x=x(x^{p-1}-a^{\frac {p-1}{n}})+x(a^{\frac {p-1}n}-1)=(x^n-a)xP(x)+(a^{\frac {p-1}n}-1)x$。
由引理得 $a$ 是模 $p$ 的 $n$ 次剩余当且仅当 $a^{\frac {p-1}n} \equiv 1 \pmod p$，所以 $a$ 是模 $p$ 的非 $n$ 次剩余当且仅当 $a^{\frac {p-1}{n}} \not \equiv 1 \pmod p$，并且有 $n$ 个解。
必要性：
如果 $x_0$ 是一解，那么 $(x_0^n)^{\frac {p-1}{n}} \equiv 1$，那么 $a^{\frac {p-1}n} \equiv 1$。
二次剩余的数量
根据欧拉判别法，我们需要计算 $a^{\frac {p-1}2} \equiv 1 \pmod p$ 的 $a$ 有多少个，由上面的相关定理，所以 $a$ 有 $\frac {p-1}{2}$ 个，并且这几个的恰好与 $1^2,2^2,\dots,({\frac {p-1}{2}})^2$ 中的一个同余，并且形成一个排列的关系。（两两不重复）
证明如下：
如果 $1 \le k < l \le \frac {p-1}2$，那么说明 $x^2 \equiv k^2$ 有四个解 $x=+k,-k+l,-l \pmod p$，与前面的只有两个解相违背，所以此条件成立。
Cipolla 算法
为了解决 $x^2 \equiv a \pmod p$ 的问题，我们首先随机一个数 $r$ 满足 $r^2-a$ 为二次非剩余，因为二次剩余和非二次剩余的数量差不多，所以这个 $r$ 可以很快找到。
然后因为不存在 $i$ 使得 $i^2 \equiv r^2-a$，那么就像 $\sqrt{-1}$ 一样扩域，即在模 $p$ 的简化剩余系加一个元素 $i$，新的域中的每个数都可以写成 $a+bi$ 的形式。
同理我们可以定义加法 $A+B=(A_a+B_a)+(A_b+B_b)i$，乘法 $AB=(A_aB_a+A_bB_bi^2)+(A_aB_b+A_bB_a)i$，同时还有逆元。
引理 $1$：$i^p=-i$，证明：$i^p=i(i^2)^{\frac {p-1}2}=i(r^2-a)^{\frac {p-1}2}=-i$。
引理 $2$：$(A+B)^p \equiv A^p+B^p$，考虑使用二项式展开，因为 $p$ 是质数，所以二项式展开之后 $C_p^i$ 中只有 $i=0,p$ 的项不包含 $p$ 因子，所以证明显然。
那么 $(a+i)^{p+1} \equiv n$，证明如下：
$(a+i)^{p+1} \equiv (a^p+i^p)(a+i) \equiv (a-i)(a+i) \equiv a^2-(a^2-n) \equiv n$。
于是 $(a+i)^{\frac {p+1}{2}}$ 就是一个解，另外一个解就是这个解的相反数，如果这个数的虚部不为 $0$，那么我们就可以拿这个当做答案了。
感性理解一下这个数的虚部确实不为 $0$，当然你也可以用反证法证明一下。
于是代码就很好写了，定义一个复数类即可：
1 |
|