当前位置: 首页 > news >正文

格密码基础:对偶格(超全面)

目录

一. 对偶格的格点

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_nb_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

长度满足:

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

相关文章:

格密码基础:对偶格(超全面)

目录 一. 对偶格的格点 1.1 基本定义 1.2 对偶格的例子 1.3 对偶格的图形理解 二. 对偶格的格基 2.1 基本定义 2.2 对偶格的格基证明 三. 对偶格的行列式 3.1 满秩格 3.2 非满秩格 四. 重复对偶格 五. 对偶格的转移定理(transference theorem&#xff…...

ECMAScript简介及特性

ECMAScript是一种由ECMA国际(前身为欧洲计算机制造商协会)制定和发布的脚本语言规范,JavaScript在它基础上进行了自己的封装。ECMAScript和JavaScript的关系是,前者是后者的规格,后者是前者的一种实现。 ECMAScript的…...

csdn中的资源文件如何删除?

csdn中的资源文件如何删除? 然后写文章的时候 点击资源绑定,解锁资源,就可以再次上传。...

NA原理及配置

在IP地址空间中,a;b;c类地址中各有一部分地址,被称为私有IP地址(私网地址),其余的为公有IP地址(公网地址) A:10.0.0.0 - 10.255.255.255 --- 相当于1条A类网段…...

解决:TypeError: ‘tuple’ object does not support item assignment

解决:TypeError: ‘tuple’ object does not support item assignment 文章目录 解决:TypeError: tuple object does not support item assignment背景报错问题报错翻译报错位置代码报错原因解决方法方法一:方法二:今天的分享就到…...

vue3项目中axios的常见用法和封装拦截(详细解释)

1、axios的简单介绍 Axios是一个基于Promise的HTTP客户端库,用于浏览器和Node.js环境中发送HTTP请求。它提供了一种简单、易用且功能丰富的方式来与后端服务器进行通信。能够发送常见的HTTP请求,并获得服务端返回的数据。 此外,Axios还提供…...

基础语法(一)(1)

常量和表达式 在这里,我们可以把Python当成一个计算器,来进行一些算术运算 例如: print(1 2 - 3) print(1 2 * 3) print(1 2 / 3)注意: print是一个python内置的函数,这个稍后我们会进行介绍 可以使用-*/&…...

YOLOv8模型yaml结构图理解(逐层分析)

前言 YOLO-V8(官网地址):https://github.com/ultralytics/ultralytics 一、yolov8配置yaml文件 YOLOv8的配置文件定义了模型的关键参数和结构,包括类别数、模型尺寸、骨架(backbone)和头部(hea…...

【大数据】Zookeeper 集群及其选举机制

Zookeeper 集群及其选举机制 1.安装 Zookeeper 集群2.如何选取 Leader 1.安装 Zookeeper 集群 我们之前说了,Zookeeper 集群是由一个领导者(Leader)和多个追随者(Follower)组成,但这个领导者是怎么选出来的…...

Redis 过期策略

我们在set key的时候可以设置key的过期时间,哪redis是怎么处理过期的key的呢? 有三种过期策略 定时过期:每个设置过期时间的key会创建一个定时器,到过期时间就会立即对key进行清除。该策略可以立即清除过期的数据,对…...

RT_Thread 调试笔记:串口打印、MSH控制台 相关

说明:记录日常使用 RT_Thread 开发时做的笔记。 持续更新中,欢迎收藏。 1.打印相关 1.打印宏定义,可以打印打印所在文件,函数,行数。 #define PRINT_TRACE() printf("-------%s:%s:%d------\r\n", __FIL…...

(适趣AI)Vue笔试题

📑前言 本文主要是【Vue】——(适趣AI)Vue笔试题的文章,如果有什么需要改进的地方还请大佬指出⛺️ 🎬作者简介:大家好,我是听风与他🥇 ☁️博客首页:CSDN主页听风与他 …...

Matytype的安装问题(word及PPT报错问题)

特别针对:mathtype安装了多次,又卸载了多次的用户。 Word报弹错错误:参考 mathtype安装后,打开word出现没找到dll的错误,这个问题较好解决。 如何解决MathType兼容Office 2016-MathType中文网 PPT(PowerPoi…...

docker拉取镜像提示 remote trust data does not exist for xxxxxx

1、How can I be sure that I am pulling a trusted image from docker 2、docker: you are not authorized to perform this operation: server returned 401. 以上两个问题可以试试以下解决办法 DOCKER_CONTENT_TRUSTfalse 本人是使用jenkins部署自己的项目到docker容器出现…...

ElasticSearch Nested类型全文检索、聚合查询

ElasticSearch Nested类型全文检索、聚合查询 Nested类型全文检索 创建索引 PUT /products1 {"mappings": {"properties": {"fulltext": {"type": "text"},"name": {"type": "text","…...

专业级的渗透测试服务,助力航空业数字化安全启航

​某知名航空公司是中国首批民营航空公司之一,运营国内外航线200多条,也是国内民航最高客座率的航空公司之一。在数字化发展中,该航空公司以数据驱动决策,通过精细化管理、数字创新和模式优化等方式,实现了精准营销和个…...

【docker】安装 Redis

查看可用的 redis版本 docker search redis拉取 redis最新镜像 docker pull redis:latest查看本地镜像 docker images创建挂在文件 mkdir -pv /test1/docker_volume/redis/datamkdir -pv /test1/docker_volume/redis/confcd /test1/docker_volume/redis/conf/touch redis.con…...

pinia的独立维护,统一导出及持久化

目录 1.说明及示例 2.注意 1.说明及示例 在src下创建store文件夹,在store文件夹下创建index.js文件,内容如下: import { createPinia } from "pinia"; // pinia的持久化 import piniaPluginPersistedstate from "pinia-pl…...

【AI视野·今日Robot 机器人论文速览 第六十七期】Mon, 1 Jan 2024

AI视野今日CS.Robotics 机器人学论文速览 Mon, 1 Jan 2024 Totally 16 papers 👉上期速览✈更多精彩请移步主页 Daily Robotics Papers MURP: Multi-Agent Ultra-Wideband Relative Pose Estimation with Constrained Communications in 3D Environments Authors A…...

FBL刷写

刷写 1、刷写需求的理解2、刷写流程2.1、预编程阶段:保证在编程阶段的动作能够正常操作,控制器给响应。整车功能不会出现问题 刷写某一控制器时,避免其他控制器集DTC,85控制DTC; 28 通信控制.保证总线负载率不要过高(下…...

华为云AI开发平台ModelArts

华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架,相比 MapReduce 具有以下核心优势: 内存计算:数据可常驻内存,迭代计算性能提升 10-100 倍(文档段落:3-79…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

【2025年】解决Burpsuite抓不到https包的问题

环境:windows11 burpsuite:2025.5 在抓取https网站时,burpsuite抓取不到https数据包,只显示: 解决该问题只需如下三个步骤: 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX(不访问内存)XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...

AspectJ 在 Android 中的完整使用指南

一、环境配置(Gradle 7.0 适配) 1. 项目级 build.gradle // 注意:沪江插件已停更,推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...