為什麼某些組表示更容易計算離散對數？

乘法組模式 $ p $ 與加法組 mod 等距 $ p-1 $ ，但計算加法組中的離散對數很容易，而完成乘法組中的離散對數通常很困難。

是什麼讓組表示對計算離散對數的複雜性如此重要？

好吧，同構的群並不意味著同構是有效可計算的。如果 $ G \simeq H $ 通過 $ \phi : G \rightarrow H $ 和 $ \phi $ 是可計算的，那麼確實，DLOG 並不難 $ G $ 比在 $ H $ 因為您可以轉換實例。

在你提到的情況下，我們有 $ G = \mathbb Z/(p-1) \mathbb Z $ 和 $ H = (\mathbb Z/p\mathbb Z)^\times $ . 一個有效的態射 $ \phi: G \rightarrow H $ 眾所周知，它被稱為“快速取冪”。所以 DLOG 並不難 $ G $ 比它在 $ H $ . 但是計算一個反向態射 $ \psi: H \rightarrow G $ 好像更難…

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