JSER

同余方程求解器

输入参数

快速示例：

计算结果

输入参数后点击"求解方程"

算法说明：

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)
  • 中国剩余定理：可以求解同余方程组