理论基础

格理论的起源可以追溯到 17 世纪有关球堆积问题的研究，直至 1840 年，高
斯才引入格在几何中的概念并给出了三维空间中球的最大堆积密度。格在群论和几何中的定义不同于离散数学中有关偏序集合的描述，几何上，可以将格看作是具有周期性结构的 n 维空间中的点的集合。
Shamir最早将格理论引入密码学领域，其在 1982 年利用格对背包公钥密码体制进行了攻击，后来 Coppersmith对其分析方法做了推广，将破解 RSA 公钥密码体制的问题转化成了求格中的困难问题。近些年，随着对格理论中有关计算性难题的研究，人们发现其在数论、计算机科学、密码分析和设计中都有着很*
广泛的应用前景。

格的定义

设b1,b2,...,bn∈Rmb_1,b_2,...,b_n\in \mathbb{R}^m一组线性无关的向量，其产生的格被定义为

L(b1,b2,...,bn)={Σi=1nxibi∣xi∈Z}L(b_1,b_2,...,b_n) = \{ \Sigma^n_{i=1}x_ib_i|x_i\in\mathbb{Z}\}

​ 简记为L，m为格L的维数，n为格L的秩，通常研究满秩格，即m=n。称B={b1,b2,..,bn}B=\{b_1,b_2,..,b_n\}为一组格基，同一个格L可以由不同的格基来表示。

image-20240428214624348

​ 上图展示了由基向量{b0,b1}\{b_0,b_1\}或{v0,v1}\{v_0,v_1\}生成的二维格。

​ 在给定格L中的任意一组基向量，将其以行向量的形式表达为矩阵A，通过对A左乘一个幺模矩阵U≠IU\neq I（如果A∈Rm×nA \in R ^{m\times n}是整数矩阵，r=rank(A)=min{m,n}而且A的所有非零rxr子式等于1或-1，则称A为幺模矩阵）得到矩阵UA，UA的行向量则表示格L的另外一组基。

​ 一般来说，如果一组基向量几乎是正交的，那么认为它是好的基向量，否则认为是坏的。如上图，{b0,b1}\{b_0,b_1\}是一组好的基向量，{v0,v1}\{v_0,v_1\}是一组坏的基向量，基向量正交的程度直接影响解决格问题的复杂程度。

格的延展空间

设n维格L(B),其基向量B的所有线性组合形成的集合

span(B)={Bx∣x∈Rn}span(B) = \{Bx|x\in \mathbb{R}^n \}

称为这组基向量的延展空间

格的延展空间为整个n维空间的前提是为满秩格

格的基本空间

设n维格L(B),以下向量的集合

P(B)={Bx∣x∈Rn,∀i:0≤xi≤1}P(B) = \{Bx|x\in\mathbb{R}^n,\forall i:0\le x_i\le1\}

称为格L的一个基础区域。

image-20240428221226121