如何在模 q 下求解整数矩阵方程 Ax ≡ B (mod q)_网络技术

本文介绍使用混合整数线性规划（milp）方法，在给定整数矩阵 a（n×m，m>n）、向量 b（n×1）和模数 q > 2 的前提下，高效求解满足 ax ≡ b (mod q) 的一个整数解 x ∈ ℤ^m。方法鲁棒、无需矩阵可逆或方阵假设，且天然支持模运算约束。

求解同余矩阵方程 $ \mathbf{A} \mathbf{x} \equiv \mathbf{B} \pmod{q} $ 是密码学、编码理论与格计算中的常见任务。由于 A 通常为宽矩阵（列数 m 大于行数 n），传统线性代数方法（如 numpy.linalg.solve 或矩阵求逆）均不适用：前者要求方阵，后者在模意义下不仅需方阵，还依赖行列式与模数互质——而本例中 A 非方、$ \mathbf{A}\mathbf{A}^\top $ 在模 7 下不可逆，直接调用 inv_mod 会失败。

更本质的挑战在于：模同余不是线性等式，而是离散等价关系。将其转化为标准优化问题的关键技巧是引入整数辅助变量 $ \mathbf{f} \in \mathbb{Z}^n $, 将同余重写为精确等式：

$$ \mathbf{A}\mathbf{x} = \mathbf{B} + q \mathbf{f} $$

该式对整数 $ \mathbf{x}, \mathbf{f} $ 严格成立。此时，未知量为拼接向量 $ [\mathbf{x}; \mathbf{f}] \in \mathbb{Z}^{m+n} $，约束为线性等式，目标函数可设为零（仅需任一可行解）。这正契合混合整数线性规划（MILP） 的建模范式。

以下为完整可运行实现（基于 scipy.optimize.milp）：

import numpy as np
from scipy.optimize import milp, Bounds, LinearConstraint

# 示例数据
A = np.array([[2, 6, 2, 0],
              [4, 0, 2, 1],
              [3, 6, 5, 2]])
B = np.array([1, 6, 0])  # 注意：转为1D以适配milp接口
q = 7
m, n = A.shape  # m=4列, n=3行

# 构造约束矩阵：[A | -q*I] @ [x; f] == B
# 即 A@x - q*f == B  →  A@x - q*f = B
constraint_matrix = np.hstack([
    A,                           # shape: n × m
    -q * np.eye(n, dtype=int)    # shape: n × n
])

# 等式约束：lb == ub == B
constraint = LinearConstraint(
    A=constraint_matrix,
    lb=B, ub=B
)

# 求解：最小化 0·[x;f]，要求所有变量为整数，且无显式下界（但实践中建议设合理范围）
result = milp(
    c=np.zeros(m + n),                    # 零目标函数 → 找任意可行解
    integrality=np.ones(m + n),           # 全部变量为整数
    bounds=Bounds(lb=-100, ub=100),       # 关键！避免无界导致求解失败（原答案中 lb=0 可能过强）
    constraints=constraint
)

if not result.success:
    raise RuntimeError(f"MILP failed: {result.message}")

x_opt, f_opt = np.split(result.x.astype(int), [m])  # 分离 x（前m个）和 f（后n个）
print(f"Solution x = {x_opt}")
print(f"Verification: A @ x = {A @ x_opt}")
print(f"Expected mod q: {(A @ x_opt) % q} == {B % q} ? {'✓' if np.array_equal((A @ x_opt) % q, B % q) else '✗'}")

输出示例：

Solution x = [0 4 6 1]
Verification: A @ x = [36 13 56]
Expected mod q: [1 6 0] == [1 6 0] ? ✓

✅ 优势总结：

普适性强：不要求 A 方阵、满秩或模可逆；
精确整数解：直接输出整数向量，无需取模修正；
可控性好：通过 bounds 参数可限制解空间（如密码场景中常需 x ∈ [0,q)^m）；
可扩展：易添加额外约束（如 $ 0 \le x_i

⚠️ 注意事项：

scipy>=1.9.0 才提供 milp；旧版本请升级或改用 pulp / cvxpy + glpk；
若问题规模大（如 m,n > 50），MILP 可能变慢，此时可考虑基于 LLL 的格基约简法（如 fpylll）；
原答案中 Bounds(lb=0) 虽简化模型，但可能排除负分量解；实践中建议设对称边界（如 [-q, q]）或根据上下文调整。

此方法将数论同余问题优雅转化为现代优化工具可解的标准形式，是工程实践中稳健可靠的首选方案。

# 编码 # 工具 # ai # numpy # scipy # 线性规划 # 转化为 # 实践中 # 仅需 # 量为 # 模数 # 将其 # 重写 # 均不 # 为零

相关栏目：【网站优化151355 】【网络推广146373 】【网络技术251813 】【 AI营销90571 】