如何求解带模运算等式s = (k*(h+x*r)) mod q中的未知量x

首先先明确原式的等价含义：你给出的等式 s = (k * (h + x * r)) mod q 等价于两边模q同余，即：

s ≡ k * (h + x * r) (mod q)

我们通常求解的是0 ≤ x < q范围内的整数解，默认q为素数（这类问题绝大多数场景q都取素数），求解步骤如下：

• 第一步：消去系数k的影响
  只要k不是q的倍数，就存在模q下的乘法逆元 k^{-1}，满足 k * k^{-1} ≡ 1 (mod q)。等式两边同时乘以k^{-1}，得到：
  s * k^{-1} ≡ h + x * r (mod q)
• 第二步：移项分离含x的项
  等式两边同时减去h，得到：
  s * k^{-1} - h ≡ x * r (mod q)
• 第三步：消去系数r的影响
  只要r不是q的倍数，同样存在模q下的乘法逆元 r^{-1}，等式两边同时乘以r^{-1}，即可得到x的解：
  x ≡ (s * k^{-1} - h) * r^{-1} (mod q)

特殊情况处理 #

• 如果q为合数，需要先计算最大公约数gcd(k, q)，如果s不能被gcd(k, q)整除，该等式无整数解；如果可以整除，将等式三个项都除以gcd(k, q)，得到新的模为q / gcd(k, q)的等式后再按上述步骤求解
• 如果r是q的倍数，直接代入原式验证：若两边相等则x可取任意整数，否则等式无解

逆元计算方法 #

如果q为素数，根据费马小定理，任意不是q倍数的整数a，其模q逆元为 a^{q-2} mod q，可以用快速幂算法快速计算得到结果。

内容的提问来源于stack exchange，提问作者yurishima