Diffie-Hellman 中最大的質因數是什麼？
我正在閱讀 TAHER ELGAMAL 的A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms的論文，以更好地理解 ElGamal 公鑰方案，他說對於任何基於離散對數問題的密碼系統，質數 $ p $ 應該這樣選擇 $ p-1 $ 至少有一個大質因數。
我的問題如下：如何確定 $ p-1 $ 實際上是大嗎？
如何確定最大的質因數 $ p-1 $ 實際上是大嗎？
大多數情況下，它不是由 $ p $ 那 $ p-1 $ 有很大的素因數。相反，一個大的主要因素 $ q $ 被選擇，然後它被選擇一個素數 $ p $ 形式的 $ p=2,q,r+1 $ 對於一些 $ r\ge1 $ ，這確保了 $ p-1 $ 有很大的素因數 $ q $ .
- 有時，我們想要 $ r=1 $ ， 在這種情況下 $ p $ 是一個安全的素數並且 $ q $ 匹配的蘇菲熱爾曼素數。有關如何搜尋這些內容，請參見最後一段。
- 對於其他一些應用程序，我們希望 $ r $ 大到 $ p $ 遠大於 $ q $ （例如 $ p $ 3072 位 $ q $ 256 位）。這是施諾爾集團的案例。為了尋找 $ r $ 製造 $ p $ 素數，當它不成立時，我們通常會添加一個小值 $ r $ ; 也許 $ 1 $ ，或一個小的隨機值，以使 $ p $ 更隨機播種。
Schnorr 組的標準生成過程在FIPS 186-4 附錄 A中。更罕見的是，它在生成後檢查 $ p $ 那 $ p-1 $ 有很大的素因數。
- 對於一個安全的素數，這歸結為檢查 $ (p-1)/2 $ 是素數。
- 否則，我們可以計算 $ (p-1)/2 $ ，將它們相乘（與多重性）得到 $ r $ ，然後檢查是否 $ q=(p-1)/(2,r) $ 是素數。如果確實如此，並且足夠大，則驗證 $ p $ （但我們可能無法提取足夠的因素）。這僅對探索或取證有用：prime $ q $ 通常需要使用 $ p $ ，因此這樣的 $ q $ 通常被移動 $ p $ .
快速搜尋安全素數（大於 $ 5 $ 和 $ 7 $ )
通常，我們還需要某個生成器 $ g $ （經常 $ 2 $ 或者 $ 3 $ ) 已知是有序的 $ q=(p-1)/2 $ （最大素數階）或階數 $ 2,q $ （最大順序，這是不可能的 $ g=3 $ ）。搜尋可以如下：
對於每個候選人 $ q $ （必然：與 $ q\bmod6=5 $ ; 並進一步與 $ q\bmod12=11 $ 為了 $ g=2 $ 有秩序的 $ q $ ，或與 $ q\bmod12=5 $ 為了 $ g=2 $ 有秩序的 $ 2,q $ )
計算 $ p=2,q+1 $
計算 $ t=g^q\bmod p $
如果 $ t=1 $ （為了 $ g $ 有秩序的 $ q $ ） 或者如果 $ t=p-1 $ （為了 $ g $ 有秩序的 $ 2,q $ )
如果 $ q $ 是素數
如果 $ p $ 是素數
- 輸出 $ p $ 並停下來。
的測試 $ t $ 是費馬贗素檢驗。它可以快速過濾掉大多數候選人 $ p $ 不是素數的，以及所有素數 $ p $ 和 $ g $ 不是所需的順序。如果由於某種原因我們不關心生成器，那麼計算仍然是值得的 $ t $ 和 $ g=2 $ 並接受兩者 $ t=1 $ 或者 $ t=p-1 $ .
通過僅篩選候選人進行選擇，可以更快地進行搜尋 $ q $ 兩者都沒有 $ q $ 也不 $ 2,q+1 $ 能被一個小素數整除。