灯，等灯等灯
线性同余方程组与格基约化问题
前言
没有听到吗？在耳边回荡着的钟声。
传闻中，远古文明能够捕猎闪电，将其封印在蜿蜒曲折的法阵中，用以驱动炼金术的最高成就——机械之心。
而在诸多机械之心的流派里，蔚蓝是曾经的王者。无信者窃取神明的奇迹，沉湎于蔚蓝创造出来的虚幻之间，得以逃避残酷的现实。
只是，火已渐熄，位不见王影。那一抹纯净的蔚蓝也逐渐染上铜锈和铁锈的颜色。破落的圣殿中只剩无名的巡礼者，还在追寻当年先知摩尔留下的足迹。
此时才明白，那则预言的含义：火焰熄灭之时，钟声响起，余灰纷沓而来，解开沉寂千年的机关，点亮传承的图腾。无火的余灰不能成为柴薪，可也许正因这样，才会如此向往光明吧。
还没有听到吗？那回荡在耳边的，古老而熟悉的，钟声——
灯，等灯等灯
以上是 Hackergame 2021 的一道点灯题的题文。
解这题的时候连线代都不会，拿到神的题解也跑不起来，后来才知道 Sagemath 要另行安装， pip install sage 是无用的。
前些天在单人豪华房里坐了几天牢，趁机也入门了一下格密码，隐约联想到这道题有点类似 CVP 的感觉，而再回头看神的题解果真也是这个思路，如今便借着学习一下 Python 和格。
考虑到读者水平可能与我相近，故以下的分析我尽可能做到详细，几乎每一步都有分析，相应的，文章篇幅也会比较长。如果能认真读完并理解，相信会有不小的收获。
题目链接
好吧已经 Hackergame 2022 了，关了。
灯 by mcfx详解
注：此题共 3 关，为 Level0 、 Level1 及 Level2 ，由于 Level1 综合了三关的解法，故以下均以 Level1 为例。
准备数据及函数
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75from sage.all import *
import sys, requests
target = [
[189, 189, 189, 189, 189, 33, 33, 33, 189, 189, 189, 189],
[189, 189, 189, 33, 33, 33, 189, 33, 44, 189, 189, 189],
[189, 189, 189, 189, 189, 33, 33, 33, 33, 189, 189, 189],
[189, 189, 189, 189, 189, 33, 189, 33, 33, 189, 189, 189],
[189, 189, 189, 33, 33, 189, 189, 33, 33, 33, 189, 189],
[189, 134, 33, 33, 189, 189, 189, 189, 33, 33, 189, 189],
[189, 144, 33, 33, 189, 189, 189, 189, 33, 189, 189, 189],
[189, 142, 33, 33, 189, 189, 189, 189, 33, 33, 33, 189],
[189, 100, 142, 33, 189, 189, 189, 189, 33, 33, 33, 189],
[189, 142, 142, 189, 189, 189, 189, 189, 189, 33, 189, 189],
[189, 59, 142, 33, 189, 189, 189, 189, 33, 189, 189, 189],
[189, 189, 33, 33, 189, 189, 189, 189, 189, 189, 189, 189],
]
def level01_val(i, j, x, y):
if (x == i or y == j):
return 3 - (abs(x - i) + abs(y - j))
return 0
def level2_val(i, j, x, y):
return [31, 63, 127][max(abs(x - i), abs(y - j))]
levels = [
(level01_val, '''
............
............
............
............
............
............
............
............
............
............
............
............
'''),
(level01_val, '''
............
............
..X.X.......
..XXX.......
..X.X.......
............
.......XXX..
.......X....
.......X.X..
.......XXX..
............
............
'''),
(level2_val, '''
............
............
..X.X...XX..
..X.X...X...
..XXX..XX...
............
............
..XXX..XXX..
...X...X....
...X...XXX..
............
............
''')
]
def id(x, y): return x * 12 + y
level_id = int(sys.argv[1])
ban = list(map(lambda x: [y == 'X'for y in x], levels[level_id][1].split()))from sage.all import *
首先要安装 Sagemath，因为 Sagemath 在 Windows 下运行也是要虚拟出一个 Unix 环境，故建议在 WSL 里sudo apt install sagemath，可能中途要apt-get upgrade。sys.argv[1]argv[0]是脚本名称（它是否为完整路径名取决于操作系统）。则argv[1]为省去后缀名的文件名，如 Level0 时为脚本名为0.py，argv[1]为 0 。ban = list(map(lambda x: [y == 'X'for y in x], levels[level_id][1].split()))lambda是 Python 的一个关键字，可以用来定义匿名函数。
所谓匿名函数，就是没有名字的函数，与命名函数类似，都有参数和返回值，只是没有名字。
如add=lambda x, y: x+y这个函数就将传入的两个参数相加，返回结果，即add(1, 2)等于1+2；map(lambda x: x+1, [1, 2, 3])将列表 [1, 2, 3] 中的元素分别加 1 ，其结果 [2, 3, 4] 。
这里map(lambda x: [y == 'X'for y in x], levels[level_id][1].split())一句是将上面定义的 12 阶方阵中X转为True，.转为False，然后放入一个列表ban中，此时ban为两级列表。
准备矩阵系数
1
2
3
4
5
6
7
8
9
10
11
12
13m = []
free = []
for i in range(12):
for j in range(12):
if ban[i][j]:
continue
free.append((i, j))
t = [0] * 144
for x in range(i - 2, i + 3):
for y in range(j - 2, j + 3):
if (0 <= x < 12) and (0 <= y < 12):
t[id(x, y)] = levels[level_id][0](i, j, x, y)
m.append(t + [0])levels[level_id][0](i, j, x, y)
这里是在元组里放函数，注意到上面的Levels=[(levev01_val, '''...'''),(...),(...)]，所以levels[level_id][0]是levev01_val函数。这样的用法如：1
2
3
4def add(x,y):return x+y
tup=(add,1,2)
print(tup[0](tup[1],tup[2]))
# 3list也可以实现类似操作，Python确实花.jpg。
不难发现， free[] 里放的是可以点的坐标，如 $(0,0),(0,1)…$
注意到，level01_val函数在上面已经定义：1
2
3
4def level01_val(i, j, x, y):
if (x == i or y == j):
return 3 - (abs(x - i) + abs(y - j))
return 0这个函数的参数中
i,j为操作的点(即按下的点)坐标，x,y为受影响的点坐标，返回值为受影响坐标的增量。
如(i,j)为 $(2,3)$ 时，若x,y为 $(2,3)$ ，则根据规则，返回值为 3 ，若x,y为 $(2,4)$ ，则返回值为 2 ，若x,y为 $(3,3)$ ，则返回值为 2 ，若x,y为 $(3,4)$ ，则返回值为 0 。如下表：x\y\返回值 2 3 4 1 0 2 0 2 2 3 2 3 0 2 0 1
2
3
4
5for x in range(i - 2, i + 3):
for y in range(j - 2, j + 3):
if (0 <= x < 12) and (0 <= y < 12):
t[id(x, y)] = levels[level_id][0](i, j, x, y)
m.append(t + [0])上面已经定义函数
def id(x, y): return x * 12 + y，即id函数把给定的坐标转为方阵一维展开后的位置，则此处把每个操作点对整个方阵 144 个位置影响(增量)后面补一个 0 （下面会解释为什么加一个 0 ）放入t[]中，此时t可以看作一个向量。
每个t[]补入m[]后，此时 $m$ 是一个 (144-16)x(144+1) 即 128x145 的矩阵，且第 145 列全为 0 ( 16 为 X 即不可操作点的数量)，如下：
$$
m=\begin{pmatrix}
3 & 2 & 1 & 0 & 0 & \cdots & 0 \\
2 & 3 & 2 & 1 & 0 & \cdots & 0 \\
1 & 2 & 3 & 2 & 1 & \cdots & 0 \\
0 & 1 & 2 & 3 & 2 & \cdots & 0 \\
\vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & 0 & 0 & \cdots & 0
\end{pmatrix}
$$注意：上面打省略号的地方不全为0！
比如第一行是由如下一个 12x12 的矩阵展开为一维形式：
$$
\begin{pmatrix}
3 & 2 & 1 & 0 & 0 & \cdots & 0 \\
2 & 0 & 0 & 0 & 0 & \cdots & 0 \\
1 & 0 & 0 & 0 & 0 & \cdots & 0 \\
0 & 0 & 0 & 0 & 0 & \cdots & 0 \\
\vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & 0 & 0 & \cdots & 0
\end{pmatrix}
$$1
2
3
4
5
6
7
8
9for i in range(144):
m.append([(i == j) * 256 for j in range(144)] + [0])
t = []
for i in range(12):
for j in range(12):
t.append(target[i][j])
C = 256
m.append([-x for x in t] + [C])不难看出，此时的 $m$ 为如下形式：
$$
m=\begin{pmatrix}
3 & 2 & 1 & 0 & 0 & \cdots & 0 & 0\\
2 & 3 & 2 & 1 & 0 & \cdots & 0 & 0\\
1 & 2 & 3 & 2 & 1 & \cdots & 0 & 0\\
0 & 1 & 2 & 3 & 2 & \cdots & 0 & 0\\
\vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & 0 & 0 & 0 & \cdots & 3 & 0\\
256 & 0 & 0 & 0 & 0 & \cdots & 0 & 0\\
0 & 256 & 0 & 0 & 0 & \cdots & 0 & 0\\
0 & 0 & 256 & 0 & 0 & \cdots & 0 & 0\\
0 & 0 & 0 & 256 & 0 & \cdots & 0 & 0\\
0 & 0 & 0 & 0 & 256 & \cdots & 0 & 0\\
\vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & 0 & 0 & 0 & \cdots & 256 & 0 \\
-189 & -189 & -189 & -189 & -189 & \cdots & -189 & 256\\
\end{pmatrix}
$$此时矩阵 $m$ 的前 272 个行向量(即除开最后一个行向量)的整系数线性组合即为操作后可以得到的方阵化为一维后的向量， Level0 时只需令该向量与解向量相等，而 Level1 和 Level2 则需要算出离解向量最近的可由这 272 个向量整数系线性表出的向量作为新的解向量，因为我们不保证在一些点不可操作的前提下仍能整数系线性表出解向量(重点，敲黑板) 。
同时由于题目在模意义下进行，所以若解出的系数为负整数也可以模 256 化为正整数。
而 $m$ 的最后一个行向量为负的解向量，这里留给后面解释。1
2
3
4n = len(m)
print('pre ok')
m2 = Matrix(m).LLL()
print('lll ok')这里 n 取得 m 的行向量数，即 (144-16+144+1)=273 ，然后对 m 跑 LLL 算法进行格基规约，仍然得到一个 273x145 的矩阵。
我最常用的求 CVP 的近似解的办法是，给原来每个向量后面加个 0，然后再加个新向量，前面的位置是欲求 CVP 的向量，最后是一个很大的常数。给这个新的格跑一遍 LLL，结果中最后是大常数的那一行，就是我们想要的答案。—— mcfx
这就是为什么最后要补一列零向量的原因。
同时上面有一个细节，那就是 $m$ 的最后一个行向量为负的解向量，结合神的解释，我发现，若矩阵中最后一个行向量的最后一个维度为大常数，其他行向量的最后一个维度为 0 ，那么 LLL 后最后这个行向量只是与其他行向量的线性组合进行一次相加(或相减)，也就是说，这个方法将 CVP 化为 SVP 问题时，求解 SVP 的过程中不会对这个特殊行向量进行任何数乘！ 那么将这个向量直接乘上-1然后加上原来的解向量再抹去最后一维就是CVP的解了。
同时我观察了 m2 (即m.LLL后的结果)的特征，发现 273 个行向量中的 128 个均为零向量，恰为 273-145 个。这里有一个有趣的问题，那就是这 273 组基是否可以互相线性表出。在线性代数中，一般的，我们在欧几里得空间即实数域里讨论向量的实数系组合问题，此时 145 维向量空间里的每个向量都可以由 145 个线性无关的向量线性表出。而格中是在向量的整数系组合下讨论问题，此时情况就有所不同了，比如以 $(1,1)$ 和 $(-1,1)$ 为基张成的格并不包括 $(1,0)$ 等向量，即不存在整数 $m,n$ 满足 $m*(1,1)+n*(-1,1)=(1,0)$ 。
找到 CVP 的答案
1
2
3
4
5
6for i in range(n):
if m2[i][144]:
for j in range(144):
m[-1][j] = m2[i][j] - m[-1][j]
print(sum(abs(m2[i][j]) for j in range(144)))
break由上面分析可知，此时
m[-1]的前 144 维就是新的解向量。至此， Level1 和 Level2 就可以化为 Level0 的解法了。跑高斯消元求解
1
2
3
4
5
6
7s = []
for i in range(144):
t = []
for j in range(len(free)):
t.append(m[j][i])
t.append(m[-1][i] % 256)
s.append(t)上面知道
free[]是可以操作的点的坐标列表，故len(free[])即为 144-16=128 。
这里取 $m$ 的前 (144-16)=128 个行向量的前 144 维进行转置作为系数矩阵与 $m$ 的最后一行向量的前 144 维变为列向量，合成增广矩阵，即为一个标准的非齐次线性方程组，即 $s$ 为一个如下的 144x145 的矩阵：
$$
s=\begin{pmatrix}
3 & 2 & 1 & 0 & 0 & \cdots & 0 & 189\\
2 & 3 & 2 & 1 & 0 & \cdots & 0 & 190\\
1 & 2 & 3 & 2 & 1 & \cdots & 0 & 191\\
0 & 1 & 2 & 3 & 2 & \cdots & 0 & 189\\
\vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & 0 & 0 & 0 & \cdots & 3 & 189
\end{pmatrix}
$$1
2
3
4
5
6
7
8for i in range(len(free)):
for j in range(i + 1, 144):
while s[j][i]:
t = s[i][i] // s[j][i]
for k in range(len(free) + 1):
s[i][k], s[j][k] = s[j][k], (s[i][k] - s[j][k] * t) % 256
for i in range(len(free), 144):
assert s[i][len(free)] == 0经以上消元后 $s$ 的第 129 行到最后一行均为 0 ，且系数矩阵与增广矩阵等秩，方程组有唯一解， $s$ 为如下的上三角矩阵：
$$
s=\begin{pmatrix}
1 & 0 & 0 & 0 & 0 & \cdots & 0 & 188\\
0 & 1 & 0 & 0 & 0 & \cdots & 0 & 188\\
0 & 0 & 1 & 0 & 0 & \cdots & 0 & 189\\
0 & 0 & 0 & 1 & 0 & \cdots & 0 & 189\\
0 & 0 & 0 & 0 & 1 & \cdots & 0 & 190\\
\vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & 0 & 0 & 0 & \cdots & 1 & 127
\end{pmatrix}
$$1
2
3
4
5
6
7
8ans = [0] * len(free)
for i in range(len(free) - 1, -1, -1):
t = s[i][len(free)]
for j in range(i + 1, len(free)):
t = (t - ans[j] * s[i][j]) % 256
for j in range(256):
if j * s[i][i] % 256 == t:
ans[i] = j提交答案
1
2
3
4
5
6
7
8
9
10
11
12
13sol = [[0] * 12 for _ in range(12)]
for i, (x, y) in enumerate(free):
sol[x][y] = ans[i]
print(sol)
data = {
'level': level_id,
'solution': str(sol),
}
headers = {'Cookie': 'xxx'}
r = requests.post('http://202.38.93.111:12768/submit', headers=headers, data=data)
print(r.text)
遇到的一些问题
- Latex 矩阵无法正常显示
有少少离奇，这个博客主题要在矩阵的每行结尾加四个反斜杠才能正常换行，否则就挤作一行。
