12 q 元格与模线性方程#

整理日期：2026-10-16。
前置笔记：01 格与格基、02 基本区域、格行列式与正交化、07 对偶格与对偶基。

设 $q\ge2$ 为整数，

$$\mathbb Z_q=\mathbb Z/q\mathbb Z, \qquad A\in\mathbb Z_q^{n\times m}, \qquad n\le m.$$

向量按列排列，长度使用欧氏范数。记 $\widetilde A\in\mathbb Z^{n\times m}$ 为 $A$ 的任意整数代表矩阵。

#1. $q$ 元格与两种矩阵表示

满足

$$\boxed{ q\mathbb Z^m\subseteq\Lambda\subseteq\mathbb Z^m }$$

的格称为 $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)^*$，当且仅当它与所有生成向量的内积均为整数，即

$$qy\in\mathbb Z^m, \qquad \widetilde A y\in\mathbb Z^n.$$

令 $x=qy$，条件变为

$$x\in\mathbb Z^m, \qquad \widetilde A x\in q\mathbb Z^n.$$

因此 $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$ 为素数，并记

$$r=\operatorname{rank}_{\mathbb Z_q}(A).$$

有限域线性代数给出

$$|\ker A|=q^{m-r}, \qquad |\operatorname{im}A^{\mathsf T}|=q^r.$$

于是

$$\boxed{ \det\bigl(\Lambda_q^\perp(A)\bigr)=q^r, \qquad \det\bigl(\Lambda_q(A)\bigr)=q^{m-r}. }$$

特别地，当 $A$ 满行秩，即 $r=n$ 时，两者分别为 $q^n$ 和 $q^{m-n}$。满行秩情形及其等价条件见 Micciancio，§2，PDF 第 5 页，Exercise 4。

两者的行列式乘积为 $q^m$，这也与上一节的缩放对偶关系一致。

#4. 非齐次模方程对应格陪集

考虑

$$Ax\equiv u\pmod q, \qquad u\in\mathbb Z_q^n.$$

若存在一个整数解 $x_0$，则全部整数解构成

$$\boxed{ \{x\in\mathbb Z^m:Ax\equiv u\pmod q\} = x_0+\Lambda_q^\perp(A). }$$

原因是

$$Ax\equiv u \iff A(x-x_0)\equiv0 \pmod q.$$

因此，齐次解集是格，非齐次解集在有解时是这个格的陪集。非零右端项对应的解集不含原点。

这也解释了短解问题的几何意义：

$$\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$ 上的可逆行变换，可以将其化为

$$A=\begin{pmatrix}I_n&C\end{pmatrix}.$$

下面使用重排后的坐标，并将 $C$ 取为整数代表矩阵。可逆行变换保持两类格不变，列重排对应格坐标的重排。

将 $x\in\mathbb Z^m$ 分成两块 $x=(u,v)$，则

$$Ax\equiv0\pmod q \iff u+Cv\equiv0\pmod q \iff u=-Cv+qz, \qquad z\in\mathbb Z^n.$$

所以，模核格的一组列基为

$$\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：在模核格中寻找短的非零向量。

其核心约束为

$$x\in\Lambda_q^\perp(A)\setminus\{0\}, \qquad \|x\|\le\beta.$$

长度限制至关重要：若只要求非零解，$qe_i$ 总是现成的解。SIS 的正式定义还需要指定随机矩阵的分布和参数范围，下一篇再展开。见 Micciancio，PDF 第 1 页，Definition 1。

LWE：观察模像格中的格点受到小误差扰动后的结果。

其整数误差形式写为

$$b\equiv A^{\mathsf T}s+e\pmod q,$$

其中 $s\in\mathbb Z_q^n$，$e\in\mathbb Z^m$ 是较短的误差向量。取 $b$ 的整数代表 $\widetilde b$，则

$$\widetilde b-e\in\Lambda_q(A), \qquad \operatorname{dist}\bigl(\widetilde b,\Lambda_q(A)\bigr) \le\|e\|.$$

因此，带噪模线性方程可以解释为：给定一个靠近模像格的点，尝试恢复其背后的格点或秘密。其样本分布、搜索版与判定版将在第十四篇中明确。见 Micciancio，PDF 第 1 页，Definition 2 及其后的分布说明；第 4 页的格解释。

#引用此笔记

• 00 概览与阅读路线
• 13 SIS 问题与短整数关系
• 14 LWE 问题与带噪线性方程