簡介

模逆元（Modular multiplicative inverse）也稱為模反元素、模倒數、數論倒數。模逆元是數論中的概念，指的是在模 $m$ 的情況下，某個數 $a$ 存在一個數 $x$，使得：

$$a \cdot x \equiv 1 \pmod{m}$$

這個情況下，$x$ 就是 $a$ 在模 $m$ 下的乘法模逆元，只有在 $a$ 和 $m$ 互質 (即 $\gcd(a, m) = 1$) 的情況下，這個模逆元 $x$ 才會存在。

求解模逆元的方法

擴展歐幾里得演算法（Extended Euclidean Algorithm）

理論

擴展歐幾里得演算法根據輾轉相除法（Euclidean Algorithm），並能求出整數係數 $x$ 和 $y$ 使得：

$$\text{gcd}(a,m)=ax+my$$

根據貝祖定理（Bézout’s Identity），如果 $\gcd(a,m)=1$ ，則一定存在整數 $x$, $y$ 使得：

$$ax+my=1$$

此時，$x$ 即為 $a$ 在模 $m$ 下的 模逆元，即：

$$a^{−1} \equiv x \pmod{m}$$

步驟

1. 對於給定的 $a$ 和模數 $m$，使用擴展歐幾里得算法求解: $ax + my = \gcd(a,m)$

2. 若 $\gcd(a,m) \neq 1$，則模逆元不存在

3. 若 $\gcd(a,m) = 1$，則所求的係數 $x$ 即為模逆元

   • 若 $x < 0$，需要加上模數 $m$ 使結果為正
   • 最終結果應滿足 $0 \leq x < m$

範例

求解 $3$ 模 $7$ 的乘法逆元。

1. 使用擴展歐幾里得算法求解 $3x + 7y = \gcd(3,7)$

   計算過程: $$ \begin{align*} 7 &= 2 \times 3 + 1 \\ 3 &= 3 \times 1 + 0 \\ \Rightarrow& \gcd(3, 7) = 1 \end{align*} $$

   逆推係數: $$ \begin{align*} 1 &= 7 - 2 \times 3 \\ 1 &= 1 \times 7 + (-2) \times 3 \end{align*} $$

2. 得到 $3 \times (-2) + 7 \times 1 = 1$

3. 因此 $x = -2$ 即為模逆元

   • 由於 $-2 < 0$，需要加上模數 $7$
   • $-2 + 7 = 5$
   • 所以 $3$ 模 $7$ 的乘法逆元為 $5$

驗證: $3 \times 5 = 15 \equiv 1 \pmod{7}$

程式碼

#include <iostream>
using namespace std;

// 擴展歐幾里得算法
// 返回 gcd(a,b) 並且通過引用返回係數 x 和 y
long long extended_gcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long x1, y1;
    long long gcd = extended_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return gcd;
}

// 計算模逆元
// 返回 a 模 m 的乘法逆元，若不存在則返回 -1
long long mod_inverse(long long a, long long m) {
    long long x, y;
    long long gcd = extended_gcd(a, m, x, y);
    
    if (gcd != 1) {
        return -1;  // 模逆元不存在
    }
    
    // 確保結果為正且小於 m
    return (x % m + m) % m;
}

int main() {
    // 測試案例
    long long a = 3;
    long long m = 7;
    
    long long inv = mod_inverse(a, m);
    
    if (inv == -1) {
        cout << a << " 模 " << m << " 的乘法逆元不存在" << endl;
    } else {
        cout << a << " 模 " << m << " 的乘法逆元為: " << inv << endl;
        
        // 驗證結果
        cout << "驗證: " << a << " * " << inv << " mod " << m 
             << " = " << (a * inv) % m << endl;
    }
    
    return 0;
}

費馬小定理（Fermat’s Little Theorem）

理論

費馬小定理指出，若 $m$ 是質數， $a$ 是一個整數，且 $a$ 與 $m$ 互質（即 $\gcd(a, m) = 1$），則有：

$$ a^{m-1} \equiv 1 \pmod{m} $$

這表示，當 $a$ 和 $m$ 互質時，$a$ 的 $m-1$ 次方在模 $m$ 下同餘於 1。

利用費馬小定理，我們可以計算模逆元。在模 $m$ 的意義下，數 $a$ 的乘法逆元是指一個整數 $x$，使得：

$$ a \times x \equiv 1 \pmod{m} $$

根據費馬小定理，我們有：

$$ a^{m-1} \equiv 1 \pmod{m} $$

這可以重寫為：

$$ a \times a^{m-2} \equiv 1 \pmod{m} $$

因此，$a^{m-2}$ 就是 $a$ 在模 $m$ 下的乘法逆元。

步驟

1. 確認條件： 確保 $m$ 是質數，且 $a$ 與 $m$ 互質（即 $\gcd(a, m) = 1$）。
2. 計算 $a^{m-2} \mod m$： 使用快速冪算法計算 $a$ 的 $m-2$ 次方在模 $m$ 下的值。

範例

假設我們要計算 3 在模 7 下的乘法逆元。因為 7 是質數，且 3 與 7 互質，我們可以使用費馬小定理。根據定理，3 的逆元是：

$$ 3^{7-2} \mod 7 = 3^5 \mod 7 $$

計算過程如下：

• $3^2 = 9 \equiv 2 \pmod{7}$
• $3^4 = (3^2)^2 = 2^2 = 4 \pmod{7}$
• $3^5 = 3^4 \times 3 = 4 \times 3 = 12 \equiv 5 \pmod{7}$

因此，3 在模 7 下的乘法逆元是 5，因為：

$$ 3 \times 5 = 15 \equiv 1 \pmod{7} $$

程式碼

#include <iostream>
using namespace std;

// 快速冪算法計算 a^b % p
long long mod_exp(long long a, long long b, long long p) {
    long long result = 1;
    a = a % p;
    while (b > 0) {
        if (b % 2 == 1) {                   // 如果 b 是奇數
            result = (result * a) % p;
        }
        b = b >> 1;                         // 將 b 除以 2
        a = (a * a) % p;                    // 將 a 平方
    }
    return result;
}

// 計算 a 在模 p 下的乘法逆元
long long mod_inverse(long long a, long long p) {
    return mod_exp(a, p - 2, p);
}

int main() {
    long long a = 3, p = 7;
    cout << "The modular inverse of " << a << " mod " << p << " is " << mod_inverse(a, p) << endl;
    return 0;
}

應用

1. 密碼學
   • RSA 加密算法： RSA 算法是目前最廣泛使用的非對稱加密算法之一。模逆元在 RSA 算法中扮演著至關重要的角色，它被用於計算私鑰。
   • 橢圓曲線密碼學: 在橢圓曲線密碼學中，模逆元用於計算有限域上的點加法和點倍乘操作中的斜率，以實現安全的加密和簽名功能。
   • Digital Signature Algorithm: 在數位簽章演算法（DSA）中，模逆元用於計算簽章值
2. 計算機科學
   • Rolling Hash: 在 Rolling Hash 演算法中，模逆元用於在從哈希值中移除字串前端字元時，透過乘以進制的模逆元來有效地更新哈希值。

參考資料

• Wikipedia - Modular multiplicative inverse
• Wikipedia - Euclidean algorithm
• Wikipedia - Extended Euclidean algorithm
• Wikipedia - Bézout’s identity
• 計算模逆元與一些常用的競賽數學 by Grorge
• 【筆記】模逆元 by YuiHuang
• 乘法逆的概念如何應用在模運算，為什麼它對於仿射密碼等密碼的解密很重要？
• Wikipedia - RSA (cryptosystem)
• Wikipedia - Rolling hash
• Wikipedia - Elliptic-curve cryptography
• Wikipedia - Digital Signature Algorithm