在離散對數中超越 LSB
在離散對數中，我們使用蘇菲日耳曼素數 $ p=2q+1 $ 在哪裡 $ q $ 是一個素數。
然後我們知道最低有效位 $ x_0 $ 在
$$ g^{2x+x_0}=h\bmod p $$在哪裡 $ 2x+x_0 $ 是已知的離散對數 $ h\bmod p $ 關於已知生成器 $ g $ .
- 認為 $ g^2=r\bmod p $ 那為什麼我不能將問題減少到
$$ r^{x}=hg^{-x_0}\bmod p $$然後讓 $ x=2x’+x’_{0} $ 在哪裡 $ x’_0 $ 是 lsb 的 $ x $ 並遞歸解決查找問題 $ 2x+x_0 $ 這是離散對數 $ h\bmod p $ 關於發電機 $ g $ ? 2. 假設我知道 $ x_0 $ 在 $ g^{3x+x_0}=h\bmod p $ 在哪裡 $ x_0\in{0,1,2} $ 成立（也就是說，如果很容易求解離散對數的最後三位數 $ p=2q+1 $ 問題會更容易嗎？
如果 $ p = 2q+1 $ 在哪裡 $ q $ 是素數，然後我們可以有效地解決 $ x_0 \in {0, 1} $ 為了 $ g^{2x+x_0} = h \pmod p $ ， 如果 $ g $ 是一個發電機。
這是真實的; 這是觀察“如果 $ g $ 有訂單 $ a \times b $ 和 $ b $ 小，那麼如果 $ g^y = h $ ，那麼我們可以找到 $ y \bmod b $ 快速（具體來說，在 $ O(\sqrt{b}) $ 時間）。
作為 $ g $ 是整個組的生成器，它有順序 $ 2q $ ，所以我們可以找到 $ y \bmod 2 $ 很快（或者，正如你所說，找到 $ x_0 $ 在哪裡 $ y = 2x + x_0 $ )
認為 $ g^2 = r $ ，那麼為什麼我不能將問題簡化為 $ r^x = hg^{-x_0} \pmod p $
好吧，我想你可以，但是解決這個問題和 DLog 問題一樣困難（實際上，這是可以證明的；如果有一個 Oracle 這樣做，你可以解決整個 DLog 問題）。前面的觀察並不能幫你解決這個問題； $ r $ 有訂單 $ q $ ，這是一個素數；它沒有提供任何神奇的計算方法 $ x \bmod 2 $ ; 它所能做的最好的就是找到 $ x \bmod q $ 在 $ O(\sqrt{q}) $ 時間，我們有比這更有效的方法。
假設我知道 $ x_0 $ 在 $ g^{3x+x_0} = h \pmod p $ ， 哪個 $ x \in { 0, 1, 2 } $ ，會有幫助嗎？
是的，如果你有一個 Oracle 可以找到 $ y \bmod 3 $ ，那麼您就可以有效地解決 DLog 問題。也就是說，我們不知道有什麼方法可以有效地做到這一點（假設組的順序不是 3 的倍數）。