最近发现了格问题的极致恶心，所以还是得系统学一下；
LWE问题
1. 基本概念
对于已知一个矩阵 A 和一个向量 b ，他们满足关系式：\(b=As+e\)，e 为变换过程中的噪声向量，其值比较小，通过已知条件还原 s 称为LWE问题，又被称为误差还原，也是机器学习领域的一个容错学习问题；
对于基本的线性方程组求解：\(b=As\)问题，我们可以通过高斯消除法进行比较轻松的求解，但是对于引入噪声的情况，高斯消除法的消元过程会不断地放大噪声，导致最后的结果差异较大，所以我们应该采取更加合适的方法；
对于LWE问题，我们所得的 As 需要非常接近结果 b ，这和 CVP 问题又有了莫名地相似，也是一个 NP-hard 问题；
2. 分析过程
对于LWE问题，我们都是在有限域 p 上进行研究，所以它的基本表达式为\(As+e \equiv c \ (mod \ p)\)，可以转换为：
\[s_0a_{i,0}+s_1a_{i,1}+……+s_na_{i,n} \equiv c_i-e_i\ (mod\ p) \]进一步得到：
\[s_0a_{i,0}+s_1a_{i,1}+……+s_na_{i,n}+e_i+k_ip\equiv c_i \]之后构造格子 L ：
然后对格 L 使用 LLL 算法，得到无噪声下的最短向量 x（一个 good basis），然后再将 x 和 c 通过 babai 算法，求得在格基为 x 情况下 c 的 CVP 最近向量，这就是\(c-e\)的值，记为 b ，又因为：
所以可以直接求得 s 的值；
这里直接借用 Lazzaro佬的脚本 https://lazzzaro.github.io
点击查看代码
``` #脚本1-小规模 #Sage from sage.modules.free_module_integer import IntegerLatticerow =
column =
prime =
ma =
res =
W = matrix(ZZ, ma)
cc = vector(ZZ, res)
Babai's Nearest Plane algorithm
def Babai_closest_vector(M, G, target):
small = target
for _ in range(5):
for i in reversed(range(M.nrows())):
c = ((small * G[i]) / (G[i] * G[i])).round()
small -= M[i] * c
return target - small
A1 = matrix.identity(column)
Ap = matrix.identity(row) * prime
B = block_matrix([[Ap], [W]])
lattice = IntegerLattice(B, lll_reduce=True)
print("LLL done")
gram = lattice.reduced_basis.gram_schmidt()[0]
target = vector(ZZ, res)
re = Babai_closest_vector(lattice.reduced_basis, gram, target)
print("Closest Vector: {}".format(re))
R = IntegerModRing(prime)
M = Matrix(R, ma)
M = M.transpose()
ingredients = M.solve_right(re)
print("Ingredients: {}".format(ingredients))
m = ''
for i in range(len(ingredients)):
m += chr(ingredients[i])
print(m)
</details>