模 p 下的平方根: Cipolla 演算法
設 p 為質數且 a∈Z。考慮問題: 是否存在 r∈Z 使得 r2≡a (modp)? 如果這樣的 r 存在,有沒有好的方法找? 如果第一個問題的答案是肯定的且 p∤,我們說 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...