二次剩餘

定義

令整數 \(a\)，\(p\) 滿足 \((a,p)=1\)，若存在整數 \(x\) 使得

\[ x^2\equiv a\pmod p \]

則稱 \(a\) 為模 \(p\) 的二次剩餘，否則稱 \(a\) 為模 \(p\) 的二次非剩餘。

通俗一些，可以認為是求模意義下的 開平方 運算。對於更高次方的開方可參見 k 次剩餘。

這裏只討論 \(p\) 為 奇素數 的求解方法。後文可能在模 \(p\) 顯然的情況下簡寫成二次（非）剩餘。

Euler 判別法

對奇素數 \(p\) 和滿足 \((a,p)=1\) 的整數 \(a\)，

\[ 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} \]

即對上述的 \(p\) 和 \(a\)，

1. \(a\) 是 \(p\) 的二次剩餘當且僅當 \(a^{\frac{p-1}{2}}\equiv 1 \pmod p\).
2. \(a\) 是 \(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\) 的 \(a\) 均有 \(a^{(p-1)/2}\equiv \pm 1\pmod p\)

另外由 \(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) \]

其中 \(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\) 的二次剩餘當且僅當 \(a^{(p-1)/2}\equiv 1\pmod p\). 進而 \(a\) 是模 \(p\) 的非二次剩餘當且僅當 \(a^{(p-1)/2}\equiv -1\pmod p\).

Legendre 符號

定義

對奇素數 \(p\) 和整數 \(a\)，定義 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} \]

Legendre 符號可進一步推廣為 Jacobi 符號，Jacobi 符號可進一步推廣為 Kronecker 符號。

下表為部分 Legendre 符號的值（From Wikipedia）

性質

1. 對任意整數 \(a\)，

   \[ a^{\frac{p-1}{2}}\equiv \left(\frac{a}{p}\right)\pmod p \]

   進一步，我們有推論：

   • \[ \left(\dfrac{1}{p}\right)=1 \]
   • \[ \begin{aligned} \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} \end{aligned} \]

2. \(a_1\equiv a_2\pmod p\iff \left(\dfrac{a_1}{p}\right)=\left(\dfrac{a_2}{p}\right)\)

3. （完全積性）對任意整數 \(a_1,a_2\)，

   \[ \left(\frac{a_1a_2}{p}\right)=\left(\frac{a_1}{p}\right)\left(\frac{a_2}{p}\right) \]

   我們有推論：對整數 \(a,b\)，\(p\nmid b\) 有

   \[ \left(\frac{ab^2}{p}\right)=\left(\frac{a}{p}\right) \]
4. \[ \begin{aligned} \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} \end{aligned} \]

證明

1. 由 Legendre 符號的定義 和 Euler 判別法 易得。

2. 注意到

   \[ a_1\equiv a_2\pmod p\iff \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\) 且 \(p>2\), 故：

   \[ a_1\equiv a_2\pmod p\iff \left(\frac{a_1}{p}\right)=\left(\frac{a_2}{p}\right) \]

3. 由 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\) 且 \(p>2\), 故：

   \[ \left(\frac{a_1a_2}{p}\right)=\left(\frac{a_1}{p}\right)\left(\frac{a_2}{p}\right) \]

4. 參見 二次互反律

二次互反律

二次互反律

設 \(p\)，\(q\) 是兩個不同的奇素數，則

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

證明方式很多，讀者感興趣的話可參考⁵。一種證明方式是基於如下引理（Gauss 引理）：

Gauss 引理

設 \((n,p)=1\), 對整數 \(k~\left(1\leq k\leq \dfrac{p-1}{2}\right)\)，令 \(r_k\) 為 \(nk\) 模 \(p\) 的最小非負剩餘，設 \(m\) 為所有 \(r_k\) 中大於 \(\dfrac{p}{2}\) 的個數，則

\[ \left(\frac{n}{p}\right)=(-1)^m \]

這個引理可以證明如下有用的結論：

結論

對奇素數 \(p\)，

\[ \begin{aligned} \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} \end{aligned} \]

二次互反律不僅能用於判斷數 \(n\) 是否是模 \(p\) 的二次剩餘，還能用於確定使數 \(n\) 為二次剩餘的模數的結構。

二次剩餘的數量

對於奇素數 \(p\)，模 \(p\) 意義下二次剩餘和二次非剩餘均有 \(\frac{p-1}{2}\) 個。

證明

根據 Euler 判別法，考慮 \(a^{\frac{p-1}{2}}\equiv 1\pmod p\).

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

相關算法

特殊情況時的算法

對於同餘方程 \(x^2\equiv a\pmod p\)，其中 \(p\) 為奇素數且 \(a\) 為二次剩餘在 \(p\bmod 4=3\) 時有更簡單的解法，考慮

\[ \begin{aligned} \left(a^{(p+1)/4}\right)^2&\equiv a^{(p+1)/2}&\pmod p\\ &\equiv x^{p+1}&\pmod p\\ &\equiv \left(x^2\right)\left(x^{p-1}\right)&\pmod p\\ &\equiv x^2&\pmod p&\quad (\because{\text{Fermat's little theorem}}) \end{aligned} \]

那麼 \(a^{(p+1)/4}\bmod p\) 為一個解。

Atkin 算法

仍然考慮上述同餘方程，此時 \(p\bmod 8=5\)，那麼令 \(b\equiv (2a)^{(p-5)/8}\pmod p\) 和 \(\mathrm{i}\equiv 2ab^2\pmod p\) 那麼此時 \(\mathrm{i}^2\equiv -1\pmod p\) 且 \(ab(\mathrm{i}-1)\bmod p\) 為一個解。

證明

\[ \begin{aligned} \mathrm{i}^2&\equiv\left(2ab^2\right)^2&\pmod p\\ &\equiv \left(2a\cdot \left(2a\right)^{(p-5)/4}\right)^2&\pmod p\\ &\equiv \left(\left(2a\right)^{(p-1)/4}\right)^2&\pmod p\\ &\equiv \left(2a\right)^{\frac{p-1}{2}}&\pmod p\\ &\equiv -1&\pmod p \end{aligned} \]

那麼

\[ \begin{aligned} \left(ab(\mathrm{i}-1)\right)^2&\equiv a^2\cdot \left(2a\right)^{(p-5)/4}\cdot (-2\mathrm{i})&\pmod p\\ &\equiv a\cdot (-\mathrm{i})\cdot \left(2a\right)^{(p-1)/4}&\pmod p\\ &\equiv a&\pmod p \end{aligned} \]

Cipolla 算法

Cipolla 算法用於求解同餘方程 \(x^2\equiv a\pmod p\)，其中 \(p\) 為奇素數且 \(a\) 為二次剩餘。

算法可描述為找到 \(r\) 滿足 \(r^2-a\) 為二次非剩餘，\((r-x)^{(p+1)/2}\bmod (x^2-(r^2-a))\) 為一個解。

在複數域 \(\mathbf{C}\) 中，考慮令 \(x^2+1\in\mathbf{R}\lbrack x\rbrack\) 和實係數多項式的集合 \(\mathbf{R}\lbrack x\rbrack\) 對 \(x^2+1\) 取模後的集合記作 \(\mathbf{R}\lbrack x\rbrack /(x^2+1)\)，那麼集合中的元素都可以表示為 \(a_0+a_1x\) 的形式，其中 \(a_0,a_1\in\mathbf{R}\)，又因為 \(x^2\equiv -1\pmod{\left(x^2+1\right)}\)，考慮多項式的運算可以發現 \(\mathbf{R}\lbrack x\rbrack /(x^2+1)\) 中元素的運算與 \(\mathbf{C}\) 中一致。

後文考慮對於係數屬於有限域 \(\mathbb{F}_p\) 的多項式 \(\mathbb{F}_p\lbrack x\rbrack\) 和對 \(x^2-(r^2-a)\in\mathbb{F}_p\lbrack x\rbrack\) 取模後的集合 \(\mathbb{F}_p\lbrack x\rbrack /(x^2-(r^2-a))\) 中的運算。

選擇 \(r\)：

若 \(a\equiv 0\pmod p\) 那麼 \(r^2-a\) 為二次剩餘，此時解顯然為 \(x\equiv 0\pmod p\)。所以假設 \(a\not\equiv 0\pmod p\)。使得 \(r^2-a\) 為非零二次剩餘的選擇有 \(\dfrac{p-3}{2}\) 個，而使得 \(r^2\equiv a\pmod p\) 的選擇恰有兩個，那麼有 \(\dfrac{p-1}{2}\) 種選擇可以使得 \(r^2-a\) 為二次非剩餘，使用隨機方法平均約兩次可得 \(r\).

證明

令 \(f(x)=x^2-(r^2-a)\in\mathbb{F}_p\lbrack x\rbrack\) 和 \(a_0+a_1x=(r-x)^{(p+1)/2}\bmod (x^2-(r^2-a))\) 那麼有 \(a_0^2\equiv a\pmod p\) 且 \(a_1\equiv 0\pmod p\).

\[ \begin{aligned} x^p&\equiv x(x^2)^{\frac{p-1}{2}}&\pmod{f(x)}\\ &\equiv x(r^2-a)^{\frac{p-1}{2}}&\pmod{f(x)}&\quad (\because{x^2\equiv r^2-a\pmod{f(x)}})\\ &\equiv -x&\pmod{f(x)}&\quad (\because{r^2-a}\text{ is quadratic non-residue}) \end{aligned} \]

又因為二項式定理

\[ \begin{aligned} (a+b)^p&=\sum_{i=0}^p\binom{p}{i}a^ib^{p-i}\\ &=\sum_{i=0}^p\frac{p!}{i!(p-i)!}a^ib^{p-i}\\ &\equiv a^p+b^p\pmod p \end{aligned} \]

可以發現只有當 \(i=0\) 和 \(i=p\) 時由於沒有因子 \(p\) 不會因為模 \(p\) 被消去，其他的項都因為有 \(p\) 因子被消去了。所以

\[ \begin{aligned} (r-x)^{p}&\equiv r^p-x^p&\pmod{f(x)}\\ &\equiv r+x&\pmod{f(x)} \end{aligned} \]

所以

\[ \begin{aligned} (a_0+a_1x)^2&=a_0^2+2a_0a_1x+a_1^2x^2\\ &\equiv (r-x)^{p+1}&\pmod{f(x)}\\ &\equiv (r-x)^p(r-x)&\pmod{f(x)}\\ &\equiv (r+x)(r-x)&\pmod{f(x)}\\ &\equiv r^2-x^2&\pmod{f(x)}\\ &\equiv a&\pmod{f(x)} \end{aligned} \]

若 \(a_1\not\equiv 0\pmod p\) 且

\[ \begin{aligned} (a_0+a_1x)^2&=a_0^2+2a_0a_1x+a_1^2x^2\\ &\equiv a_0^2+2a_0a_1x+a_1^2(r^2-a)\pmod{f(x)} \end{aligned} \]

所以 \(x\) 的係數必須為零即 \(a_0\equiv 0\pmod p\) 此時考慮 Legendre 符號為完全積性函數可知 \(r^2-a\equiv a/a_1^2\pmod p\) 顯然為二次剩餘，不符合定義。因此 \(a_1\equiv 0\pmod p\) 且 \(a_0^2\equiv a\pmod p\).

Bostan–Mori 算法

該算法基於 Cipolla 算法，我們將問題轉換為 常係數齊次線性遞推 再應用 Bostan–Mori 算法。考慮另一種常見的 Cipolla 算法的描述為 \(b=x^{\left(p+1\right)/2}\bmod{\left(x^2-tx+a\right)}\) 為滿足 \(b^2\equiv a\pmod{p}\) 的一個解³，其中 \(x^2-tx+a\in \mathbb{F}_p\lbrack x\rbrack\) 為不可約多項式。選取 \(t\) 同樣使用隨機。證明過程略。參考文獻⁴中的算法我們可以發現問題可轉化為求解形式冪級數的乘法逆元的某一項係數：

\[ b=\left\lbrack x^{(p+1)/2}\right\rbrack\dfrac{1}{1-tx+ax^2} \]

且

\[ \left\lbrack x^n\right\rbrack\dfrac{k_0+k_1x}{1+k_2x+k_3x^2}= \begin{cases} \left\lbrack x^{(n-1)/2}\right\rbrack\dfrac{k_1-k_0k_2+k_1k_3x}{1+(2k_3-k_2^2)x+k_3^2x^2},&\text{if }n\bmod 2=1\\ \left\lbrack x^{n/2}\right\rbrack\dfrac{k_0+(k_0k_3-k_1k_2)x}{1+(2k_3-k_2^2)x+k_3^2x^2},&\text{else if }n\neq 0 \end{cases} \]

而 \(n=0\) 時顯然有 \(\left\lbrack x^0\right\rbrack\dfrac{k_0+k_1x}{1+k_2x+k_3x^2}=k_0\)，該算法乘法次數相較於 Cipolla 算法更少，其他相關乘法次數較少的算法可見²。

Legendre 算法

對於同餘方程 \(x^2\equiv a\pmod p\)，其中 \(p\) 為奇素數且 \(a\) 為二次剩餘。Legendre 算法可描述為找到 \(r\) 滿足 \(r^2-a\) 為二次非剩餘，令 \(a_0+a_1x=(r-x)^{\frac{p-1}{2}}\bmod (x^2-a)\)，那麼 \(a_0\equiv 0\pmod p\) 且 \(a_1^{-2}\equiv a\pmod p\).

證明

考慮選擇一個 \(b\) 滿足 \(b^2\equiv a\pmod p\)，那麼 \((r-b)(r+b)=r^2-a\) 為二次非剩餘，所以

\[ (r-b)^{\frac{p-1}{2}}(r+b)^{\frac{p-1}{2}}\equiv -1\pmod p \]

存在環態射

\[ \begin{aligned} \phi:\mathbb{F}_p\lbrack x\rbrack/(x^2-a)&\to \mathbb{F}_p\times \mathbb{F}_p\\ x&\mapsto (b,-b) \end{aligned} \]

那麼

\[ \begin{aligned} (a_0+a_1b,a_0-a_1b)&=\phi(a_0+a_1x)\\ &=\phi(r-x)^{\frac{p-1}{2}}\\ &=((r-b)^{\frac{p-1}{2}},(r+b)^{\frac{p-1}{2}})\\ &=(\pm 1,\mp 1) \end{aligned} \]

所以 \(2a_0=(\pm 1)+(\mp 1)=0\) 而 \(2a_1b=(\pm 1)-(\mp 1)=\pm 2\).

Tonelli–Shanks 算法

Tonelli–Shanks 算法是基於離散對數求解同餘方程 \(x^2\equiv a\pmod p\) 的算法¹，其中 \(p\) 為奇素數且 \(a\) 為模 \(p\) 的二次剩餘。

令 \(p-1=2^n\cdot m\) 其中 \(m\) 為奇數。仍然使用隨機方法尋找 \(r\in\mathbb{F}_p\) 滿足 \(r\) 為二次非剩餘。令 \(g\equiv r^m\pmod p\) 且 \(b\equiv a^{(m-1)/2}\pmod p\)，那麼存在整數 \(e\in\lbrace 0,1,2,\dots ,2^n-1\rbrace\) 滿足 \(ab^2\equiv g^e\pmod p\)。若 \(a\) 為二次剩餘，那麼 \(e\) 為偶數且 \(\left(abg^{-e/2}\right)^2\equiv a\pmod p\).

證明

\[ \begin{aligned} g^{2^n}&\equiv r^{2^n\cdot m}&\pmod p\\ &\equiv r^{p-1}&\pmod p\\ &\equiv 1&\pmod p \end{aligned} \]

而

\[ \begin{aligned} g^{2^{n-1}}&\equiv r^{2^{n-1}\cdot m}&\pmod p\\ &\equiv r^{\frac{p-1}{2}}&\pmod p\\ &\equiv -1&\pmod p \end{aligned} \]

所以 \(g\) 的階為 \(2^n\)，又因為 \(ab^2\equiv a^m\pmod p\) 是 \(x^{2^n}\equiv 1\pmod p\) 的解，所以 \(a^m\) 是 \(g\) 的冪次，記 \(a^m\equiv g^e\pmod p\).

若 \(a\) 是二次剩餘，那麼

\[ \begin{aligned} g^{2^{n-1}\cdot e}&\equiv (-1)^e&\pmod p\\ &\equiv a^{2^{n-1}\cdot m}&\pmod p\\ &\equiv a^{\frac{p-1}{2}}&\pmod p\\ &\equiv 1&\pmod p \end{aligned} \]

所以 \(e\) 為偶數，而

\[ \begin{aligned} \left(abg^{-e/2}\right)^2&\equiv a^2b^2g^{-e}&\pmod p\\ &\equiv a^{m+1}g^{-e}&\pmod p\\ &\equiv a&\pmod p \end{aligned} \]

剩下的問題是如何計算 \(e\)，Tonelli 和 Shanks 提出一次確定 \(e\) 的一個比特。令 \(e\) 在二進制下表示為 \(e=e_0+2e_1+4e_2+\cdots\) 其中 \(e_k\in\lbrace 0,1\rbrace\).

因為 \(a\) 是二次剩餘，所以開始時 \(e_0=0\)，然後計算 \(e_1\) 然後 \(e_2\) 等等，由以下公式給出

\[ \left(g^eg^{-(e\bmod 2^k)}\right)^{2^{n-1-k}}\equiv g^{2^{n-1}\cdot e_k}\equiv \begin{cases} 1\pmod p,&\text{if }e_k=0\\ -1\pmod p,&\text{else if }e_k=1 \end{cases} \]

正確性顯然。

習題

• 洛谷 P5491【模板】二次剩餘
• 「Timus 1132」Square Root

參考資料與註釋

1. Quadratic residue - Wikipedia
2. Euler's criterion - Wikipedia

---

1. Daniel. J. Bernstein. Faster Square Roots in Annoying Finite Fields. ↩

2. S. Müller, On the computation of square roots in finite fields, Design, Codes and Cryptography, Vol.31, pp. 301-312, 2004 ↩

3. A. Menezes, P. van Oorschot and S. Vanstone. Handbook of Applied Cryptography, 1996. ↩

4. Alin Bostan, Ryuhei Mori.A Simple and Fast Algorithm for Computing the N-th Term of a Linearly Recurrent Sequence. ↩

5. Quadratic reciprocity - Wikipedia ↩

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用