整理日期：2026-10-16。
前置笔记：01 格与格基、02 基本区域、格行列式与正交化、07 对偶格与对偶基。
设 \(q\ge2\) 为整数，
向量按列排列，长度使用欧氏范数。记 \(\widetilde A\in\mathbb Z^{n\times m}\) 为 \(A\) 的任意整数代表矩阵。
1. \(q\) 元格与两种矩阵表示#
满足
的格称为 \(q\) 元格（\(q\)-ary lattice）。
由于加入 \(q\) 的整数倍不改变成员关系，一个整数向量是否属于 \(\Lambda\)，完全由它模 \(q\) 后的剩余类决定。
给定矩阵 \(A\)，有两种常用构造。
模核格：由齐次模方程定义。
$$ \boxed{ \Lambda_q^\perp(A)#
{x\in\mathbb Z^m:Ax\equiv0\pmod q}. } $$
它包含所有满足模线性约束的整数向量，是模 \(q\) 核空间在整数空间中的全部提升。
模像格：由模 \(q\) 的行空间生成。
$$ \boxed{ \Lambda_q(A)#
\left{ x\in\mathbb Z^m: x\equiv A^{\mathsf T}s\pmod q \text{，某个 }s\in\mathbb Z_q^n \right}. } $$
等价地，
$$ \Lambda_q(A)#
\widetilde A^{\mathsf T}\mathbb Z^n + q\mathbb Z^m. $$
这里使用的是 \(A^{\mathsf T}\) 的像，也就是 \(A\) 的行向量在模 \(q\) 意义下生成的集合。加入 \(q\mathbb Z^m\)，才能得到所有整数提升。
两者都是 \(\mathbb Z^m\) 的加法子群，并且都包含 \(qe_1,\ldots,qe_m\)，因此都是 \(\mathbb R^m\) 中的满秩格。定义及满秩性见 Micciancio《Random Lattices and Lattice-Based Cryptography》，Fall 2019，§2，PDF 第 4 页。
需要区分：模核的有限域维数可以小于 \(m\)，但对应整数格的秩仍为 \(m\)。矩阵 \(A\) 描述模约束或模生成关系；实际的格基则是一个 \(m\times m\) 的整数矩阵。
2. 两类格的对偶关系#
它们满足
$$ \boxed{ \Lambda_q(A)^*#
\frac1q\Lambda_q^\perp(A), \qquad \bigl(\Lambda_q^\perp(A)\bigr)^*#
\frac1q\Lambda_q(A). } $$
这些等式对任意整数 \(q\ge2\) 成立。见 Micciancio–Regev《Lattice-based Cryptography》，2008-07-22 作者稿，§2，PDF 第 5 页。
证明可以直接使用像格的生成方式。向量 \(y\) 属于 \(\Lambda_q(A)^*\)，当且仅当它与所有生成向量的内积均为整数，即
令 \(x=qy\)，条件变为
因此 \(x\in\Lambda_q^\perp(A)\)，得到第一个等式。再使用双对偶与缩放性质，便得到第二个等式。
所以，\(\Lambda_q^\perp(A)\) 中的“\(\perp\)”表示模 \(q\) 正交；它与通常的对偶格之间存在因子 \(q\)，也不是实数空间中的正交补。
3. 行列式与模空间中的计数#
对任意 \(q\) 元格，\(\Lambda/q\mathbb Z^m\) 表示它包含的模 \(q\) 剩余类。由子群指数与基本区域体积的关系，
$$ \det(\Lambda)#
[\mathbb Z^m:\Lambda]#
\frac{q^m}{|\Lambda/q\mathbb Z^m|}. $$
因此，一个 \(q\) 周期内包含的剩余类越多，格的行列式越小。
现在进一步假设 \(q\) 为素数，并记
有限域线性代数给出
于是
特别地，当 \(A\) 满行秩，即 \(r=n\) 时，两者分别为 \(q^n\) 和 \(q^{m-n}\)。满行秩情形及其等价条件见 Micciancio，§2，PDF 第 5 页，Exercise 4。
两者的行列式乘积为 \(q^m\)，这也与上一节的缩放对偶关系一致。
4. 非齐次模方程对应格陪集#
考虑
若存在一个整数解 \(x_0\)，则全部整数解构成
$$ \boxed{ {x\in\mathbb Z^m:Ax\equiv u\pmod q}#
x_0+\Lambda_q^\perp(A). } $$
原因是
因此，齐次解集是格，非齐次解集在有解时是这个格的陪集。非零右端项对应的解集不含原点。
这也解释了短解问题的几何意义：
$$ \min_{Ax\equiv u;(\mathrm{mod};q)}|x|#
\min_{v\in\Lambda_q^\perp(A)}|x_0+v|#
\operatorname{dist}\bigl(-x_0,\Lambda_q^\perp(A)\bigr). $$
找到任意解只确定了一个陪集；找到其中的短解，需要进一步优化长度。这个联系也出现在 Micciancio，§2，PDF 第 6 页，Exercise 6 及其提示。
5. 从模矩阵写出一组格基#
假设 \(q\) 为素数且 \(A\) 满行秩。通过列重排和模 \(q\) 上的可逆行变换，可以将其化为
下面使用重排后的坐标，并将 \(C\) 取为整数代表矩阵。可逆行变换保持两类格不变，列重排对应格坐标的重排。
将 \(x\in\mathbb Z^m\) 分成两块 \(x=(u,v)\)，则
所以，模核格的一组列基为
$$ \boxed{ B_{\mathrm{ker}}#
\begin{pmatrix} qI_n&-C\ 0&I_{m-n} \end{pmatrix}. } $$
同理，由像格的定义可得到一组列基
$$ \boxed{ B_{\mathrm{img}}#
\begin{pmatrix} I_n&0\ C^{\mathsf T}&qI_{m-n} \end{pmatrix}. } $$
两组基满足
$$ B_{\mathrm{img}}^{\mathsf T}B_{\mathrm{ker}}#
qI_m, $$
直接体现了两类格之间的缩放对偶关系。这也是从模方程表示转为格基表示的一种显式构造。
6. 与 SIS、LWE 的衔接#
SIS：在模核格中寻找短的非零向量。
其核心约束为
长度限制至关重要：若只要求非零解，\(qe_i\) 总是现成的解。SIS 的正式定义还需要指定随机矩阵的分布和参数范围，下一篇再展开。见 Micciancio，PDF 第 1 页，Definition 1。
LWE：观察模像格中的格点受到小误差扰动后的结果。
其整数误差形式写为
其中 \(s\in\mathbb Z_q^n\)，\(e\in\mathbb Z^m\) 是较短的误差向量。取 \(b\) 的整数代表 \(\widetilde b\)，则
因此，带噪模线性方程可以解释为：给定一个靠近模像格的点，尝试恢复其背后的格点或秘密。其样本分布、搜索版与判定版将在第十四篇中明确。见 Micciancio，PDF 第 1 页，Definition 2 及其后的分布说明；第 4 页的格解释。