二次殘差如何工作以及它們與 Diffie Hellman 有何關係？
有人可以用英語向我解釋二次殘差嗎？我一直在閱讀所有數學符號的論壇，很難理解。它們是如何融入 Diffie-Hellman 的？使用它們與立方殘基有區別嗎？
有人可以用英語向我解釋二次殘差嗎？
一個值 $ x $ 是二次餘數模 $ p $ 如果存在值 $ t $ 為此 $ t^2 \bmod p = x $ .
也就是說，我們取 $ t $ ，平方它（這是二次部分），然後取模 $ p $ （也就是餘數部分，也就是去掉所有倍數後剩下的部分 $ p $ )，這給了我們價值 $ x $ . 如果這樣的過程能給我們 $ x $ , 我們說 $ x $ 是二次殘差。
例如， $ 2 $ 是二次殘差模 $ 7 $ （因為如果我們從 $ 3 $ ，平方，然後取結果模 $ 7 $ ，我們最終得到 $ 2 $ ); 然而 $ 3 $ 不是（可以通過計算驗證 $ 1^2 \bmod 7, 2^2 \bmod 7, 3^2 \bmod 7, …, 6^2 \bmod 7 $ )
另外，在這個答案中，我一直很小心地說“二次殘差模 $ p $ “；顯然，相同的值 $ x $ 可以是一個以某個素數為模的二次殘差 $ p $ 而不是模另一個素數 $ q $ . 通常，您會看到語句“$x”是二次殘差”；它們的意思是模數，但這是隱含的（因為它們在特定的組中工作，這從上下文中應該是顯而易見的）。
重要事實：
- 如果 $ p $ 是大於 2 的素數，那麼其中的一些值 $ 1 $ 和 $ p-1 $ 將是二次殘差模 $ p $ ，有的不會。事實上，這些值中恰好有一半會，一半不會。
- 如果 $ p $ 是素數，那麼 $ a \times b \bmod p $ 將是二次殘差模 $ p $ 如果兩者中的任何一個 $ a $ 和 $ b $ 是二次殘差，或者兩者都不是。
- 如果 $ p $ 是一個素數，事實證明很容易檢查哪裡 $ x $ 是二次殘差模組 $ p $ .
它們是如何融入 Diffie-Hellman 的？
大多數情況下，它不是。如果 Diffie-Hellman 發生器 $ g $ 不是二次殘差模 $ p $ ，然後給定 $ g^a \bmod p $ ，我們可以判斷是否 $ a $ 是偶數還是奇數；給定 $ g^a \bmod p, g^b \bmod p $ ，我們可以判斷是否 $ g^{ab} \bmod p $ 是二次殘差模 $ p $ 或不。另一方面，我們通常使用生成大型素子群的生成器來執行 Diffie-Hellman；這樣的生成器將始終是二次殘差模 $ p $ ，因此檢查值 $ g^a \bmod p, g^b \bmod p $ 什麼也沒告訴我們。
使用它們與立方殘基有區別嗎？
如果 $ p $ 是一個素數 $ p \equiv 2 \bmod 3 $ , 然後三次餘數模 $ p $ 無趣；所有值 $ x $ 是三次殘基模 $ p $ .
如果 $ p $ 是一個素數 $ p \equiv 1 \bmod 3 $ ，然後三分之一的值之間 $ 1 $ 和 $ p-1 $ 將是三次餘數模 $ p $ ，三分之二不會。另一方面，同樣的 Diffie-Hellman 邏輯也適用；如果 $ g $ 生成一個大素子群，然後 $ g $ 將是一個三次餘數模 $ p $ , 也會如此 $ g^a \bmod p, g^b \bmod p, g^{ab} \bmod p $ 還有……