有人可以解釋與 Z * p 中的組有關的四個平方根的定義嗎？
因此，我遇到了以下問題：
什麼時候 $ p $ 和 $ q $ 是不同的奇數素數和 $ N = pq $ , 中的點 $ Z^∗_N $ 有零或四個平方根。四分之一的點有四個平方根；其餘的沒有平方根。的四個平方根 $ x ∈ Z^∗_N $ 看起來像 $ ±a, ±b $ . （當然，-a 表示 N-a，因為我們正在對 N 取模。）假設我給你一個有效的確定性算法 S，它在具有平方根的輸入 x 上找到某個平方根。（如果 x 沒有平方根，則返回 ⊥。）使用 S 製作一個包含 N 的有效機率算法 F。
我不是要解決問題，而是要了解“四個平方根”可能意味著什麼？單個元素怎麼可能 $ x∈ Z^∗_N $ 有“四平方根”嗎？
" $ x $ 有四個平方根”表示有四個不同的元素 $ r $ 在組中，這樣 $ r^2 = x $ .
例如，在 $ \mathbf{Z}_{15}^\times $ 元素 $ 1 $ 有四個平方根，分別是 $ 1 $ , $ 4 $ , $ 11 $ ， 和 $ 14 $ （注意 $ 11 \equiv -4 $ 和 $ 14 \equiv -1 \pmod{15} $ ).
我想在這裡給出一個證明和解決方案。認為 $ x^2 \equiv m\pmod{N} $ 有根 $ x=x_{0} $ ，那麼我們可以得到另外三個根，如下所示：
讓 $ x_{0} \equiv x_{1}\pmod{p} $ 和 $ x_{0} \equiv x_{2}\pmod{q} $ 分別。因此，
- $ x^2 \equiv m\pmod{p} $ 正好有兩個平方根，即 $ x \equiv x_{1}\pmod{p} $ 和 $ x \equiv p-x_{1}\pmod{p} $ .
- 相似地， $ x^2 \equiv m\pmod{q} $ 正好有兩個平方根，即 $ x \equiv x_{2}\pmod{q} $ 和 $ x \equiv q-x_{2}\pmod{q} $ .
從中國剩餘定理，同餘方程 $ x^2 \equiv m\pmod{N} $ 正好有四個根。它們是組合中的根
$$ \begin{equation} \left{ \begin{array}{cl} x \equiv x_{1}\pmod{p} & \ & \ x\equiv x_{2}\pmod{q} & \end {array}\right. \end{equation} $$ $$ \begin{equation} \left{ \begin{array}{cl} x \equiv x_{1}\pmod{p} & \ & \ x\equiv q-x_{2}\pmod{q} & \end {array}\right. \end{equation} $$ $$ \begin{equation} \left{ \begin{array}{cl} x \equiv p-x_{1}\pmod{p} & \ & \ x\equiv x_{2}\pmod{q} & \end {array}\right. \end{equation} $$ $$ \begin{equation} \left{ \begin{array}{cl} x \equiv p-x_{1}\pmod{p} & \ & \ x\equiv q-x_{2}\pmod{q} & \end {array}\right. \end{equation} $$ 我們將前兩個方程的根表示為 $ a $ , $ b $ ， 然後 （ $ N-a $ ） 和 （ $ N-b $ ) 分別是最後兩個方程的根。
由上式可知，四個平方根為 $ a $ , $ b $ , ( $ N-a $ ） 和 （ $ N-b $ ）。
值得一提的是，當 $ p, q $ 是Blum 素數，即 $ p\equiv q \equiv3 \pmod{4} $ , $ x \equiv\pm m^{\frac{p+1}{4}} \pmod{p} $ 正是方程的根 $ x^2 \equiv m\pmod{p} $ .