利用LLL来解决线性方程组

LLL在密码学中是一个非常好用的工具。

我们知道格对于密码学分析有着极其重要的意义 对于一个方程组，如果我们能够证明它的解是格中的一个短向量，那么，我们就可以利用格来绕过传统的解方程方法，转而使用LLL来直接获得该解。

这篇文章主要讨论的是，假设我们从问题中抽象出了一个线性方程组，那么我们可以如何进行求解

一、使用LLL寻找一个多元线性方程的解

假设我们从某个问题中获得了方程：

a0x0+a1x1+...+anxn=sa_0x_0 + a_1x_1 + ... + a_nx_n = s

并且我们确信，我们所要找的解很小。

那么我们可以选择这样的构造这样的基：

$\mathbf{B} = \begin{pmatrix} \mathbf{I} & k\mathbf{a} \ 0 & -ks \end{pmatrix} $

其中，a\mathbf{a}代表列向量(a0 a1 ... an)T(a_0\ a_1\ ...\ a_n)^T

注：每一行为一个基向量

这样构造之后，我们就会发现：

对于一个行向量v=(v1 v2 ... vn 1)\mathbf{v} = (v_1\ v_2\ ... \ v_n\ 1)

$\mathbf{v}\mathbf{B} = \begin{pmatrix} v_1 & v_2& …& v_n& k(a_1v_1+a_2v_2 +…+a_nv_n-s)\end{pmatrix} $

由此可见，当我们把k设置的足够大，

那么当最后一个元素为0时，vB\mathbf{v}\mathbf{B}就足够短。

那么LLL在拼命寻找由基B\mathbf{B}优化而来的基时，不可避免的会发现这个向量

那么LLL会有相当大的概率返回给我们最后一个元素为0时对应的vB\mathbf{v}\mathbf{B}, 其中通过也就包含了我们要求解的x

\

sagemath中的矩阵对象自带.LLL()方法，这里给出一段示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 1. 准备数据
coeffs = [12, 23, 34]
target = 127
n = len(coeffs)
K = 1000  # 权重，要足够大

# 2. 初始化矩阵 (n+1) x (n+1)
# 这里的 ZZ 非常重要！
B = Matrix(ZZ, n + 1, n + 1)

# 3. 填充矩阵
# 填充单位阵部分
for i in range(n):
    B[i, i] = 1

# 填充最后一列（系数部分）
for i in range(n):
    B[i, n] = K * coeffs[i]

# 填充最后一行（目标值部分）
B[n, n] = -K * target


# 执行 LLL 算法
# 结果是一个新的矩阵，包含了规约后的基
res = B.LLL()

print("\nLLL 规约后的矩阵:")
print(res)

二、拓展到寻找多元线性方程组的解

当我们将问题从单一方程推广到方程组时，核心思想并没有改变：

我们将每一个方程视为一个独立的约束，并将这个约束映射到矩阵的一列中。 假设我们要解如下的线性方程组，包含 nn 个变量和 mm 个方程：

{a1,1x1+a1,2x2+⋯+a1,nxn=s1a2,1x1+a2,2x2+⋯+a2,nxn=s2⋮am,1x1+am,2x2+⋯+am,nxn=sm\begin{cases} a_{1,1}x_1 + a_{1,2}x_2 + \dots + a_{1,n}x_n = s_1 \\ a_{2,1}x_1 + a_{2,2}x_2 + \dots + a_{2,n}x_n = s_2 \\ \vdots \\ a_{m,1}x_1 + a_{m,2}x_2 + \dots + a_{m,n}x_n = s_m \end{cases}

我们需要构造一个维度为 (n+1)×(n+m)(n+1) \times (n+m) 的格基矩阵 B\mathbf{B}。 左侧 nn 列为单位阵，右侧 mm 列对应 mm 个方程的系数（乘以权重 KK）。

构造出的矩阵 B\mathbf{B} 如下所示：

B=[10⋯0Ka1,1Ka2,1⋯Kam,101⋯0Ka1,2Ka2,2⋯Kam,2⋮⋮⋱⋮⋮⋮⋱⋮00⋯1Ka1,nKa2,n⋯Kam,n00⋯0−Ks1−Ks2⋯−Ksm]\mathbf{B} = \left[ \begin{array}{cccc|cccc} 1 & 0 & \cdots & 0 & K a_{1,1} & K a_{2,1} & \cdots & K a_{m,1} \\ 0 & 1 & \cdots & 0 & K a_{1,2} & K a_{2,2} & \cdots & K a_{m,2} \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 & K a_{1,n} & K a_{2,n} & \cdots & K a_{m,n} \\ \hline 0 & 0 & \cdots & 0 & -K s_1 & -K s_2 & \cdots & -K s_m \end{array} \right]

对于解向量 v=(x1,…,xn,1)\mathbf{v} = (x_1, \dots, x_n, 1)，计算 vB\mathbf{v}\mathbf{B} 后，右侧的 mm 个分量将全部归零： $$ \mathbf{v}\mathbf{B} = \left( x_1, \ x_2, \ \dots, \ x_n, \ \ \underbrace{0, \ 0, \ \dots, \ 0}_{m \text{ 个}} \right) $$

也即是说LLL会很愿意返回给我们解向量 v=(x1,…,xn,1)\mathbf{v} = (x_1, \dots, x_n, 1)

三、进阶：处理模线性方程组

在密码学场景中，我们遇到的往往是定义在模 MM 上的方程组：

∑i=1naj,ixi≡sj(modM)(j=1,…,m)\sum_{i=1}^n a_{j,i}x_i \equiv s_j \pmod M \quad (j=1, \dots, m)

为了利用格消除模数的影响，我们需要为每一个方程增加一行，用于表示模数 MM 的倍数。

矩阵大小变为 (n+m+1)×(n+m)(n + m + 1) \times (n + m)。

Bmod=[Ka1,1⋯Kam,1In⋮⋱⋮Ka1,n⋯Kam,n0⋯0KM⋯0⋮⋱⋮⋮⋱⋮0⋯00⋯KM0⋯0−Ks1⋯−Ksm]\mathbf{B}_{mod} = \left[ \begin{array}{ccc|ccc} & & & K a_{1,1} & \cdots & K a_{m,1} \\ & \mathbf{I}_{n} & & \vdots & \ddots & \vdots \\ & & & K a_{1,n} & \cdots & K a_{m,n} \\ \hline 0 & \cdots & 0 & K M & \cdots & 0 \\ \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ 0 & \cdots & 0 & 0 & \cdots & K M \\ \hline 0 & \cdots & 0 & -K s_1 & \cdots & -K s_m \end{array} \right]

中间增加的 m×mm \times m 对角块允许格向量在每个方程的列上减去 KMKM 的整数倍，从而实现同余式归零。