Rsa
基數未知的離散對數
我正在嘗試解決眾所周知的問題 $ g^x = y \pmod{N} $ 但僅在這種情況下 $ g $ 是未知的。我知道的 ：
- $ x $ 是一個素數： $ 2^{16} + 1 $
- $ y $ 已知
- $ N $ 是一個很大的數字，我設法將其分解為兩個“較小”的素數（例如每個 38 個數字）
我發現了各種處理離散對數的方法，但似乎它們總是旨在解決 $ x $ . 也許答案並不難找到，但這在這一點上有點超出我的數學技能:) 感謝任何幫助。
這實際上是一個 RSA 解密問題，而不是離散日誌問題。
在這種情況下，
$$ g = y^{x^{-1} \bmod \phi(N)} \pmod N $$ 如果你有分解 $ N = pq $ ， 在哪裡 $ p, q $ 都是素數，這本質上是：
$$ g = y^{x^{-1} \bmod (p-1)(q-1)} \bmod N $$ 你可以計算 $ x^{-1} \bmod (p-1)(q-1) $ （或者，同樣有效的方法， $ x^{-1} \bmod \text{lcm}((p-1)(q-1)) $ )，使用擴展歐幾里得算法計算乘法逆。