3mod4 在平方和平方根 mod n 中的意義？
為什麼大多數文獻在討論以素數 P 為模的平方或平方根時，認為 P 與 3 mod 4 一致？
如果 $ p \equiv 3 \pmod{4} $ 然後 $ p + 1 $ 能被 4 整除。如果我們要取平方根 $ a $ 反對 $ p $ 然後：
$$ \left ( \pm a^{\frac{p + 1}{4}} \right)^2 \equiv a^{\frac{p + 1}{2}} \equiv a^{\frac{p - 1 + 2}{2}} \equiv a^{\frac{p - 1}{2} + 1} \equiv a^{\frac{p - 1}{2}} \cdot a \pmod{p} $$ 但由於 $ a $ 被選為二次餘數（否則它沒有平方根），因此：
$$ a^{\frac{p - 1}{2}} \equiv 1 \pmod{p} $$ 因此兩個平方根 $ a $ 模組 $ p $ 在這種情況下，可以很容易地計算為： $$ \pm a^{\frac{p + 1}{4}} $$ 與案例不同的是 $ p \equiv 1 \pmod{4} $ 這需要更多的工作來找到平方根 $ a $ 反對 $ p $ . 當然，這仍然是可能的，只是涉及更多一點（例如，參見 Tonelli-Shanks 算法）。 所以這可能是一種可能性。另一種可能性是觀察到 $ p \equiv 3 \pmod{4} $ 只是意味著 $ p - 1 $ 僅被 2 除一次，這在許多情況下可能是一個要求或一個理想的屬性。
什麼時候 $ p \equiv 3 \pmod 4 $ 然後 $ -1 $ 是一個非方形模組 $ p $ . 這意味著在二次餘數模的兩個平方根中 $ p $ , one 本身就是一個二次餘數模 $ p $ .