解決離散日誌問題
當模數是一個難以分解的合數時，離散對數問題能否解決，即當模數 $ n=p*q $ ， 在哪裡 $ p $ 和 $ q $ 是兩個大素數嗎？
問題正在解決 $ x $ 方程 $ g^x\bmod n=a $ , 給定整數 $ n $ , $ g $ , $ a $ ， 和 $ n $ 一個難以分解的大型複合材料（這意味著 $ n $ 是幾百位）。沒有說明問題實例是如何產生的。
至少對於問題的某些實例來說，這很難。特別是，如果其中一個因素 $ p $ 的 $ n $ 很大（例如，至少 1536 位），並且 $ p-1 $ 有很大的因素 $ p_0 $ （比如說，至少 256 位），以及 $ g $ 在 $ \Bbb Z_p^* $ 是 $ p_0 $ 或更大的倍數，然後是問題的一個實例 $ x $ 是隨機選擇的 $ [1,n/2] $ 和 $ a $ 計算為 $ g^x\bmod n=a $ 很難。論據：解決能力 $ g^x\bmod n=a $ 為了 $ x $ 和因式分解的知識 $ n $ 瑣碎地暗示解決問題的能力 $ g^x\bmod p=a\bmod p $ 為了 $ x $ （模組 $ p-1 $ )，這被認為很難；並且缺乏分解的知識 $ n $ 只能使問題的問題更難。
我在沒有證據的情況下推測條件“ $ p $ 大”可以替換為現有的“ $ n $ 太難考慮”；而且隨機實例很難。
在通常的離散對數方法中，Baby-step/Giant-step和Pollard’s Rho仍然適用，但成本 $ O(\sqrt x) $ 乘法模 $ n $ （和 Pollard 的 Rho 的中等記憶力）。這允許以適度的方式解決實例 $ x $ （比如標準 PC 的 80 位），但我認為沒有更好的方法來解決隨機實例。