Discrete-Logarithm
可以認為以下離散對數問題很困難嗎？
為了 $ m, m’ $ , 是否可以找到 $ r, s, t $ 這樣 $ r^s = m $ 和 $ r^t = m’ $ 通知 $ G $ ， 在哪裡 $ G $ 是一個大素數。
你覺得這樣比較容易找到嗎 $ r $ 從 $ m $ 和 $ m’ $ ? 考慮到 $ m $ 和 $ m’ $ 是任意值。
編輯後，您的問題基本上是 DLOG 問題的一個問題，並且由於您沒有進一步指定您的組（我們稱之為 $ \mathbb{Z}_p $ ) 任何進一步，讓我們假設 $ p-1 $ 有一個已知的因式分解，這對於 DLOG 問題來說是相當標準的。
- 發現 $ r $ 是微不足道的：嘗試隨機值 $ r $ ，並檢查訂單是否為 $ p-1 $ . 如果你想讓它更有效率，計算訂單 $ m,m’ $ 首先，找到一個具有最小公倍數的元素。
- 發現 $ s,t $ 給定 $ r,m,m’ $ 只是 DLOG 問題的兩個實例，它們相互獨立。
相對於多項式有界的對手，兩次執行 DLOG 不會使問題本身變得更難 - 一個小的靜態因素，如 $ 2 $ 一點也不重要。然後，DLOG 問題只是困難的，如果至少有一個大型子組，並且像Pohlig-Hellman這樣的算法實際上單獨解決每個子組中的問題，然後組合解決方案。
如果你不熟悉 DLOG 問題的算法，可以這樣考慮：Factoring $ p-1 $ 很簡單，有了這些素數，我們可以應用分而治之的策略：解決每個素數的問題，然後使用中國剩餘定理組裝解決方案。所以這還不夠 $ p $ 是一個大素數。