二次剩余

引入

二次剩余可以认为是在讨论求模意义下 开平方 运算的可行性。对于更高次方的开方可参见 k 次剩余。

定义

二次剩余

令整数，满足，若存在整数使得

x^2\equiv a\pmod p,

则称为模的二次剩余，否则称为模的二次非剩余。后文可能在模显然的情况下简写成二次（非）剩余。

Euler 判别法

当模数为奇素数时，我们有如下定理：

Euler 判别法

对奇素数和满足的整数，有

a^{\frac{p-1}{2}}\equiv\begin{cases} 1 \pmod p, & (\exists x\in\mathbf{Z}),~~a\equiv x^2\pmod p,\\ -1 \pmod p, & \text{otherwise}.\\ \end{cases}

即对上述的和，

是的二次剩余当且仅当 $a^{\frac{p-1}{2}}\equiv 1 \pmod p$ .
是的二次非剩余当且仅当 $a^{\frac{p-1}{2}}\equiv -1 \pmod p$ .

证明

首先由 Fermat 小定理有 $a^{p-1}\equiv 1\pmod p$ ，故

\left(a^{\frac{p-1}{2}}+1\right)\left(a^{\frac{p-1}{2}}-1\right)\equiv 0\pmod p,

从而对任意满足的均有 $a^{(p-1)/2}\equiv \pm 1\pmod p.$

另外由是奇素数，我们有：

x^{p-1}-a^{\frac{p-1}{2}}={\left(x^2\right)}^{\frac{p-1}{2}}-a^{\frac{p-1}{2}}=(x^2-a)P(x),

其中是某个整系数多项式，进而：

\begin{aligned} x^p-x&=x\left(x^{p-1}-a^{\frac{p-1}{2}}\right)+x\left(a^{\frac{p-1}{2}}-1\right)\\ &=(x^2-a)xP(x)+\left(a^{\frac{p-1}{2}}-1\right)x.\\ \end{aligned}

由同余方程的定理 5 可知，是模的二次剩余当且仅当 $a^{(p-1)/2}\equiv 1\pmod p$ . 进而是模的非二次剩余当且仅当 $a^{(p-1)/2}\equiv -1\pmod p$ .

基于 Euler 判别法，我们可以得到如下推论：

二次剩余的数量

对于奇素数，模意义下二次剩余和二次非剩余均有 $\dfrac{p-1}{2}$ 个。

证明

根据 Euler 判别法，考虑 $a^{\frac{p-1}{2}}\equiv 1\pmod p.$

注意到 $\dfrac{p-1}{2}\mid (p-1)$ ，由同余方程的定理 6 可知 $a^{\frac{p-1}{2}}\equiv 1\pmod p$ 有 $\dfrac{p-1}{2}$ 个解。所以模意义下二次剩余和二次非剩余均有 $\dfrac{p-1}{2}$ 个。

Legendre 符号

为了方便接下来的讨论，我们引入如下记号：

Legendre 符号

对 奇素数 和整数，定义 Legendre 符号如下：

\left(\frac{a}{p}\right)=\begin{cases} 0, & p\mid a,\\ 1, & (p\nmid a) \land ((\exists x\in\mathbf{Z}),~~a\equiv x^2\pmod p),\\ -1, & \text{otherwise}.\\ \end{cases}

即对于的，

是模的二次剩余当且仅当 $\left(\dfrac{a}{p}\right)=1.$
是模的二次非剩余当且仅当 $\left(\dfrac{a}{p}\right)=-1.$

下表为部分 Legendre 符号的值（From Wikipedia）

性质

对任意整数，
$a^{\frac{p-1}{2}}\equiv \left(\frac{a}{p}\right)\pmod p.$
进一步，我们有推论：
- $\left(\dfrac{1}{p}\right)=1.$
- $\left(\dfrac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}=\begin{cases} 1, & p\equiv 1\pmod 4,\\ -1, & p\equiv 3\pmod 4. \end{cases}$
$a_1\equiv a_2\pmod p\implies \left(\dfrac{a_1}{p}\right)=\left(\dfrac{a_2}{p}\right).$
（完全积性）对任意整数，
$\left(\frac{a_1a_2}{p}\right)=\left(\frac{a_1}{p}\right)\left(\frac{a_2}{p}\right).$
我们有推论：对整数， $p\nmid b$ 有
$\left(\frac{ab^2}{p}\right)=\left(\frac{a}{p}\right).$
$\left(\frac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}=\begin{cases} 1, & p\equiv \pm 1\pmod 8, \\ -1, & p\equiv \pm 3\pmod 8. \\ \end{cases}$

证明

由 Legendre 符号的定义和 Euler 判别法易得。
注意到
$a_1\equiv a_2\pmod p\implies \left(\frac{a_1}{p}\right)\equiv\left(\frac{a_2}{p}\right)\pmod p,$
而 $\left|\left(\dfrac{a_1}{p}\right)-\left(\dfrac{a_2}{p}\right)\right|\leq 2$ 且，故：
$a_1\equiv a_2\pmod p\implies \left(\frac{a_1}{p}\right)=\left(\frac{a_2}{p}\right).$
由 1 得
$\left(\frac{a_1a_2}{p}\right)\equiv a_1^{\frac{p-1}{2}}a_2^{\frac{p-1}{2}}\equiv\left(\frac{a_1}{p}\right)\left(\frac{a_2}{p}\right)\pmod p.$
而 $\left|\left(\dfrac{a_1a_2}{p}\right)-\left(\dfrac{a_1}{p}\right)\left(\dfrac{a_2}{p}\right)\right|\leq 2$ 且，故
$\left(\frac{a_1a_2}{p}\right)=\left(\frac{a_1}{p}\right)\left(\frac{a_2}{p}\right).$
参见二次互反律

基于如上性质，若对任意奇素数和， $\left(\dfrac{p}{q}\right)$ 的值均可计算，则我们就可以对任意合法情况计算 Legendre 符号的值。接下来我们有一个优美的定理，这个定理巧妙地在 $\left(\dfrac{p}{q}\right)$ 和 $\left(\dfrac{q}{p}\right)$ 之间建立起了联系，使得我们能用类似辗转相除法的思路完成计算。

二次互反律

设，是两个不同的奇素数，则

\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}.

证明方式很多⁵。一种证明方式是基于如下引理：

Gauss 引理

设是奇素数，，对整数 $k~\left(1\leq k\leq (p-1)/2\right)$ ，令为模的最小非负剩余，设 $A=\{r_k:r_k<p/2\}$ ， $B=\{r_k:r_k>p/2\}$ ，则

\left(\frac{n}{p}\right)=(-1)^{|B|}.

证明

设 $\lambda=|A|$ ， $\mu=|B|$ ，显然 $\lambda+\mu=(p-1)/2$ ，则

n^{\frac{p-1}{2}}\left(\frac{p-1}{2}\right)!=\prod_{k=1}^{\frac{p-1}{2}} nk\equiv\prod_{a\in A}a\prod_{b\in B}b\pmod{p}.

我们知道对中任意元素，有 $\dfrac{p}{2}<b<p$ ，所以 $0<p-b<\dfrac{p}{2}$ ，进一步，对中任意元素，我们有 $p-b\notin A$ ，否则若中分别存在元素使得，则存在整数使得，且 $p\mid n(k_1+k_2)$ ，由于，则 $p\mid (k_1+k_2)$ ，注意到，所以产生矛盾。因此

n^{\frac{p-1}{2}}\left(\frac{p-1}{2}\right)!\equiv(-1)^{\mu}\prod_{a\in A}a\prod_{b\in B}(p-b)=(-1)^{\mu}\left(\frac{p-1}{2}\right)!\pmod{p},

即

n^{\frac{p-1}{2}}\equiv(-1)^{\mu}\pmod{p}.

从而由 Legendre 符号的性质 1 即得证。

容易得到如下推论：

推论

对奇素数，有

\left(\frac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}=\begin{cases} 1, & p\equiv \pm 1\pmod 8, \\ -1, & p\equiv \pm 3\pmod 8. \\ \end{cases}

对奇素数，奇数满足，有

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

证明

对 Gauss 引理中的 $n,k,r_k,A,B,\lambda,\mu$ ，有 $nk=p\left\lfloor\dfrac{nk}{p}\right\rfloor+r_k$ ，进而

\begin{aligned} n\cdot\frac{p^2-1}{8}=\sum_{k=1}^{\frac{p-1}{2}}nk&=p\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor\dfrac{nk}{p}\right\rfloor+\sum_{a\in A}a+\sum_{b\in B}b\\ &=p\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor\dfrac{nk}{p}\right\rfloor+\sum_{a\in A}a+\sum_{b\in B}(p-b)+2\sum_{b\in B}b-p\mu\\ &=p\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor\dfrac{nk}{p}\right\rfloor+\sum_{k=1}^{\frac{p-1}{2}}k+2\sum_{b\in B}b-p\mu\\ &=p\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor\dfrac{nk}{p}\right\rfloor+\frac{p^2-1}{8}+2\sum_{b\in B}b-p\mu, \end{aligned}

因此

(n-1)\frac{p^2-1}{8}=p\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor\dfrac{nk}{p}\right\rfloor+2\sum_{b\in B}b-p\mu.

若，则 $0<\dfrac{nk}{p}\leq\dfrac{p-1}{p}<1$ ，从而有

\frac{p^2-1}{8}\equiv\mu\pmod{2}.

若 $2\nmid n$ ，则有

\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor\dfrac{nk}{p}\right\rfloor\equiv\mu\pmod{2}.

根据如上推论，证明二次互反律只需验证

\frac{p-1}{2}\frac{q-1}{2}=\sum_{k=1}^{\frac{p-1}{2}}\left\lfloor\dfrac{qk}{p}\right\rfloor+\sum_{k=1}^{\frac{q-1}{2}}\left\lfloor\dfrac{pk}{q}\right\rfloor.

考虑由点， $1\leq x\leq \dfrac{q-1}{2},1\leq y\leq \dfrac{p-1}{2}$ 构成的集合，将其根据与的大小关系分成两部分（显然 $px\neq qy$ ），分别验证三个集合的大小即可。

二次互反律不仅能用于判断数是否是模的二次剩余，还能用于确定使数为二次剩余的模数的结构。

Example

使得为二次剩余的奇素数满足 $p\equiv \pm 1\pmod 5.$
使得为二次剩余的奇素数满足 $p\equiv 1\pmod 3.$
使得，同时为二次剩余的奇素数满足 $p\equiv 11\pmod{24}.$

另外，我们还可以证明诸如「形如的素数有无限多个」之类的结论，这一类结论实际上是 Dirichlet 定理的简单推论。

Jacobi 符号

根据二次互反律，我们可以很自然地想到一种推广 Legendre 符号的方法：

Jacobi 符号

对 正奇数 $m=p_1^{\alpha_1}\dots p_k^{\alpha_k}$ 和整数，其中 $p_1,\dots,p_k$ 是素数， $\alpha_1,\dots,\alpha_k$ 是正整数，定义 Jacobi 符号如下：

\left(\frac{a}{m}\right):=\prod_{i=1}^k\left(\frac{a}{p_i}\right)^{\alpha_i}.

其中等式右端的 $\left(\frac{a}{p_i}\right)$ 为 Legendre 符号。另外对整数有 $\left(\dfrac{a}{1}\right)=1.$

Warning

我们一般不区分 Legendre 符号和 Jacobi 符号，因为由完全积性可知 Jacobi 符号具有和 Legendre 符号一样的性质，所以这两种符号的计算方法是一致的。但是有一点需要注意：当 不是奇素数 时， $\left(\dfrac{a}{m}\right)$ 的值与是否是模的二次剩余无关，但是若 $\left(\dfrac{a}{m}\right)=-1$ ，则说明至少存在一个（实际上是奇数个）素因子使得是模的二次非剩余，从而此时是模的二次非剩余。

我们还可以把模数进一步推广为整数（只需补充 $\left(\dfrac{a}{-1}\right)$ 、 $\left(\dfrac{a}{0}\right)$ 和 $\left(\dfrac{a}{2}\right)$ 的定义），这样就得到了 Kronecker 符号。

习题

参考资料与注释

Daniel. J. Bernstein. Faster Square Roots in Annoying Finite Fields. ↩
S. Müller, On the computation of square roots in finite fields, Design, Codes and Cryptography, Vol.31, pp. 301-312, 2004 ↩
A. Menezes, P. van Oorschot and S. Vanstone. Handbook of Applied Cryptography, 1996. ↩
Alin Bostan, Ryuhei Mori.A Simple and Fast Algorithm for Computing the N-th Term of a Linearly Recurrent Sequence. ↩
Proofs of quadratic reciprocity - Wikipedia ↩

本页面最近更新：2025/6/29 23:20:23，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：hly1204, ShaoChenHeng, Chrogeek, Enter-tainer, Great-designer, iamtwz, monkeysui, nanmenyangde, sshwy, StudyingFather, TachikakaMin, Tiphereth-A, Xeonacid, xyf007, c-forrest, rgw2010
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

二次剩余

引入

定义

Euler 判别法

Legendre 符号

性质

二次互反律

Jacobi 符号

相关算法

特殊情况时的算法

Atkin 算法

Cipolla 算法

Bostan–Mori 算法

Legendre 算法

Tonelli–Shanks 算法

习题

参考资料与注释