格密码基础：对偶格（超全面）

2024-01-10 11:21:39

目录

一. 对偶格的格点

1.1 基本定义

1.2 对偶格的例子

1.3 对偶格的图形理解

二. 对偶格的格基

2.1 基本定义

2.2? 对偶格的格基证明

三. 对偶格的行列式

3.1 满秩格

3.2 非满秩格

四. 重复对偶格

五. 对偶格的转移定理（transference theorem）

六. 对偶格的连续最小值

七. 对偶格的正交投影

八. 对偶格基的正交化

推荐先阅读：

格密码的基础概念-CSDN博客

一. 对偶格的格点

1.1 基本定义

对偶格（dual lattice）也被称之为倒易格（reciprocal lattice）。原来满秩的格写做\Lambda，其对偶格的定义如下：

原来的格点和对偶格的任意（这两个字非常重要）格点相乘为整数即可。原来的格点如果为整数，那么对偶格里有可能会出现小数。此处y\in R^n代表n维实数空间，更准确来讲，对偶格应该在原来格的扩展空间内。那么对偶格更准确的定义，如下：

对偶格的右上角经常带“*”,span(\Lambda)代表格的扩展空间。

对偶格的重心在于，向量相乘为整数。当然，对偶格也是一种格，格的一些基本性质对偶格也具有。格和对偶格是成对出现的。

1.2 对偶格的例子

整数格的对偶格是其本身，也就是：

(Z^n)^*=Z^n

也就是整数格满足自对偶的性质。

如果把整数格的格点都扩大两倍，则形成子格。该格的对偶格则会出现小数，如下：

(2Z^n)^*=\frac{1}{2}Z^n

此处的系数有点类似倒数的感觉。

原始格的安全性在对偶格中依旧是存在的。

1.3 对偶格的图形理解

思考：给出任意一个向量点x，请找出所有跟这个向量点乘积为整数的点？

备注：向量与向量相乘为标量

线性代数告诉我们这些点会形成一个超平面，点跟点之间的距离为1/||x||。看一个二维的图形就很直接：

二. 对偶格的格基

格点相乘为整数，那这两个格的格基满足什么性质？

2.1 基本定义

原来的格基叫B，写做：

B=(b_1,\cdots,b_n)\in R^{m\times n}

格基内每个向量都是m维，一共有n个向量。

对偶格的格基维度肯定是保持不变的，也就是：

D=(d_1,\cdots,d_n)\in R^{m\times n}

对偶格和原来的格扩展空间肯定一致（向量点维度不一样的话，都不能相乘）：

span(D)=span(B)

刚才发现对偶格有点倒数的感觉，反应在矩阵上则互逆，所以满足：

B^TD=I

单位阵对角线上全为1，其他位置均为0。那么矩阵互逆告诉我们，向量位置一致时，相乘为1，也就是：

\langle b_i,d_j\rangle=\delta_{ij}=1\quad i=j

向量位置不一致时，相乘为0：

\langle b_i,d_j\rangle=\delta_{ij}=0\quad i\neq j

如果格基为方阵，也就是格满秩，则可以直接求逆，那么：

D=(B^T)^{-1}

如果格基非方阵，也就是格非满秩，那么可以利用伪逆：

D=B(B^TB)^{-1}

综合以上，对偶格的格基D需要满足两个性质：

?通过以上公式可以发现，只要B确定了，对偶格的格基D也是唯一确定的。

为什么格基满足如上性质，就可以是对偶格？请看2.2

2.2? 对偶格的格基证明

本质就是需要证明：

(L(B))^*=L(D)

借鉴集合相等的证明思路，我们的证明分成两步。

第一步：证明L(D)\subset(L(B))^*

从格L(B)内选取一个格点x，也就是x\in L(B)，将其写做整数倍的向量求和形式：

x=\sum a_ib_i\quad a_i\in Z

从格基D中随机抽取一个向量d_j，运算可得：

\langle x,d_j\rangle=\sum_i a_i\langle b_i,d_j\rangle=a_i\in Z

第一个等号：将格点x直接带入；

第二个等号：矩阵B与矩阵D互逆；

因为a_i一定为整数，这个时候说明格基D中的每一个列向量都可以算做一个对偶格的格点。格点的求和运算具有封闭性，继续对这些对偶格点进行整数组合也一定是对偶格点，所以可得：

L(D)\subset(L(B))^*

第二步：证明(L(B))^*\subset L(D)

从对偶格(L(B))^*内随机取一个格点y，也就是：

y\in (L(B))^*

根据对偶格的定义，易得：

y\in span(B)=span(D)

根据扩展空间的定义，那么就可以将该点写做：

y=\sum a_id_i\quad a_i\in R

将对偶格的格点和原格的某个格基向量相乘，可得:

\langle y,b_j\rangle=\sum_i a_i\langle d_i,b_j\rangle=a_j\in Z

所以可得：

y\in L(D)

综上第一步和第二步，证明完毕。

三. 对偶格的行列式

对偶格的行列式与原来格的行列式互为倒数，也就是：

det(\Lambda^*)=1/det(\Lambda)

证明：

3.1 满秩格

将格基先转置在求逆，即为对偶格，所以可得：

det(\Lambda^*)=|det((B^T)^{-1})|

逆矩阵的行列式与原矩阵的行列式互为倒数，所以可得：

det(\Lambda^*)=|det((B^T)^{-1})|=|\frac{1}{det(B^T)}|

矩阵转置不影响行列式的值，所以可得：

3.2 非满秩格

非满秩格不能直接求逆，则需要借助伪逆，运算性质与以上类似，可得：

四. 重复对偶格

对偶格的对偶，即为原格，也就是：

(\Lambda^*)^*=\Lambda

证明：

考虑一般情况。记原格\Lambda的格基为B，那么对偶格的格基为：

D=B(B^TB)^{-1}

继续对格L(D)求对偶格，也就是运算：

D(D^TD)^{-1}

带入运算可得：

五. 对偶格的转移定理（transference theorem）

本小节需要用到这篇博客的结论：

格密码与最短向量上界_最短向量问题-CSDN博客

假定格\Lambda的秩为n，对偶格的最短向量长度满足：

\lambda_1(\Lambda)\cdot \lambda_1(\Lambda^*)\leq n

证明：

首先根据闵可夫斯基上界（Minkowski's bound），可得：

将其类推到对偶格，可得：

两者相乘可得：

\lambda_1(\Lambda)\cdot \lambda_1(\Lambda^*)\leq n

备注：根据Banaszczyk定理，这个界可以继续被放缩，可得：

\lambda_1(\Lambda)\cdot \lambda_n(\Lambda^*)\leq n

六. 对偶格的连续最小值

本小节需要利用此篇博客的基础知识：

格密码基础：最短向量与连续最小值（附下界讨论）_格的逐次最小长度-CSDN博客

假定格\Lambda的秩为n，可得：

\lambda_1(\Lambda)\cdot \lambda_n(\Lambda^*)\geq 1

证明：

假定v为原来的格最短的向量点，也就是：

v\in \Lambda\quad ||v||=\lambda_1(\Lambda)

从对偶格\Lambda^*中取n个线性独立的向量：

x_1,\cdots,x_n

根据格点相乘为整数，可得：

\langle x_i,v\rangle \in Z

这两个向量的长度乘积必然大于1，也就是：

||x_i||\cdot ||v||\geq 1

\lambda_n(\Lambda^*)的长度一定比||x_i||要大，于是乎可得：

\lambda_1(\Lambda)\cdot \lambda_n(\Lambda^*)\geq 1

七. 对偶格的正交投影

对b_1,\cdots,b_n进行Gram-Schmidt正交化，可得：

\pi_1(b_1),\cdots,\pi_n(b_n)

其中\pi_i代表将向量投影到前i-1个正交平面上，也就是：

span(b_1,\cdots,b_{i-1})^\bot

假定B和D互为对偶格基。将矩阵B进行正交投影，可得：

B'=(\pi_i(b_i),\cdots,\pi_i(b_n))

此处就是把向量b_i,b_{i+1},\cdots,b_n往同一个正交平面进行投影。

该格基的对偶格基与原来保持不变，也就是

D'=(d_i,\cdots,d_n)

证明：

从扩展平面角度来讲，可得：

span(B')=span(b_1,\cdots,b_{i-1})^\bot

根据对偶格基的性质。d_i,\cdots,d_n与b_1,\cdots,b_{i-1}互相垂直，任意向量之间同样两两独立。换句话说，也就是：

span(D')=span(b_1,\cdots,b_{i-1})^\bot

所以可得：

span(B')=span(D')

满足对偶格基的第一个性质。

根据向量相乘的性质，不难计算：

根据逆矩阵的性质，不难证明原定理。

八. 对偶格基的正交化

原格基为：

b_1,\cdots,b_n

Gram-Schmidt正交化为：

\tilde{b}_1,\cdots,\tilde b_n

对偶格基：

d_1,\cdots,d_n

按反方向，Gram-Schmidt正交化为：

\tilde{d}_1,\cdots,\tilde d_n

长度满足：

证明：通过以上对偶格基长度讨论易得。也可以用归纳法：

文章来源:https://blog.csdn.net/forest_LL/article/details/135419407
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。