同餘方程求解器

輸入引數

方程型別

係數 a ax ≡ b (mod m) 中的 a

常數 b ax ≡ b (mod m) 中的 b

模數 m 模數（必須為正整數）

快速示例：

計算結果

輸入引數後點擊"求解方程"

演算法說明：

1. 線性同餘方程 ax ≡ b (mod m)：

解的存在性：方程有解當且僅當 gcd(a, m) | b（即 b 能被 gcd(a, m) 整除）
解的個數：如果有解，則在模 m 意義下有 d = gcd(a, m) 個不同的解
求解方法：
1. 計算 d = gcd(a, m)
2. 檢查 d | b，如果不滿足則無解
3. 將方程兩邊同時除以 d：(a/d)x ≡ (b/d) (mod m/d)
4. 使用擴充套件歐幾里得演算法求 a/d 在模 m/d 下的逆元 a'
5. 計算 x₀ = a' × (b/d) mod (m/d)
6. 通解為：x = x₀ + k(m/d)，其中 k = 0, 1, ..., d-1

2. 指數同餘方程 a^x ≡ b (mod m)（離散對數問題）：

問題描述：給定 a, b, m，求最小的非負整數 x 使得 a^x ≡ b (mod m)
解的存在性：
- 如果 gcd(a, m) = 1，且 b 是 a 在模 m 下生成的迴圈群中的元素，則有解
- 檢查方法：列舉 a 的冪次，直到找到 b 或遍歷完一個週期
求解方法：
- 小範圍暴力搜尋：列舉 x = 0, 1, 2, ... 直到找到解或達到搜尋上限
- Baby-step Giant-step 演算法：時間複雜度 O(√m)，適用於中等規模
- Pollard's rho 演算法：適用於大素數模
週期性：如果 x₀ 是一個解，則 x = x₀ + kφ(m) 也是解（其中 φ(m) 是尤拉函式）

3. 應用場景：

密碼學：RSA、Diffie-Hellman 金鑰交換、ElGamal 加密
數論研究：原根、二次剩餘、中國剩餘定理
隨機數生成：線性同餘生成器（LCG）
雜湊函式：模運算在雜湊表中的應用
競賽程式設計：快速冪、模逆、數論題目

演算法複雜度：

線性同餘方程：O(log m)（擴充套件歐幾里得演算法的複雜度）
指數同餘方程（暴力）：O(n)，其中 n 是搜尋上限
指數同餘方程（BSGS）：O(√m)，需要額外空間

重要定理：

貝祖定理：方程 ax + my = gcd(a, m) 總有整數解
費馬小定理：如果 p 是素數且 gcd(a, p) = 1，則 a^(p-1) ≡ 1 (mod p)
尤拉定理：如果 gcd(a, m) = 1，則 a^φ(m) ≡ 1 (mod m)
中國剩餘定理：可以求解同餘方程組