For AI agents: the complete documentation index is available at https://shijin.space/llms.txt, the full documentation bundle is available at https://shijin.space/llms-full.txt, and this page is available as Markdown at https://shijin.space/knowledge/lattices-and-bases/index.md.
ShiJin

    01 格与格基

    适用范围：计算格与格密码的基础知识。整理日期：2026-09-26。

    格与格基

    设 B=[b1,…,bn]∈Rm×nB=[b_1,\ldots,b_n]\in\mathbb R^{m\times n} 的列向量线性无关，则

    L(B)={Bz:z∈Zn}\mathcal L(B)=\{Bz:z\in\mathbb Z^n\}

    称为由 BB 生成的格，BB 是该格的一组基。格是点集，格基是生成它的一种表示。

    • nn 为格的秩，mm 为环境维数；n=mn=m 时称为满秩格。
    • 整数限制针对组合系数，基向量和格点的坐标不必为整数。
    • 线性空间 span⁡(B)={Bx:x∈Rn}\operatorname{span}(B)=\{Bx:x\in\mathbb R^n\} 允许实数系数，格只允许整数系数。
    • 基向量线性无关，因此每个格点在给定基下的整数坐标唯一。

    不同资料对“维数”的用法不一致，本文统一区分“秩”与“环境维数”。[1，定义 1—2；2，定义 1 及脚注 2]

    等价格基与换基

    同一个格可以有不同的基。对列满秩矩阵 B,B′∈Rm×nB,B'\in\mathbb R^{m\times n}，

    L(B′)=L(B)  ⟺  B′=BU,U∈Zn×n,det⁡U=±1.\mathcal L(B')=\mathcal L(B) \iff B'=BU,\quad U\in\mathbb Z^{n\times n},\quad \det U=\pm1.

    这样的整数矩阵 UU 称为幺模矩阵，其逆矩阵仍为整数矩阵。因此新旧基能相互通过整数线性组合得到，生成的格不变。[1，定义 4、引理 2—3；2，定理 3、推论 10]

    在列向量作为基的约定下，以下操作保持格不变：

    1. 交换两个基向量。
    2. 将一个基向量取反。
    3. bi←bi+kbjb_i\leftarrow b_i+k b_j，其中 k∈Zk\in\mathbb Z、i≠ji\ne j。

    任意两组等价格基都可以通过上述操作相互转换。后续格基约化正是在保持格不变的前提下，改善基向量的性质。[1，引理 4；2，第 2 节]

    一个必要的辨析

    张成相同的实线性空间，不代表生成相同的格。

    例如，I2I_2 与 diag⁡(2,1)\operatorname{diag}(2,1) 都张成 R2\mathbb R^2，但分别生成 Z2\mathbb Z^2 与 2Z×Z2\mathbb Z\times\mathbb Z。后者无法通过整数系数生成 (1,0)T(1,0)^T。

    因此，一组向量即使线性无关且属于某个给定格，也未必是该格的基；还需要能够生成该格的全部点。

    来源

    1. Oded Regev，Lattices in Computer Science，Lecture 1: Introduction，Fall 2004，第 1 页定义 1—2、第 3 页定义 4 与引理 2—3、第 3—4 页引理 4。原文
    2. Daniele Micciancio，Point Lattices，PDF 页首标注 Fall 2017，由 2019 年课程页链接。PDF 第 2 页定义 1 与脚注 2、第 4 页定理 3、第 5 页基本列操作、第 7—8 页推论 10。原文

    两份来源于 2026-09-26 核对；正文按已确认的内容精简，矩阵反例为整理时的直接计算。

    引用此笔记