Discrete-Logarithm
為什麼使用素數qqq這樣的qqq|(p-1)(p−1)(p-1)在基於離散對數的方案中？
在基於離散對數的有限域方案中，我們有一個素數 $ q $ 劃分 $ p-1 $ 和 $ q $ 是用順序指定一個子組 $ q $ . 但我們為什麼要這樣做？我們為什麼不與訂單組一起工作 $ p $ 並且需要一個有順序的子組 $ q $ .
這是出於安全原因（離散對數計算算法）還是出於計算優化？
您正在使用的組沒有訂單 $ p $ . 在離散對數方案中，您不是在有限域中工作， $ F_p $ , 而是一個乘法群 $ 1,…,p-1 $ , 有順序 $ p-1 $ . 自從 $ p $ 是一個素數， $ p-1 $ 是複合的（只要 $ p > 3 $ ）。群論告訴我們存在一個大小為的子群 $ d $ 對於每個 $ d $ 劃分 $ p-1 $ . $ ^{1} $ 通過選擇順序的子組 $ q $ ， 在哪裡 $ q $ 是素數，我們確保沒有（非平凡的）子群。這避免了小型子組限制攻擊。
正如其他答案和評論中提到的，有很簡單的方法可以找到合適的 $ p $ 和 $ q $ . 一種是使用素數， $ p $ 和 $ q $ , 這樣 $ p = 2q + 1 $ . 這樣一個 $ p $ 稱為安全素數。另一種是通過設置 $ p = qr + 1 $ ， 在哪裡 $ r $ 有（可能）未知的因式分解。由此生成的組 $ q $ 稱為Schnorr 群。
$ ^1 $ 這種說法一般來說是不正確的。對於有限域的群是這樣。有關一般情況下的血腥細節，請參閱此 Wikipedia 部分給定順序的子組的存在。這個math.stackexchange 答案是有限域群的一個很好的證明。