什麼是模反元素?
整數 a 對模數 m 的模乘法反元素,是指一個整數 x,使得 \((a \cdot x) \bmod m = 1\) 成立。它相當於模運算中的「除法」,在數論、RSA 加密系統以及許多編碼理論演算法中都扮演關鍵角色。本計算機透過擴展歐幾里得演算法(extended Euclidean algorithm)求出 x。
如何使用本計算機
輸入數字 a 與模數 m(m ≥ 2)。工具會回傳落在 0 ≤ x < m 範圍內、最小的非負反元素 x,並確認反元素是否存在,同時顯示 gcd(a, m)。若 gcd(a, m) ≠ 1,代表反元素不存在,結果會顯示為「無」。
公式說明
反元素只有在 \(\gcd(a, m) = 1\) 時才存在,也就是 a 與 m 互質。擴展歐幾里得演算法會找出滿足 \(a \cdot x + m \cdot y = \gcd(a, m)\) 的整數 x 與 y。當最大公因數為 1 時,把 x 對 m 取模即可得到反元素。若結果為負,再加上 m 即可正規化為正值。
$$\text{a} \cdot x \equiv 1 \pmod{\text{m}} \quad\Longrightarrow\quad x = \text{a}^{-1} \bmod \text{m}$$
實際範例
求 3 對模數 11 的反元素。我們要找出滿足 \(3x \equiv 1 \pmod{11}\) 的 x。試算一下,
$$3 \times 4 = 12 = 11 + 1 \quad\Longrightarrow\quad 12 \bmod 11 = 1$$因此 x = 4。擴展歐幾里得演算法也會得到相同結果,而 \(\gcd(3, 11) = 1\),證明反元素確實存在。
逐步說明:手算擴展歐幾里得演算法
a 模 m 的模反元素是滿足 \(a \cdot x \equiv 1 \pmod{m}\) 的數 x。它只在 \(\gcd(a, m) = 1\) 時存在。擴展歐幾里得演算法分三個步驟求出它。
- 重複除法。 用 m 除以 a,再用前一個除數除以餘數,依此類推,直到餘數為 0。最後一個非零餘數就是最大公因數。若它不是 1,則不存在反元素。
- 將 1 表示為組合。 逆向代入(回代),或在計算過程中追蹤係數,寫出 \(1 = a \cdot x + m \cdot y\)。這就是貝祖等式(Bézout identity)。
- 化簡 x。 取 \(x \bmod m\)。若 x 為負數,則加上 m(必要時重複),使其落在 0 到 m − 1 的範圍內。
實例:a = 7,m = 40。
| 步驟 | 除法 | 商 q | 餘數 |
|---|---|---|---|
| 1 | 40 = 5·7 + 5 | 5 | 5 |
| 2 | 7 = 1·5 + 2 | 1 | 2 |
| 3 | 5 = 2·2 + 1 | 2 | 1 |
| 4 | 2 = 2·1 + 0 | 2 | 0 |
最後一個非零餘數為 1,因此 \(\gcd(7, 40) = 1\),反元素存在。
回代:
$$1 = 5 - 2\cdot 2 = 5 - 2(7 - 5) = 3\cdot 5 - 2\cdot 7 = 3(40 - 5\cdot 7) - 2\cdot 7 = 3\cdot 40 - 17\cdot 7$$
因此 \(7 \cdot (-17) + 40 \cdot 3 = 1\),得到 \(x = -17\)。
迭代檢驗(a 的係數 t): 從 \(t_0 = 0\)(m = 40)與 \(t_1 = 1\)(a = 7)開始,然後使用 \(t_{k+1} = t_{k-1} - q_k \, t_k\)。
| 餘數 | 使用的 q | t |
|---|---|---|
| 40 | – | 0 |
| 7 | – | 1 |
| 5 | 5 | 0 − 5·1 = −5 |
| 2 | 1 | 1 − 1·(−5) = 6 |
| 1 | 2 | −5 − 2·6 = −17 |
餘數達到 1 的那一列給出 \(t = -17\)。化簡:\(-17 + 40 = \)23。
驗算: \(7 \cdot 23 = 161 = 4 \cdot 40 + 1\),所以 \(161 \bmod 40 = 1\)。✓
同樣的方法也適用於較大的數。對於 a = 17、m = 3120,它得到 x = 2753,因為 \(17 \cdot 2753 = 46801 = 15 \cdot 3120 + 1\)。這組數是經典的 RSA 教科書範例。
輸入範例及其反元素
下列每個反元素都滿足 \((a \cdot x) \bmod m = 1\)。當 \(\gcd(a, m) > 1\) 時,不存在反元素。
| a | m | gcd(a, m) | 反元素 x | 驗算 |
|---|---|---|---|---|
| 3 | 11 | 1 | 4 | 3·4 = 12 = 1·11 + 1 |
| 7 | 26 | 1 | 15 | 7·15 = 105 = 4·26 + 1 |
| 5 | 12 | 1 | 5 | 5·5 = 25 = 2·12 + 1 |
| 10 | 17 | 1 | 12 | 10·12 = 120 = 7·17 + 1 |
| 17 | 3120 | 1 | 2753 | 17·2753 = 46801 = 15·3120 + 1 |
| 4 | 6 | 2 | 無 | 4x mod 6 永遠是偶數,永遠不會是 1 |
| 6 | 9 | 3 | 無 | 6x mod 9 永遠是 3 的倍數,永遠不會是 1 |
注意到 5 是它自己在模 12 下的反元素。一般而言,\(x^2 \equiv 1 \pmod{m}\) 除了 1 之外還有其他解,因此某些數是自反元素(即自身的反元素)。
關鍵術語:互質、GCD、同餘與剩餘
- 模數 (m): 數值循環繞回的正整數,就像時鐘面上的數字。
- 同餘 (≡): \(a \equiv b \pmod{m}\) 表示 m 整除 \(a - b\),因此 a 與 b 除以 m 的餘數相同。
- GCD: 最大公因數,即能同時整除兩個數的最大整數。
- 互質(relatively prime): gcd 為 1 的兩個整數。這正是模反元素存在的條件。
- 貝祖等式(Bézout identity): 對整數 a 與 m,存在整數 x 與 y 使得 \(a \cdot x + m \cdot y = \gcd(a, m)\)。當 gcd 為 1 時,將此等式對 m 取模得到 \(a \cdot x \equiv 1\),因此 x 即為反元素。
- 剩餘類: 所有與某數模 m 餘數相同的整數所組成的集合。反元素作為剩餘類是唯一的,計算器回報的是 0 到 m − 1 之間的代表元。
- 模乘法反元素: 滿足 \(a \cdot x \equiv 1 \pmod{m}\) 的剩餘 \(x = a^{-1} \bmod m\)。
歐拉定理: 若 \(\gcd(a, m) = 1\),則 \(a^{\varphi(m)} \equiv 1 \pmod{m}\),其中 \(\varphi\) 是歐拉函數(Euler's totient function)。因此反元素也可以計算為 \(a^{\varphi(m)-1} \bmod m\)。
費馬小定理: 當 m = p 為質數時,\(\varphi(p) = p - 1\),因此對於任何不被 p 整除的 a,\(a^{-1} \equiv a^{p-2} \pmod{p}\)。例:\(3^{9} = 19683 = 1789 \cdot 11 + 4\),所以 \(3^{-1} \equiv 4 \pmod{11}\),與上表一致。冪次公式需要 m 的因數分解(以求出 \(\varphi\)),而擴展歐幾里得演算法不需要,因此對一般模數而言通常較快。
常見問題
什麼情況下反元素不存在?當 a 與 m 有大於 1 的公因數時——例如 4 對模數 6(gcd = 2)就沒有反元素。
m 一定要是質數嗎?不必。m 可以是任何 ≥ 2 的整數;重點只在於 a 與 m 是否互質。
答案會落在什麼範圍?反元素以最小的非負剩餘形式給出,介於 0 與 m − 1 之間。