Rsa
計算離散對數模n=p×qn=p×qn=p times q知道因式分解
我在一個給定的文件中讀到 $ n = p\times q $ ( $ p $ , $ q $ 素數），如果你知道 $ p $ 和 $ q $ 那麼您可以輕鬆解決離散對數問題，即對於固定 $ a,b $ ， 你可以找到 $ x $ 這樣 $$ a^x = b \bmod n $$ 但我不明白這是怎麼做到的……我試圖檢查中國提醒定理是否可以幫助我，這減少了找到離散對數模 $ p $ 和模 $ q $ ，但我仍然不明白我們如何在沒有暴力破解的情況下獲得這個新的離散對數（即使你得到了對天真的暴力破解的平方根改進，它仍然是指數級的）。
謝謝！
一般情況下這是不正確的。巴赫表明，給定因式分解 $ n $ ，計算離散對數模 $ n $ 需要對因子進行模計算（有關更多詳細資訊，請參見前一個問題。）。因此，如果這兩個因素都很大，那麼 DLP 仍然很難。
Pohlig-Hellman及時解決了DLP $ O(\sqrt{p}) $ ， 在哪裡 $ p $ 是你正在工作的團隊中最大的主要因素。你正在工作 $ \mathbb{Z}_n^* $ , 有順序 $ \varphi(n) = (p-1)(q-1) $ ，因此，如果這會影響許多小素數，您就會遇到問題。
這是Sophie Germain 素數背後的基礎，它們是以下形式的素數 $ q = 2p+1 $ ， 在哪裡 $ p $ 是素數。這滿足 $ \varphi(q) = 2p $ ，所以它們是“最小平滑的”（對於任何奇數素數，我們知道 $ 2 $ 會分 $ \varphi(q) $ . Sophie Germain 素數是唯一的小除數的素數）。