格密码入门

发表于 2026/05/23 更新于 2026/05/31

作者 youzi

5 分钟阅读

格密码入门

一、前置知识

1. n维向量空间

n维向量的内积：设 $\mathbb{R}$ 是实数集，$\mathbb{R}^m$ 为 $m$ 维欧氏空间，里面的向量用列向量表示，定义内积为 $\langle , \rangle : \mathbb{R}^m \times \mathbb{R}^m \to \mathbb{R}$ $\langle x,y \rangle \to x^Ty$
n维向量的范数(长度)：对 $\forall x \in \mathbb{R}^m,\quad |\mathbf{x}|=\sqrt{x^Tx}$

2. Gram-Schmidt正交化

施密特正交化从欧氏空间任意线性无关的向量组 $\alpha_1 ,\alpha_2,…,\alpha_n$ 出发，求得与之等价的正交向量组$\beta_1 ,\beta_2,…,\beta_n$. 具体算法过程如下：

代码实现：

  
import numpy as np

def schmidt_orthogonalize(vectors):
    """
    输入：dim*n的矩阵，每一列是一个输入向量
    输出：正交化后的列向量矩阵
    """
    dim, n = vectors.shape  # 获取维数和向量个数
    orthogonal = np.zeros_like(vectors, dtype=np.float64)  # 存储正交向量
    
    # 第一个向量直接复制
    orthogonal[:, 0] = vectors[:, 0]
    
    # 从第二个向量开始迭代
    for k in range(1, n):
        alpha_k = vectors[:, k]
        beta_k = alpha_k.copy()
        
        # 减去之前所有正交向量的投影
        for i in range(k):
            beta_i = orthogonal[:, i]
            inner_product = np.dot(alpha_k, beta_i)
            norm_sq = np.dot(beta_i, beta_i)
            beta_k -= (inner_product / norm_sq) * beta_i
        
        orthogonal[:, k] = beta_k
    
    return orthogonal

3.一些定义

n维体积：n维欧氏空间中，由n个向量张成的图形的体积定义为 $vol(v_1,v_2,...,v_n)=det(V),\; V=(v_1,v_2,...,v_n)$ 其中 vol( ) 为体积函数
离散：如果对于任何实数 $r>0$，集合 ${ v\in L:\lVert v \rVert\leq r}$ 是有限的，则子集$L\in \mathbb{R}^{m}$ 被称为离散

二.格的基本概念

1.格的定义

设 ${b_{1},b_{2},\dots,b_{n}}$ 是 $\mathbb{R}^{m}$ 中$n$个线性无关的向量（$m\geq n$）, $\mathbb{Z}$ 为整数集，称 $L=\left\{ \sum_{i=1}^{n} x_{i}b_{i}:x_{i}\in \mathbb{Z} \right\}$ 为 $\mathbb{R}^{m}$ 中的一个格。简单来说，格是m维欧氏空间的一个子集，一组基向量通过整系数线性组合生成了格中的所有元素。

[!info] 由于欧氏空间中的点和向量存在一一对应关系，所以格中的元素也可称为格点

现在给出格的等价定义：格是 $\mathbb{R}^{m}$ 的离散子群。并且可以证明，m维欧氏空间的离散子群都是格。

2.基，维数，秩与行列式

生成格的实数向量组叫做格的基，也可以称这个向量组构成的矩阵为格基。在密码学中，我们常用到的格基都为整。

我们定义格基向量的维数就为格的维数。

定义格基的秩就为格的秩，由于格基线性无关，所以格的秩为格基中向量个数。格的秩小于等于格的维数，当格的秩等于格的维数时，称为满秩格。

格 $L$ 的行列式是它的任意格基 $B$ 的基本平行六面体的体积，当格满秩时，有

$\det(L)=|\det(B) |$ 当格的秩 $n<m$ 时，定义格的行列式为

\[\det(L)=|\det(B^{T}B) |\]

显然这是一个n阶矩阵的行列式。

定理：假设 $L\in \mathbb{Z}^{m\times n}$ 是 $n$ 阶格，它可由 $B,B^{‘}$ 格基生成当且仅当存在 $U$ ,使 $B^{‘}=UB$ ,其中 $\det(U)=\pm1$ ,即 $U$ 为幺模矩阵。

简单的说，对格基做初等行变换，生成的格不变。因此，格的行列式与格基的选择无关。

可见对于给定的格，有许多不同的格基选择。通常，我们希望选取一组短且正交的格基。

对于二维格，有：$\det(L)=\lvert \lvert b_{1} \rvert \rvert \ \ \lvert \lvert b_{2} \rvert \rvert\sin(\theta)$ 。显然，由于行列式一定，格基越正交就会越短。

对于高维情况，也有上述的类似结论（Hadamard 不等式）

本文由作者按照 CC BY 4.0 进行授权

目录