在一個群體中，是不是很難計算基數GGg給定G一種G一種g^a和一種一種a?
離散對數，即：計算 $ a $ 給定 $ g $ 和 $ g^a $ , 在某些組中被認為是一個難題。
是不是也很難計算 $ g $ 給定 $ g^a $ 和 $ a $ ?
這取決於。如果訂單 $ m $ 的 $ g $ 的組是已知的並且 $ a $ 有一個反模 $ m $ （當且僅當 $ a $ 互質於 $ m $ )，那麼很簡單：計算逆 $ b:=a^{-1}\bmod m $ （例如，使用歐幾里得算法），併計算冪 $ (g^a)^b $ . 根據拉格朗日定理，這等於 $ g $ .
但是，有些情況很難處理：例如，當 $ n=pq $ 是兩個未知素數的乘積 $ p,q $ 和 $ g\in\mathbb Z/n\mathbb Z $ ，那麼這個任務就相當於解密RSA密文 $ g^a $ 關於公鑰 $ (n,a) $ ，這通常被認為是困難的。
如果你知道的話 $ a $ ，你也知道 $ \frac{1}{a} $ 然後 $ g=(g^a)^{\frac{1}{a}} $ .
現在，回答要解決的問題 $ X^r - a = 0 $ ， 什麼時候 $ r \mid (p-1) $ . 如果我的分析是正確的，如果 $ r\mid (p-1) $ ，平方根算法可以很容易地根據素數的形式進行調整 $ p $ .
- 如果 $ p=2rq + 2r -1 $ ，這是一個確定的情況：讓$$ y_0=a^{\frac{p+1}{2 \times r}} \quad \Longrightarrow \quad y_0^r=\left(\frac{a}{p}\right) \times a $$
那麼如果 $ a \in QR(p) $ ，一個特定的解決方案是 $ y_0=a^{\frac{p+1}{2 \times r}} $ 否則無解！
- 如果 $ p $ 另一種形式：一個特定的解可以通過機率算法來計算，這裡太複雜了，無法公開。
順便說一下，當計算一個特定的解決方案時，所有的 $ r $ 根是共軛的，形式為 $ y_i =\mu_i \times y_0 ;\cdots ; \mu_i $ 其中一個 $ r $ $ r $ 團結的根源。
我強調加密協議應該適當地指定給定協議解決方案中唯一性的條件，在這種情況下，我們可以使用濫用符號，如 $ \frac{1}{a} $ .
並且應該始終有一種方法來選擇合適的解決方案。我這裡提到的算法可以用 Henri Cohen 的書中給出的背景來證明，他是 BDX 數學 Dpt 的前教授。