格密码--数学基础--02基变换、幺模矩阵与 Hermite 标准形

02基变换、幺模矩阵与 Hermite 标准形

一、格的基变换与幺模矩阵

1. 基变换关系

格的两个基 $\mathbf{B},\mathbf{C}\in {\mathbb{R}}^{n\times n}$ 可通过幺模矩阵转换：
若 $\mathcal{L}(\mathbf{B})=\mathcal{L}(\mathbf{C})$（生成同一格），则存在幺模矩阵 $\mathbf{U}\in {\mathbb{R}}^{n\times n}$ （过渡矩阵的特殊情况）满足：
$$\mathbf{C}=\mathbf{BU}\text{或}\mathbf{B}=\mathbf{CV}$$
且行列式满足 $|\det (\mathbf{U})|=1$。

2. 幺模矩阵的定义与性质

• 定义：

  幺模矩阵是行列式绝对值为 1 的整数方阵：
  $$\mathbf{U}\in {\mathbb{Z}}^{n\times n}\text{且}|\det (\mathbf{U})|=1$$

• 性质：

  1. 幺模矩阵的逆矩阵仍是幺模矩阵
  2. 幺模矩阵的乘积仍是幺模矩阵

3. 格相等的充要条件

两个基生成的格相等当且仅当：
$$\mathcal{L}(\mathbf{B})=\mathcal{L}(\mathbf{C})⟺\exists \text{幺模矩阵}\mathbf{U}\text{使得}\mathbf{B}=\mathbf{CU}$$
证明：

二、初等变换与幺模矩阵的等价性

1. 初等列变换的定义

包括三种基本操作：

1. 交换两列
2. 某一列乘以 $\pm 1$
3. 某一列加上另一列的整数倍

2. 性质

• 初等列变换不改变行列式的绝对值
• 幺模矩阵经初等列变换后仍为幺模矩阵

3. 等价性

幺模矩阵等价于一系列整数初等列变换的组合：
$$\text{幺模矩阵}⟺\text{初等列变换的乘积}$$
这类变换保持整数格点集 ${\mathbb{Z}}^n$ 不变且可逆。

三、Hermite 标准形（HNF）

1. 定义

矩阵 $\mathbf{H}\in {\mathbb{Z}}^{n\times n}$ 为 HNF 当且仅当满足：

1. 上三角结构：$h_{ij}=0$ 若 $i>j$

2. $h_{ii}>0$

3. $0\le h_{ij}<h_{ii}$（对 $i<j$）
   $$\mathbf{H}=\left(\begin{array}{ccccc}{h}_{11}& h_{12}& h_{13}& \cdots & h_{1n}\\ 0& h_{22}& h_{23}& \cdots & h_{2n}\\ 0& 0& h_{33}& \cdots & h_{3n}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& 0& 0& \cdots & h_{nn}\end{array}\right)$$

2. 定理

对任意非奇异整数矩阵 $\mathbf{B}\in {\mathbb{Z}}^{n\times n}$：存在唯一幺模矩阵 $\mathbf{U}$ 使得：
$$\mathbf{B}\cdot \mathbf{U}=\mathbf{H}$$
其中 $\mathbf{H}$ 为 HNF

3.HNF求解

定理：（HNF的构造核心）

行向量 $\mathbf{v}=[v_1,v_2,\dots ,v_n]$ 可以通过一系列初等列变换变形为 $[0,0,\dots ,\gcd (v_1,v_2,\dots ,v_n)]$。

构造过程

此时已经保证了HNF的（1和2）两个条件

最后再通过对角元素进行化约（对角元的负数倍加上右侧比对角元大的元素，进行化约）从而满足条件三构造HNF

四、HNF 的作用

1. 判断格等价充要条件

两个矩阵生成同一格当且仅当它们的 HNF 相同：
$$\mathcal{L}({\mathbf{B}}_1)=\mathcal{L}({\mathbf{B}}_2)⟺\mathrm{HNF}({\mathbf{B}}_1)=\mathrm{HNF}({\mathbf{B}}_2)$$

2. 判断向量属格充要条件

向量 $\mathbf{v}\in \mathcal{L}(\mathbf{B})$ 当且仅当：
$$\exists \mathbf{x}\in {\mathbb{Z}}^n\text{使得}\mathbf{v}=\mathbf{H}\cdot \mathbf{x}$$
因 HNF 是上三角矩阵，可通过回代法快速求解。(先解第n个方程，结果带入解答第n-1个方程，依次往上带入，利用的就是$\mathbf{H}$上三角的性质)

3.HNF 是格的==“唯一指纹”==

每个格有唯一的 HNF 基，提供了标准化的格表示形式

4.计算复杂性警示

输入矩阵元素和范数即使很小，例如为多项式级时（如元素取自 {−1,0,1}\{-1, 0, 1\}{−1,0,1}，列范数 $\le \sqrt{n}$)，但是HNF 的列范数（欧几里得范数）可能指数级增长：$\Vert {\mathbf{h}}_{\mathbf{i}}{\Vert }_2=2^{\Omega (n)}$，即输出规模可能远大于输入