模 p 下的平方根: Cipolla 演算法

設 $p$ 為質數且 $a \in \mathbb{Z}$。考慮問題：

1. 是否存在 $r \in \mathbb{Z}$ 使得 $r^2 \equiv a\ (\operatorname{mod}p)$？
2. 如果這樣的 $r$ 存在，有沒有好的方法找？

如果第一個問題的答案是肯定的且 $p\nmid a$，我們說 $a$ 是 $p$ 的二次剩餘 (quadratic residue)；如果第一個問題的答案是否定的，則說 $a$ 是 $p$ 的二次非剩餘 (quadratic nonresidue)。

當 $p = 2$ 或 $a \equiv 0$ 時上面兩個問題都是 trivial；以下假定 $p \geq 3$ 且 $a \not\equiv 0$。透過觀察 $x^2-r^2 = (x-r)(x+r)$ 且 $r \neq -r$，我們發現 $a$ 可以寫成 $r^2$ 若且唯若方程式 $x^2-a = 0$ 在 $\mathbb{Z}_p$ 下恰有兩相異根。這代表恰有 $\frac{p-1}{2}$ 個 $\mathbb{Z}_p^\times$ ($\mathbb{Z}_p$ 的乘法群) 裡的元素能被開根號，而另外 $\frac{p-1}{2}$ 個 $\mathbb{Z}_p^\times$ 裡的元素不能被開根號。又，費馬小定理指出，對於所有的 $x \in \mathbb{Z}_p^\times$，均有

$$x^{p-1} -1 = (x^\frac{p-1}{2}-1)(x^\frac{p-1}{2}+1) = 0$$

若 $a = r^2$，則 $a^\frac{p-1}{2}-1 = r^{p-1}-1 = 0$。因為方程式 $x^\frac{p-1}{2}-1 = 0$ 最多只能有 $\frac{p-1}{2}$ 個根，我們得到了以下的定理：

[定理] 設 $p \geq 3$ 為一奇質數且 $a \in \mathbb{Z}_p^\times$，則

1. $a$ 是 $p$ 的二次剩餘若且唯若 $a^\frac{p-1}{2} = 1$。
2. $a$ 是 $p$ 的二次非剩餘若且唯若 $a^\frac{p-1}{2} = -1$。

至此第一個問題 $O(\log p)$ 時間複雜度圓滿解決。

為了接下來的討論方便，這邊介紹勒讓德符號 (Legendre symbol)：設 $p \geq 3$ 為一奇質數且 $a \in \mathbb{Z}$。定義

$$\left(\frac{a}{p}\right) := \begin{cases} 0,&\text{if }a\text{ can be divided by }p,\\ +1,&\text{if }a\text{ is a quadratic residue of }p,\\ -1,&\text{if }a\text{ is a quadratic nonresidue of }p. \end{cases}$$

由上面的定理知道 $\left(\frac{a}{p}\right) \equiv a^\frac{p-1}{2}\ (\operatorname{mod}p)$。若 $\left(\frac{a}{p}\right) = 1$，Cipolla 演算法給出了一個找出 $\sqrt{a}\ (\operatorname{mod}p)$ 的方法如下：

1. 尋找 $k \in \mathbb{Z}_p$ 使得 $\left(\frac{k^2-a}{p}\right) \neq 1$。
2. 如果 $\left(\frac{k^2-a}{p}\right) = 0$，直接回傳 $k$；否則考慮體擴張 (field extension) $\mathbb{Z}_p[\sqrt{k^2-a}]$，並回傳 $(k+\sqrt{k^2-a})^\frac{p+1}{2}$。

假定我們已經找到了 $k$ 使得 $\left(\frac{k^2-a}{p}\right) = -1$。我們直接計算

$$\begin{split} \left((k+\sqrt{k^2-a})^\frac{p+1}{2}\right)^2 &= (k+\sqrt{k^2-a})^{p+1}\\ &= (k+\sqrt{k^2-a})(k+\sqrt{k^2-a})^p\\ &= (k+\sqrt{k^2-a})(k^p+\sqrt{k^2-a}^p)\ (\text{since }\binom{p}{q}=0\text{ for }q = 1, 2, \ldots, p-1)\\ &= (k+\sqrt{k^2-a})(k+(k^2-a)^\frac{p-1}{2}\sqrt{k^2-a})\\ &= (k+\sqrt{k^2-a})(k-\sqrt{k^2-a})\ (\text{since }(k^2-a)^\frac{p-1}{2} = \left(\frac{k^2-a}{p}\right) = -1)\\ &= a. \end{split}$$

因為方程式 $x^2-a = 0$ 的兩根都在 $\mathbb{Z}_p$ 中，儘管計算過程牽涉到 field extension，$(k+\sqrt{k^2-a})^\frac{p+1}{2}$ 一定在 $\mathbb{Z}_p$ 中。

那要怎麼尋找滿足 $\left(\frac{k^2-a}{p}\right) \neq 1$ 的 $k$ 呢？一般來說只能用猜的。以下說明滿足 $\left(\frac{k^2-a}{p}\right) = -1$ 的 $k$ 恰有 $\frac{p-1}{2}$ 個。在 $\mathbb{Z}_p$ 下考慮

$$\begin{equation} \begin{split} \sum_{k \in \mathbb{Z}_p}\left(\frac{k^2-a}{p}\right) &= \sum_{k \in \mathbb{Z}_p}(k^2-a)^\frac{p-1}{2}\\ &= \sum_{k \in \mathbb{Z}_p}k^{p-1} + \sum_{k\in\mathbb{Z}_p}(\text{lower terms w.r.t. }k)\\ &= (p-1) + 0 = -1. \end{split} \end{equation}$$

滿足 $\left(\frac{k^2-a}{p}\right) = \pm1$ 的 $k$ 恰有 $p-2$ 個，又根據 $(1)$ 得知滿足 $\left(\frac{k^2-a}{p}\right) = -1$ 的 $k$ 比滿足 $\left(\frac{k^2-a}{p}\right) = 1$ 的多 $1$ 個，推出恰有 $\frac{p-1}{2}$ 個 $k$ 滿足 $\left(\frac{k^2-a}{p}\right) = -1$。

由於亂猜 $k$ 有 $\frac{p+3}{2p} > 1/2$ 的機率猜中，猜測次數的期望值是 $O(1)$ 的，亦即找一個 $\sqrt{a}$ 的期望時間複雜度也是 $O(\log p)$。

追伸：當 $p \equiv 3\ (\operatorname{mod} 4)$ 時，不難驗證 $a^\frac{p+1}{4}$ 直接就是 $a$ 的一個平方根，在手算時相對方便許多。另，讀者可以在這裡測試您的程式實作。