求解部分已知組中的離散對數

假設我有一個小組 $ G $ 順序不明 $ n $ 在哪裡 $ n=p^k\cdot s $ , $ \gcd(p,s)=1 $ , $ p $ 是已知素數， $ k,s $ 是未知的正整數和 $ k,s\ge1 $ . （已知 - $ p $ 和 $ p\mid n $ , 未知 - $ n,k,s $ ）。假設很容易解決階子群中的離散對數問題 $ p $ .

問題

1. 我知道如果我有一個上限 $ n $ ，我可以使用Baby step-giant step來解決離散登錄 $ G $ . 如果您知道上限，Pohlig-Hellman 是否也有效？
2. 我可以解決離散日誌問題嗎 $ G $ 在上述組設置中使用 Pohlig-Hellman 算法或任何其他具有平方根複雜度的算法？
3. 能找到嗎 $ k $ 使用任何離散對數求解算法？

我的可能答案

2. 假設 Pohlig-Hellman 僅在您準確知道組順序的情況下才有效，那麼不，我無法解決離散對數問題 $ G $ 我不知道 $ n $ （或者 $ k $ 對於這個問題）。
3. 如果我使用嬰兒步巨人步，不確定答案是什麼，但我認為你找不到 $ k $ 使用 Pohlig-Hellman。

在填補空白和驗證我的答案方面需要幫助。

Pohlig–Hellman 算法不能按原樣使用，但可以對其進行修改以利用已知的部分因式分解 $ n $ . 假設你需要找到這樣的 $ x $ 那 $ g^x=h $ . 這可以按如下方式完成：

1. 選擇小 $ k’ $ 這樣 $ k’\ge k $ . 如果上界 $ n $ 是 $ n’ $ ， 然後 $ k’=\lfloor\log_pn’\rfloor $ 可以使用。
2. 放 $ g’=g^{p^{k’}} $ 和 $ h’=h^{p^{k’}} $ . 現在，訂單 $ g’ $ 和 $ h’ $ 劃分 $ s $ .
3. 使用嬰兒步巨步算法求離散對數 $ h’ $ 到基地 $ g’ $ . 如果一個好的上限 $ s $ 未知，可以以指數增加的上限多次執行該算法。
4. 同理，使用baby-step Giant-step算法求 $ s $ ，例如，通過找到的離散對數 $ (g’)^{-1} $ 到基地 $ g’ $ . 如果 $ g $ 不是生成器，您可能會找到一個值 $ s’ $ 不同於 $ s $ （但它會分裂 $ s $ ）。在這種情況下， $ g $ 位於一個大小的子組中 $ p^ks’ $ ，所以你可以假設這個子組是整個組。
5. 然後，使用 Pohlig-Hellman 算法求離散對數 $ h^s $ 到基地 $ g^s $ . 兩個元素都在 size 的子組中 $ p^k $ .
6. 用中國剩餘定理求對數 $ h $ 到基地 $ g $ .

尋找 $ k $ ，首先用上面的算法找到 $ s $ . 那麼，如果你有一台發電機 $ g $ , 找到最小的 $ k $ 這樣 $ g^{p^ks}=e $ ， 在哪裡 $ e $ 是中性元素。如果沒有已知的生成器，則可以使用多個隨機元素代替，以使找到正確的機率 $ k $ 任意接近 $ 1 $ . 當沒有已知生成器時，沒有確定性算法適用於任意組，因為所有已知元素都可能位於 size 的子組中 $ p^{k-1}s $ ，因此無法判斷實際尺寸不是 $ p^{k-1}s $ 但實際上 $ p^ks $ .

引用自：https://crypto.stackexchange.com/questions/64132