在 mod 欄位中查找指數的底
我有以下等式：
$$ base^{exp} = number \pmod n : base,exp \in \mathbb{N} $$另一個已知的事實是：
$$ gcd(base, number) = 1 $$
$$ n = 2^{2048} $$基地=
數字=
我知道底數和數字，我該如何計算指數？這與密碼學有關，因為我正在嘗試解碼消息。
求解離散對數模 $ 2^n $ 簡單。
你依賴這個：
如果我們有（對於奇數 $ e $ )$$ (n 2^{k+1} + 2^k + 1)^e = b \pmod{2^\lambda} $$
然後要麼：
$$ (n 2^{k+1} + 2^k + 1)^e = b \pmod{2^{\lambda+1}} $$
或者
$$ (n 2^{k+1} + 2^k + 1)^{e + 2^{\lambda-k}} = b \pmod{2^{\lambda+1}} $$
這可以證明是因為 $ (n 2^{k+1} + 2^k + 1)^{2^{\lambda-k}} \equiv 1 + 2^\lambda \pmod {2^{\lambda+1}} $ （二項式定理），等等 $ (n 2^{k+1} + 2^k + 1)^{e + 2^{\lambda-k}} \equiv (n 2^{k+1} + 2^k + 1)^e \cdot (1 + 2^\lambda) \equiv $ $ (n 2^{k+1} + 2^k + 1)^e + 2^\lambda \pmod{ 2^{\lambda+1} } $
所以，你可以從底部開始找到你的指數， $ 9^1 = 9 \bmod 16 $ ，然後擴展它以增加 $ \lambda $ , 直到你擊中 $ \lambda = 2048 $