離散對數弱群
我正在尋找離散對數中的弱組，即 $ x $ 可以從中提取 $ Y $ 在多項式時間內 $ Y \equiv g^x \pmod{p} $ .
我認為一種方法是產生一個素數 $ p $ 那 $ p-1 $ 是一個平滑整數，然後使用Pohlig-Hellman算法使**離散對數問題變得容易，但我找不到任何生成此類素數的算法。簡單地說，我們可以生成隨機數，然後檢查它是否是素數，如果是素數，檢查是否 $ p-1 $ 可以分解為一組小的素數。它可以通過另一種方式完成，考慮一組小的素數並為集合中的每個素數生成隨機指數，將所有素數乘以它們的指數。通過這樣做，我們有一個數字 $ r $ 可以分解為小的素數，然後我們可以檢查是否 $ r+1 $ 是素數。
顯然，這些方法只是反複試驗，可能需要很長時間才能找到這樣的素數，特別是在生成256位素數時。有沒有更好的算法？
還有什麼其他方法可以生成 256位長的弱模數？
有沒有更好的算法？
實際上，您的第二種算法（選擇一小組素數 $ { 2, q_1, q_2, …, q_n } $ 並檢查是否 $ \ 2q_1 q_2 … q_n + 1 $ 是素數）非常有效。您說這是反複試驗（確實如此），但是它與我們用來搜尋素數的傳統算法一樣有效；如果你正在尋找一個 $ q $ 位素數，那麼您預計需要嘗試平均 $ \log(2^q) / 2 = q \log(2)/2 $ 在找到構成素數的素數之前的一組素數（實際上，少一點，因為你知道先驗你生成的數字不會有 $ q_1, q_2, …, q_n $ 作為一個因素）。
創建弱 DLog 問題的另一種方法是 $ g $ 虛弱的; 也就是說，生成一個 $ p $ 形式的 $ 2qr + 1 $ ， 在哪裡 $ q $ 是一個小素數並且 $ r $ 是一個大的（並且可以使用相同的算法來搜尋它）。然後，您選擇 $ g $ 有秩序 $ q $ （也就是說，你選擇一個隨機值 $ h $ 並設置 $ g = h^{2r} \bmod p $ , 並檢查它不是 1); 如果 $ q $ 是一個 $ m $ -bit prime，則離散對數問題將採取 $ O(2^{m/2}) $ 時間; 例如， $ m=32 $ 使這可以在幾毫秒內解決。
當然，任何一種方法的使用都可以很容易地被檢查的人發現 $ p $ 和 $ g $ …