Diffie-Hellman 組的大小應該是素數嗎？

我發現了一些關於尋找安全素數的矛盾答案。

當 p 是“安全素數”時，這意味著 $ (p−1)/2 $ 也是素數。然後我們定義 $ q=(p−1)2 $ . 在那種情況下，任何非零的階 $ g\mod p $ （除了 1 和 p-1）是 $ q $ 或者 $ 2q $

如果它可以產生一組大小 $ 2q $ 那麼根據定義，組長度不是素數。

好的，所以按照這個理論，83 應該被認為是一個安全的素數。

$ (83-1)/2=41 $ 和 $ 41 $ 是一個素數。

產生的子群的長度 $ 2 \mod 83 $ 是 $ 82 $ . （你能這樣說嗎？即使它指的是一組/組同餘 $ 2^{1..p-1} \mod p $ ?

我可以用一個小程序來證明

const groupSize = (p, g) => {
   const group = new Set()
   for(let i = BigInt(0); i < p-BigInt(1); i++){
       group.add((g**i)%p)
   }
   console.log(group.size)
}
groupSize(BigInt(83), BigInt(2))

output: 82

這與我之前關於選擇安全素數的一個問題的答案相矛盾。

如果 h 是 g 生成的組大小的一個因子，則給定 $ g^x\mod p $ ，我們可以計算 $ h\mod n $ 在 $ O(\sqrt h) $ 時間。如果 g 生成整個組，那麼它的大小將是 $ p−1 $ ，它總是有一個因子 2（假設 $ p>2 $ )，所以我們會放棄 $ x\mod 2 $ 免費。

Diffie-Hellman 什麼是子群

這讓我相信該組不能是偶數，因為它是 2 的因數？

產生的子群的長度 $ 2\pmod{83} $ 是 $ 82 $ . 你能這樣說嗎？

那將是不尋常的。至少，“長度”應該是大小（基數會非常正式）。我會在以下曲調上使用一些東西：

• 乘法子群的階由 $ 2 $ 模組 $ 83 $ 是 $ 82 $ .
• $ 2 $ 有訂單 $ 82 $ ， 模組 $ 83 $ .

---

上一個答案建議不要選擇 $ g=2 $ ，因為它生成整個乘法子群 $ \Bbb Z_{83}^* $ , 那就是集合 $ [1,83) $ 在乘法模下 $ 83 $ , 有序的 $ 82 $ . 因此（如解釋的那樣），與 $ g=2 $ , 給 $ y=g^x\bmod 83 $ 如果洩漏 $ x $ 是偶數還是奇數：只計算 $ y^{41}\bmod83 $ , 那就是 $ 1 $ 當且僅當 $ x $ 甚至。

相反，我們可以使用 $ g=3 $ , 有順序 $ 41 $ . 或者，正如另一個答案所指出的， $ g=4 $ 如果它總是有素數 $ p $ 和 $ q=(p-1)/2 $ 是素數。

引用自：https://crypto.stackexchange.com/questions/80949