如何在 IDEA 中執行乘法逆模
如何在國際數據加密算法中執行乘法逆模？我不明白如何執行它……
例如，假設我有一個值
cf80，出現在我面前的值是 this3080。這是我根據自己的理解所做的事情：answer = 53120 % 65537 53120(integer value of 3080) = 3080當我將結果轉換為十六進制時，該值為
3080但正確的結果應該是9194.
那麼，乘法逆 $ a $ 被定義為那個值 $ b $ 為此 $ a \times b = 1 $ ， 在哪裡 $ \times $ 是相關欄位/環/組中的乘法運算。
因為我們討論的是模 65537 的乘法組，這意味著問題是，給定 $ a $ ， 尋找 $ b $ 這樣 $ ab \bmod 65537 = 1 $ .
現在， % 運算符 is C 不這樣做。經典的方法是使用擴展歐幾里得算法，其中算法的兩個輸入是 $ a $ 和 $ 65537 $ ; 並讓它找到方程的解 $ ax + 65537y = GCD(a, 65537) = 1 $ ; 價值 $ x $ 是您正在尋找的乘法逆元。
當然，由於只有 65536 個可能的逆，另一種可能性是簡單地擁有 65536 個可能的逆的表，然後進行查找。在這種情況下，您可以使用擴展歐幾里得算法來建構表。
哦，作為提醒；就乘法而言，idea 將 0000 位模式解釋為值 65536（因為值 0 沒有倒數）。
一種方法是將要反轉的值取冪 $ 65537-2 $ . 您可以使用最短的加法鏈快速完成此操作 $ 65535 $ 模組 $ 65537 $ :
$$ \begin{eqnarray} a_0 &=& {\tt\text{0xcf80}} \ a_1 &=& a_0 \cdot a_0 \ a_2 &=& a_1 \cdot a_0 \ a_3 &=& a_2 \cdot a_2 \ a_4 &=& a_3 \cdot a_3 \ a_5 &=& a_4 \cdot a_2 \ a_6 &=& a_5 \cdot a_5 \ a_7 &=& a_6 \cdot a_6 \ a_8 &=& a_7 \cdot a_7 \ a_9 &=& a_8 \cdot a_8 \ a_{10} &=& a_9 \cdot a_5 \ a_{11} &=& a_{10} \cdot a_{10} \ a_{12} &=& a_{11} \cdot a_{11} \ a_{13} &=& a_{12} \cdot a_{12} \ a_{14} &=& a_{13} \cdot a_{13} \ a_{15} &=& a_{14} \cdot a_{14} \ a_{16} &=& a_{15} \cdot a_{15} \ a_{17} &=& a_{16} \cdot a_{16} \ a_{18} &=& a_{17} \cdot a_{17} \ a_{19} &=& a_{18} \cdot a_{10} \ inv &=& {\tt\text{0x9194}} = a_{19}. \end{eqnarray} $$ 請注意，根據您在 IDEA 中執行模乘的方式，您可能容易受到一些計時攻擊。