求解 x 的整数矩阵方程 Ax = B (mod q)

Question

我有一个已知的Python numpy数组A，其形状为n * m（m > n），一个已知的Python numpy数组B，其形状为n * 1，以及一个大于2的正整数q。A和中的所有值B 是区间 [0, q) 内的整数。我想知道如何使用 Python 计算 x 以满足 Ax = B (mod q) 。 x 可能有很多解，但找出其中一个解就足够了。非常感谢。

例如A、B、q设置如下。

from numpy import array
A = array([[2, 6, 2, 0], [4, 0, 2, 1], [3, 6, 5, 2]])
B = array([[1], [6], [0]])
q = 7

我尝试了以下代码，但没有一个是正确的。

1. lstsq（通常输出带有浮点数的答案）

代码：

from numpy.linalg import lstsq
return lstsq(A, B, rcond = None)[0].astype("int") % q

输出：

[[1]
 [0]
 [0]
 [0]]

但是，Ax 不等于 B。

2. 解决

代码：

from numpy.linalg import solve
return solve(A, B)

输出：

File "test.py", line 12, in sol2
    return solve(A, B)
  File "D:\Program Files\Python\lib\site-packages\numpy\linalg\linalg.py", line 396, in solve
    _assert_stacked_square(a)
  File "D:\Program Files\Python\lib\site-packages\numpy\linalg\linalg.py", line 213, in _assert_stacked_square
    raise LinAlgError('Last 2 dimensions of the array must be square')
numpy.linalg.LinAlgError: Last 2 dimensions of the array must be square

3. 来自 sympy 的 inv_mod

代码：

from numpy import asarray
from sympy import Matrix
A_inv = Matrix(A).inv_mod(q)
return asarray(A_inv.dot(B)).astype("int") % q

输出：

File "test.py", line 17, in sol3
    A_inv = Matrix(A).inv_mod(q)
  File "D:\Program Files\Python\lib\site-packages\sympy\matrices\matrices.py", line 2153, in inv_mod
    return _inv_mod(self, m)
  File "D:\Program Files\Python\lib\site-packages\sympy\matrices\inverse.py", line 169, in _inv_mod
    raise NonSquareMatrixError()
sympy.matrices.common.NonSquareMatrixError

4. 使用 (A * A.T).inv_mod(q)

代码：

from numpy import asarray, dot
from sympy import Matrix
return dot(dot(A.T, asarray(Matrix(dot(A, A.T)).inv_mod(q)).astype("int")), B) % q

输出：

File "test.py", line 23, in sol4
    x = dot(dot(A.T, asarray(Matrix(dot(A, A.T)).inv_mod(q)).astype("int")), B) % q
  File "D:\Program Files\Python\lib\site-packages\sympy\matrices\matrices.py", line 2153, in inv_mod
    return _inv_mod(self, m)
  File "D:\Program Files\Python\lib\site-packages\sympy\matrices\inverse.py", line 178, in _inv_mod
    raise NonInvertibleMatrixError('Matrix is not invertible (mod %d)' % m)
sympy.matrices.common.NonInvertibleMatrixError: Matrix is not invertible (mod 7)

Answer 1

假设

q

是解的约束，并且您只想在

x

中获得整数解，则使用“正常”优化无法解决此问题。为此，您将需要整数线性规划。 Scipy 为 ILP 提供了一个模块。

无约束优化

如果

q

仅是输入

A

和

B

的约束，并且您对实数解没问题，则

lstsq

正是您所需要的。你得到垃圾结果的原因是你通过使用

astype("int")

转换为 int 来切断小数点分隔符之后的所有内容。

import numpy as np
from numpy.linalg import lstsq

if __name__ == '__main__':
    A = np.array([[2, 6, 2, 0], [4, 0, 2, 1], [3, 6, 5, 2]])
    b = np.array([1, 6, 0])

    q = 7

    solution = lstsq(A, b, rcond=None)[0]
    print("real number solution:", solution)
    reconstructed = A @ solution
    # after rounding to 10 significant digits, this should be equal to b
    rounded_reconstructed = np.round(reconstructed, 10)
    print(rounded_reconstructed, b)

    assert all(np.isclose(reconstructed, b)), "unequal after rounding"

您可以看到，该解是非常接近实数的近似值。在这种情况下，大约为 15 位有效数字。这就是

lstsq

能给你的一切。如果您希望保持某些约束，则必须明确说明，NumPy 不会猜测。

约束优化

将约束优化问题转变为无约束优化问题的一种方法，

lstseq

等人。可以使用的是拉格朗日。 Here是一个相当不错的问题，涉及拉格朗日乘子。研究约束优化问题的另一个有用的东西是单纯形算法。

如果您寻找整数解，这不会对您有帮助。但如果你想要这些，很快就会变得更加困难。这是“真正的数学”。^[1]

一般建议

在你的问题上投入更多精力。有一个关于提出好问题的指南。

例如：了解您正在做什么、了解问题以及为什么需要某些东西会有所帮助。在这里，很难知道您正在寻找什么样的解决方案。它还有助于获取一些示例，不仅用于输入，还有助于获取您期望的输出。

---

[1]：实际上是离散数学=D