对格的理解还是太肤浅了，这里加强一下理论学习

一、格的定义

首先介绍一些基本概念 中的内积 定义欧几里得范数 为了研究整数集里的问题

假设在中有n个线性无关的向量，m>n

则 就是说只考虑向量的整系数线性组合，这在平面内会生成很多离散的点，实现了分割平面

image-20250428225623927

长得就像晶胞一样（Crystal)

基本平行多面体（Fundamental Parallelepiped）

给定基，我们可以定义一个基本平行多面体： 这个平行多面体可以看作格的“最小重复单元”，类似于晶体的“晶胞”。

需要遍历0到1，以覆盖这个晶胞

image-20250428230354533

这些向量称为格L的基，m是维数，n是格L的秩

格基可以写成一个矩阵 不同的基可以生成同一个格，不过，我们可以用晶胞作为每个格的区分标准，那么我们考察这个晶胞的体积，因为行列式本身就是对空间的拉伸程度，那我们计算这个晶胞体积，其实就是格的行列式 但是如果不满秩呢？

image-20250428232044265

那其实好像也能用每个线段长度来定义这个晶胞

换而言之，我们只计算n维子空间上的晶胞大小就行了，这个其实就是 比如这里行列式是，那么这个间隔就是

Kernal lattice 满足加法和整数数乘封闭，所以构成一个格

可以用sagemath求出核格

1
2
3
4
5
6
7
q = 7  # 示例模数
A = matrix(Zmod(q), [
    [1, 2, 3],
    [4, 5, 6]
])  # 示例矩阵，维度 2x3
kernel_mod_q = A.right_kernel_matrix()  # 计算模 q 的解空间基
print("模 q 的核基矩阵:\n", kernel_mod_q)

二、行列式是格基变换中的不变量

定义 1 幺模矩阵（unimodular matrix）是行列式绝对值为1的整数方阵。

Hermite 正规形（Hermite Normal Form, HNF）

定义

对于矩阵 ，若存在幺模矩阵（unimodular matrix）（即 ），使得：

则称 为 的行 Hermite 正规形，且满足以下条件：

  1. 上三角结构
  • 是上三角矩阵： 对所有 成立。
  • 所有零行必须位于非零行的下方。
  1. 主元性质
  • 非零行的主元（第一个非零元素 ）严格位于其上方行主元的右侧。
  • 主元必须为正：。
  1. 主元周边约束
  • 主元下方：（，由上三角性保证）。
  • 主元上方： 对所有 成立。

性质

  • 唯一性：给定 ，其 HNF 是唯一的。
  • 幺模变换： 是整数可逆矩阵，保持格的生成集不变。

这看着和高斯消元法好像也没什么区别？

HNF在格密码中有什么用呢，考虑两个格基B和C

显然他们可以由彼此线性表出，而且系数是整数 那么就得到 如果C是满秩的，就是满格，那UV=I,但是如果C只是列满秩的话，UV=I也是其中一个解

那么就有 因为V,U都是整数，根据行列式定义，他们的行列式也都是整数，而 则 所以U和V都是幺模矩阵

可以得到定理 是幺模矩阵 由于初等列变换的时候，行列式不变，所以初等列变换等价于右乘幺模矩阵

这就可以和Hermite normal from对应上了，我们把矩阵A化成Hermite normal form，其实就是进行一个格基的变换

这与高斯消元法不同，高斯消元法不能保证系数还是整数

三、Gram-Schmidt正交化

对格基进行正交化，那么有 其中 那么这样的话 就构成了一组格的正交向量，但一般不是基，显然这个会破坏原本的整数关系

但这个可以帮助我们计算行列式

我们思考一下，Gram-Schmidt之后，都是垂直的向量，那体积就很好算了，就是每个向量模长乘一起，那怎么证明这个体积和原来一样呢？

考虑QR分解 这里的Q是正交矩阵

而R则是对角线为的上三角矩阵

那么

还有一个不等式 下面证明 正定 证明： 对于任意由于列满秩，则只有零解，则对于任意 然后利用Hadamard不等式即可 实际上，直接根据正交化即可，正交化的模长不会比原来大(勾股定理)

四、最短向量问题

首先思考一个问题，如何判断一个区域内是否有格点？

这就用到了Minkowski-Lattice定理

Blichfeldt定理

如果一个多面体S,满足 则 数学水平还不足够证明，这里直接用形式化论证代替了

因为S比晶胞大，所以我们可以把S中的部分拆开平移，变成拼图，然后让S覆盖L，这样就能找到格向量了

但我们不能保证这个格向量在S内，因为这不是凸集

Minkowski-Lattice定理

设 是一个格，是一个关于原点对称的凸集。如果满足： 则包含至少一个非零格点

由于对称性，所以有一半体积其实作废了，所以要乘以

Minkowski第一定理

设是中秩为的格，为格中最短向量的长度那么

其实就是利用上面的定理构造一个凸集S

超立方体的体积 而对角线为 如果即可，然后以这个超立方体作为S的内切超立方体,S的半径就是

而最短向量又在s里

所以 当然这只是一个上界估计，存在性定理，并没有给出构造方法

最短向量问题(The Shortest Vector Problem, SVP)

寻找一个非零格向量，使得最小。

五、LLL算法

什么是LLL约化基

那么我们如何得到短向量呢，可以先从短的基开始，LLL规约基满足两个条件，一个是尽可能短，另一个是尽可能正交 一组基是约化的，如果 为什么这里是1/2呢，给出我的看法

我们希望通过GSO得到一组基，那这个基自然要在格里，回顾一下 为了让他们在格里，我们要保证这个μ是整数才行

如果那直接向下取整就行，那关键是的时候，这时候取整直接变成0了，等于没有GSO，所以我们要考虑加上1/2，这样在1/2,1之间的，还能进行，至于0到1/2的，那就是真的结束了

所以 那么第二个条件怎么理解呢，可以理解成 并不比短太多 从上面看，规约得到的向量应该越来越小，但是不能小太多，不然格会变得畸形

注意到和是正交的，所以上面也可以写成 于是又 我们一般情况下取

LLL算法

for i=1,2,..,n for j =i-1,..,1 :=

​ if

​ Then swap ,goto loop

​ Else output B

注意到这个类似于Gauss算法，所以属于格基变换，求得的还是格基

下面介绍一下LLL约化基的性质 左边前面已经证明了，考虑右边

令,于是有 而 于是 那么 于是 还有 注意到 则有 则 于是 同时，假设为格中最短向量的长度，那么有 于是有 所以我们可以用LLL算法求出近似度为的最短向量

六、CopperSmith方法

我们可以利用LLL算法来求解模多项式问题

比如我们想要求解 这个模多项式方程，这个是困难的，我们可以考虑构造整数上与之同解的方程，使得 我们知道当f(x)的系数比较小的时候，这个模多项式方程有可能变成多项式方程，这就可以考虑使用LLL算法求得约化基

注意到 而且同解，沿着这个思路 也是同解的，然后我们把h进行线性组合，寄希望与他们的系数可以相互抵消，使得系数绝对值变小

先考虑

引理Howgrave-Graham

设h(x)是一个有d个单项式的多项式，如果满足 那么，可以在整数集上求解

由 根据柯西不等式 而 那么

所以

根据上面这个，我们来构造 这个模数没统一，我们不妨固定为m吧，那这样的话，前面构造就得改 于是有 构造 只需令 那怎么找到这样的g呢

我们用的系数向量造格子

寻找满足的向量

不妨令LLL约化得到的b_1为这个向量，那么 只需令