# 12 q 元格与模线性方程

整理日期：2026-10-16。  
前置笔记：[01 格与格基](/knowledge/lattices-and-bases/)、[02 基本区域、格行列式与正交化](/knowledge/fundamental-region-and-orthogonalization/)、[07 对偶格与对偶基](/knowledge/dual-lattices/)。

设 $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 页](https://cseweb.ucsd.edu/classes/fa19/cse206A-a/Lec4-Random.pdf)。

需要区分：模核的有限域维数可以小于 $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 页](https://cims.nyu.edu/~regev/papers/pqc.pdf)。

证明可以直接使用像格的生成方式。向量 $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](https://cseweb.ucsd.edu/classes/fa19/cse206A-a/Lec4-Random.pdf)。

两者的行列式乘积为 $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 及其提示](https://cseweb.ucsd.edu/classes/fa19/cse206A-a/Lec4-Random.pdf)。

## 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](https://cseweb.ucsd.edu/classes/fa19/cse206A-a/Lec4-Random.pdf)。

**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 页的格解释](https://cseweb.ucsd.edu/classes/fa19/cse206A-a/Lec4-Random.pdf)。

## 引用此笔记

- [00 概览与阅读路线](/knowledge/lattices-overview/)
- [13 SIS 问题与短整数关系](/knowledge/sis-and-short-integer-relations/)
- [14 LWE 问题与带噪线性方程](/knowledge/lwe-and-noisy-linear-equations/)