模乘逆元計算機

什麼是模乘逆元？

整數 a 對於模數 m 的模乘逆元是指在 [0, m-1] 範圍內的一個整數 x，使得：

它被寫作 a⁻¹ (mod m)，類似於普通算術中的乘法逆元（即 1/a），但應用於模運算領域。

關鍵條件： 逆元存在的當且僅當 gcd(a, m) = 1 — 也就是說，a 和 m 必須互質。

如何計算：擴展歐幾里得演算法

最有效的方法是使用擴展歐幾里得演算法。它能找到滿足貝祖等式的整數 x 和 y：

當 gcd(a, m) = 1 時，對等式兩邊取模 m 得到 a·x ≡ 1 (mod m)，因此 x 即為模逆元。

範例： 求 3⁻¹ (mod 7)：

擴展 GCD 給出：3·(5) + 7·(-2) = 15 − 14 = 1，因此 3⁻¹ ≡ 5 (mod 7)。驗證：3 × 5 = 15 = 2×7 + 1 ≡ 1 (mod 7) ✓

在密碼學與數學中的應用

常見問題解答