浅谈二次剩余

· · 算法·理论

前置：同余方程的基础知识。

记 a/b=\dfrac{a}{b}。

二次剩余

对于满足 \gcd(a,p)=1 的整数 a,p，若存在 x 使得 x^2\equiv a\pmod p，则称 a 为模 p 的二次剩余。

下文默认 \gcd(a,p)=1。

Euler 判别法

对于 奇素数 p 和整数 a，a 为 p 的二次剩余当且仅当 a^{(p-1)/2}\equiv 1\pmod p。 ::::info[证明]{open} 若 a 为二次剩余：

有 x^{p-1}\equiv a^{(p-1)/2}\equiv 1\pmod p。

若 a 不为二次剩余：

易得对于任意 a，有唯一对应的 b=a^{-1}n 使得 ab\equiv n\pmod p 且 a\not=b。由威尔逊定理可知 a^{(p-1)/2}\equiv (p-1)!\pmod p。 ::::::::

关于二次剩余数量的推论

对于奇素数 p，其二次剩余数量为 (p-1)/2。

::::info[证明]{open} 若 m^2\equiv n^2\pmod p，则有 p\mid (m+n)(m-n)，可知 m+n=p。于是对于所有 n\in [1,(p-1)/2]，其对应的 m>(p-1)/2。由此可知 1\sim (p-1)/2 的平方模 p 分别对应一个二次剩余。 ::::

Legendre 符号

对于 奇素数 p，我们记

\left(\dfrac{a}{p}\right)\equiv\begin{cases}0,&p\mid a,\\1,&\exists x\in \mathbf{Z}_p,x^2\equiv a\pmod p,\\-1,&\mathrm{otherwise.}\end{cases}

即对于 a,p，a 是 p 的二次剩余当且仅当 \left(\dfrac{a}{p}\right)=1。

性质

  1. 由定义可知 a^{(p-1)/2}\equiv \left(\dfrac{a}{p}\right)\pmod p。

  2. 完全积性：\left(\dfrac{ab}{p}\right)=\left(\dfrac{a}{p}\right)\left(\dfrac{b}{p}\right)。\ 由 \left(\dfrac{ab}{p}\right)\equiv a^{(p-1)/2}b^{(p-1)/2}\equiv \left(\dfrac{a}{p}\right)\left(\dfrac{b}{p}\right)\pmod p，同时 \left|\left(\dfrac{ab}{p}\right)-\left(\dfrac{a}{p}\right)\left(\dfrac{b}{p}\right)\right|\le 2<p 得证。

    二次互反律

    设 p,q 是两个不同的奇素数，则有

\left(\dfrac{p}{q}\right)\left(\dfrac{q}{p}\right)=(-1)^{(p-1)(q-1)/4}

::::info[引理 1（Gauss 引理）]{open} 对于奇素数 p 和整数 n,1\le k\le (p-1)/2，令 r_k=nk\bmod p，设 A=\{r_k\mid r_k>p/2\},B=\{r_k\mid r_k<p/2\}，则有

\left(\dfrac{n}{p}\right)=(-1)^{|A|}

:::: ::::info[引理 1 证明]{open} 我们有

n^{(p-1)/2}\prod_{k=1}^{(p-1)/2} k\equiv \prod_{a\in A}a\prod_{b\in B}b \pmod p

。由 \forall a\in A,p/2<a<p 可知 0<p-b<p/2。而 \forall a\in A,p-a\not\in B，这是由于若存在，则由定义可知存在 k_1,k_2 使得 a=nk_1\bmod p,b=nk_2\bmod p，由此有 p\mid k_1+k_2 且 k_1+k_2<p，引出矛盾。

易得 |A|+|B|=(p-1)/2，则有 \prod_{a\in A}a\prod_{b\in B}b\equiv \prod_{a\in A}(p-a)\prod_{b\in B} b\equiv (-1)^{|A|}\prod_{k=1}^{(p-1)/2} k\pmod p。

于是有 $\left(\dfrac{n}{p}\right)\equiv n^{(p-1)/2}\equiv (-1)^{ A }\pmod p$。

::::info[推论 1]{open} 对于奇素数 p 和奇数 n，有

\left(\dfrac{n}{p}\right)=(-1)^{\sum_{i=1}^{(p-1)/2}\left\lfloor ni/p\right\rfloor}

:::: ::::info[推论 1 证明]{open}

\begin{aligned}n\sum_{k=1}^{(p-1)/2}k&=p\sum_{k=1}^{(p-1)/2} \left\lfloor nk/p\right\rfloor+\sum_{a\in A}a+\sum_{b\in B} b\\&=p\sum_{k=1}^{(p-1)/2} \left\lfloor nk/p\right\rfloor+\sum_{a\in A}(p-a)+\sum_{b\in B}b+2\sum_{a\in A} a-p|A|\\&=p\sum_{k=1}^{(p-1)/2} \left\lfloor nk/p\right\rfloor+\sum_{k=1}^{(p-1)/2} k+2\sum_{a\in A} a-p|A|\end{aligned}

因此有

(n-1)\sum^{(p-1)/2}_{k=1} k=p\sum_{k=1}^{(p-1)/2} \left\lfloor nk/p\right\rfloor+2\sum_{a\in A} a-p|A|

因此在 2\nmid n 时，移项可得

|A|\equiv\sum_{k=1}^{(p-1)/2}\left\lfloor nk/p\right\rfloor\pmod 2
带入 $\left(\dfrac{n}{p}\right)=(-1)^{ A }$ 即得证。

::::info[证明]{open} 由上述推论，证明 \left(\dfrac{p}{q}\right)\left(\dfrac{q}{p}\right)=(-1)^{(p-1)(q-1)/4} 即证明

(p-1)(q-1)/4=\sum_{k=1}^{(p-1)/2}\left\lfloor qk/p\right\rfloor+\sum_{k=1}^{(q-1)/2}\left\lfloor pk/q\right\rfloor

考虑平面内 x\in[1,(p-1)/2],y\in[1,(q-1)/2] 的点 (x,y)，其被直线 l:y=(q/p)x 分为两部分。其下方点数即 \sum_{k=1}^{(p-1)/2}\left\lfloor qk/p\right\rfloor，上方点数同理。故命题得证。 ::::

Cipolla 算法

对于奇素数 p 和整数 a，求方程 x^2\equiv a\pmod p 的解。

考虑找到一个数 r 使得 r^2-a 不是二次剩余，则 (r+\sqrt{r^2-a})^{(p+1)/2} 是方程的一个解。 ::::info[随机找 r 的期望次数]{open} 每个 r 满足不是二次剩余的概率为 (p-1)/2，因此期望次数为 2p/(p-1)，约为 2。 :::: ::::info[引理 2]{open}

(a+b)^p\equiv a^p+b^p\pmod p

考虑二项式定理即可证明。 :::: ::::info[正确性证明]{open} 记 w=\sqrt{r^2-a}，由 引理 2 有

(r+w)^p\equiv r^p+w^p\equiv r^{p-1}r+(w^2)^{(p-1)/2}w\equiv r-w\pmod p

，因此有 (r+w)^{p+1}\equiv (r+w)(r-w)\equiv a\pmod p。 ::::

需要实现一个复数类。复杂度 O(\log p)。

Tonelli–Shanks 算法

对于奇素数 p 和整数 a，求方程 x^2\equiv a\pmod p 的解。

令 p=m2^n，m 为奇数。找到 r 使得 r 不是二次剩余。令 g\equiv r^m\pmod p,b\equiv a^{(m-1)/2}\pmod p。则存在偶数 e\in[0,2^n-1]，使得 abg^{-e/2} 是方程的一个解。 ::::info[阶]{open} 定义满足 a^{n}\equiv 1\pmod p 的最小的 n 为 a 模 p 的阶，记为 \delta_p(a)。 :::: ::::info[引理 3（阶的性质）]{open} 若正整数 n 满足 a^n\equiv 1\pmod p，则有 \delta_p(a)\mid n。 :::: ::::info[引理 3 证明]{open} 必要性：

a^n\equiv a^{n\bmod \delta_p(a)}a^{\delta_p(a)\left\lfloor n/\delta_p(a)\right\rfloor}\equiv a^{n\bmod \delta_p(a)}\equiv 1\pmod p

若 n\bmod \delta_p(a)\not=0，则违反了阶的最小性。

充分性显然。 :::: ::::info[正确性证明]{open} 由于

g^{2^n}\equiv r^{m2^n}\equiv r^{p-1}\equiv 1\pmod p

且

g^{2^{n-1}}\equiv r^{m2^{n-1}}\equiv r^{(p-1)/2}\equiv -1\pmod p

所以有 \delta_p(a)\mid 2^n 且 \delta_p(g)\nmid 2^{n-1}，故 \delta_p(g)=2^n。又由于

(ab^2)^{2^n}\equiv a^{m2^n}\equiv a^{p-1}\equiv 1\pmod p

所以 a^m 为 g 的幂次。令 a^m\equiv g^e\pmod p，又由

g^{e2^{n-1}}\equiv a^{m2^{n-1}}\equiv 1\pmod p

故 2^n\mid e2^{n-1}，即偶数 e 存在。那么

(abg^{-e/2})^2\equiv a^2b^2g^{-e}\equiv a^{m+1} a^{-m}\equiv a \pmod p

::::

$$(g^eg^{-(e\bmod 2^k)})^{2^{n-k-1}}\equiv g^{e_k2^{n-1}}\equiv (-1)^{e_k}$$ 其中 $e_k$ 表示 $e$ 二进制拆分中 $2^k$ 的系数。有 $g^e\equiv a^m\pmod p,e\bmod 2^k=\sum_{i=0}^{k-1} e_i,e_0=0$，因此可以递推求出 $e$。 复杂度仍为 $O(\log p)$。 ## 任意模数二次剩余 对于素数幂次 $m=p^e$ 和整数 $a$，求方程 $x^2\equiv a\pmod {m}$ 的解。 ### $m$ 为奇素数幂 首先使用朴素的算法求出 $x^2\equiv a\pmod p$ 的解 $x_1$。接下来考虑递推求出模 $m$ 时的解。对于函数 $f(x)=x^2-a$，原方程即求 $f(x)\equiv 0\pmod p$ 的解。设当前已求出了 $x_j$，满足 $p^j\mid f(x_j)$，考虑求出 $x_{j+1}$。设 $f(x_j)=cp^j,x_{j+1}=x_j+tp^j$，则有 $$f(x_{j+1})= x_{j+1}^2-a= (x_j+tp^j)^2-a= (x_j^2-a)+2x_jtp^j+t^2p^{2j}= cp^j+2x_jtp^j+t^2p^{2j}\equiv cp^j+2x_jtp^j\pmod {p^{j+1}}$$ 最后一项也即 $p^j(c+2x_jt)$，要使 $p^j(c+2x_jt)\equiv 0\pmod {p^{j+1}}$，也即使 $c+2x_jt\equiv 0\pmod p$，这是个关于 $t$ 的同余方程，$t\equiv -c(2x_j)^{-1}\pmod p$ 是其的一个解。 ### $p=2

此时 (2x_j) 模 p 的逆元不存在。

在 e=1,2 时是平凡的。

对于 e=3，仅 n=1 有解 1,3,5,7。

对于 e>3，考虑递推。设目前已知 i 的答案 x_i，且 x_i 为奇数，考虑如何求出 x_{i+1}。设 x_i^2=a+t2^i，则有

(x_i+2^{k-1})^2\equiv x_i^2+2^{2k-2}+x_i2^k\equiv a+t2^i+x_i2^k\equiv a+(t+1)2^k\pmod {2^{i+1}}

那么当 x_i^2,(x_i+2^{k-1})^2 在模 2^{i+1} 次方下相差 2^k，依据 a 的二进制在这一位上的值取对应的解即可。

推广到任意模数

通过中国剩余定理合并 m 的各个质因数答案即可。使用 Pollard-Rho 进行质因数分解可以做到时间复杂度 O(n^{1/4+\varepsilon})。

参考资料

  1. OI Wiki - 二次剩余
  2. OI Wiki - 高次剩余&单位根
  3. CSDN - 浅谈二次剩余