我怎樣才能解決同餘模N？
我正在嘗試解決形式的一致性
$$ J_A \cdot a^e\equiv 1 \pmod n $$ 在哪裡 $ n=pq $ 為了 $ p,q $ 素數和 $ \gcd(e,\varphi(n))=\gcd(J_A,n)=1 $
求解 $ a\in \mathbb{Z} $ ， 按照 $ n,J_A $ 和 $ e $ .
我正在使用Page 451 書中的 GQ 簽名方案中的範例。
Nota Bene：這不是一個家庭作業問題。我正在尋找一種方法來實現它。
$ J_A \cdot a^e : \equiv : 1 :: \pmod{n} ;;;;; \iff ;;;;; a^e : \equiv ;; $ $ \operatorname{modinv} $ $ (J_A,\hspace{-0.02 in}n) :: \pmod{n} $
由於這是RSA 問題，已知最快的解決方法是分解 $ n $ 這揭示了 $ \lambda $ $ (n) $ ，
然後嘗試 $ ;;; a : = : \operatorname{mod}\left(\hspace{-0.03 in}(\operatorname{modinv}(J_A,\hspace{-0.02 in}n))^{\operatorname{modinv}(e,\hspace{.02 in}\lambda(n))},n\hspace{-0.03 in}\right) :::: $ .
看來您正在尋找解決 RSA 假設的方法。
RSA假設說：
如果對於任何機率多項式時間對手 $ \mathcal{A} $ , 在輸入 $ N,e,R $ ， 在哪裡 $ R\in_R \mathbb{Z}_N^* $ , 輸出 $ a $ 這樣 $ a^e \equiv R\pmod N $ 在安全參數中可以忽略不計 $ n $ .
用你的方式， $ R\equiv J_A^{-1} \pmod N $ . 解決 $ a $ 相當於解決 $ a \equiv R^d \pmod N $ . 因此，如果 RSA 假設成立，則找到 $ a $ 並不比因式分解更容易 $ N $ .
但有一個引理：
讓 $ N,e,d $ 是 RSA 參數和 $ f $ 是相對質數的整數 $ e $ . 有一個有效的程序給出 $ N,e,f $ （但不是 $ d $ ) 和一個值 $ (a^f)^d \pmod N $ 計算 $ a^d \pmod N $
我將給出一個關於這個引理的簡短證明：
證明：從 $ gcd(e,f)=1 $ 我們有 $ ve+uf=1 $ . 讓 $ s=(a^f)^d $ ， 然後 $ \bar{s}=a^vs^u $ 是我們想要的值。因為 $ \bar{s}^e=a^{ve+uf}=a $ ， 因此 $ a^d \equiv \bar{s} \pmod N $ .
所以，我的回答是：如果你不想考慮因素 $ N $ , 你可以找到這個值 $ (a^f)^d \pmod N $ 這樣 $ gcd(e,f)=1 $ .