柊四千的倉庫

設 $p$ 為質數且 $a \in \mathbb{Z}$。考慮問題： 是否存在 $r \in \mathbb{Z}$ 使得 $r^2 \equiv a\ (\operatorname{mod}p)$？ 如果這樣的 $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$，則 $a$ 是 $p$ 的二次剩餘若且唯若 $a^\frac{p-1}{2} = 1$。 $a$ 是 $p$ 的二次非剩餘若且唯若 $a^\frac{p-1}{2} = -1$。 至此第一個問題 $O(\log p)$ 時間複雜度圓滿解決。 為了接下來的討論方便，這邊介紹 勒讓德符號 (Le