映射一個值GX模pGX反對pg^x bmod p到一個小區間[1…H][1…H][1…H]
我的問題在 $ \mathbb{Z}_p^{} $ 上下文，在哪裡 $ p=q\cdot k+1 $ 對於兩個素數 $ p,q $ 和 $ k \in \mathbb{Z} $ ; $ g $ 是子群的生成器 $ G_q $ 的 $ \mathbb{Z}_p^{} $ , 有序的 $ q $ .
讓我們考慮一個小 $ H $ （例如 $ H=1024 $ ) 和一個特定的 $ h \in \mathbb{Z}_p $ ， 和 $ 0 < h < H $ ，我們隨機選擇 $ g \in \mathbb{Z}_q $ : 是否真的（我希望如此）很容易找到一個 $ x $ 這樣 $ h \equiv (g^x \bmod p) \bmod H $ ?
我擔心的是：是否可以從隨機選擇的 $ g^x \bmod p $ 可以映射到目標（期望）值 $ h $ 在一個很小的範圍內，以便我們可以很容易地找到它，例如，在 $ \mathcal{O}(H) $ ?
只是隨機抽樣 $ x $ ， 和 $ [(g^x \bmod p) \bmod H] $ 將等於您的目標值 $ h $ 有機率 $ 1/H $ . 嘗試後 $ O(H) $ 候選人你會發現一個原像。
細則：從技術上講，機率並不完全 $ 1/H $ . 每個 $ h \in \mathbb{Z}_H $ 有 $ \lfloor \frac{p-1}{H} \rfloor $ 或者 $ \lceil \frac{p-1}{H} \rceil $ 映射下的原像 $ a \in \mathbb{Z}^_p \mapsto (a \bmod H) $ . 所以擊中目標的機率 $ h $ , 當你選擇一個隨機 $ a \in \mathbb{Z}_p^ $ ， 是 $ \lfloor \frac{p-1}{H} \rfloor/(p-1) $ 對於一些 $ h $ ‘沙 $ \lceil \frac{p-1}{H} \rceil/(p-1) $ 為他人。但如果 $ p $ 是指數級的（因為我懷疑它在這裡，因為你在談論離散日誌），那麼這個機率幾乎可以忽略不計 $ 1/H $ .