格密码:傅里叶矩阵
目录
一. 铺垫性介绍
1.1 傅里叶级数
1.2 傅里叶矩阵的来源
二. 格基与傅里叶矩阵
2.1 傅里叶矩阵详细解释
2.2 格基与傅里叶矩阵
写在前面:有关傅里叶变换的解释太多了,这篇博客主要总结傅里叶矩阵在格密码中的运用。对于有一定傅里叶变换基础的同学,可直接跳转2.2看结论。
一. 铺垫性介绍
1.1 傅里叶级数
傅里叶级数的表达如下:
傅里叶级数可以看成无限维度的线性代数。这个过程可以看成将函数f(x)投影成很多的sin与cos,与此同时产生傅里叶系数与
.
反过来,借助无限的sin与cos序列,乘以对应的傅里叶系数,也能够重建原始的函数f(x)。
当然,格密码中我们更加关心有限维度的离散傅里叶变换。
1.2 傅里叶矩阵的来源
将傅里叶级数右边的函数改为输入n个值,由此输出n个值
。这两个向量,y与c之间的关系一定是线性的,数字信号处理过程中也经常会用到此性质。既然是线性关系,那我们可以将其构建为一个矩阵,由此便出现了傅里叶矩阵F。比如,给定输出y有四个值2,4,6,8,求解输入c的本质就是:已知Fc=y,求解c,如下:
二. 格基与傅里叶矩阵
2.1 傅里叶矩阵详细解释
先从4维的离散傅里叶矩阵(后续记为DFT)F说起:
离散傅里叶矩阵的共轭矩阵记为,熟悉线性代数的都知道,DFT矩阵满足如下:
排除系数4的影响,也就是矩阵乘以本身的共轭矩阵为单位阵,这不就类似正交阵(准确来讲应该叫酉矩阵)。
给定任意的维度n,傅里叶矩阵可以将输入c与输出y联系起来。这个过程可以写成n个线性方程,当然也可以写成离散级数,包含n个傅里叶系数,n个输出点,如下:
当x取0时,也就是系数全为1,第一个线性方程往往比较简单,如下:
将1的N次方根主值记为,其实就是复数根,以上变换过程推广到n维为:
注意左边第一个矩阵即为傅里叶矩阵。将行数与列数记为从0到n-1,傅里叶矩阵中的元素可以总结为。比如第一行就是
,第一列就是
,这两个的元素均为
。
在利用傅里叶矩阵时,很多时候需要求逆。根据复数的性质,易知:
我们知道的角度为
,
的角度为
,类似如下:
也就是可以得出:
也就是傅里叶矩阵的逆长这个样子:
第一个等号代表,傅里叶矩阵的逆。第二个等号代表逆矩阵与共轭矩阵的关系。
如果用3维举例子的话,三维的傅里叶矩阵如下:
三维的逆傅里叶矩阵如下:
F的第j行,的第j列,相乘计算:
其实就是单位阵的对角线元素。
F的第j行乘以的第k列,计算:
除了对角线元素,其他位置均为0(单位阵)。
如果我们将,以上方程即可改写为:
因为,W满足如下:
也就是W也为1的单位根。
2.2 格基与傅里叶矩阵
格基的本质是一个矩阵,通常格点为实数的向量点。如果将其推广到复数域,格基B也可以取复数。
根据以上讨论,傅里叶矩阵:
- N维方阵;
- 对称矩阵(关于对角线);
- 正交阵(注意差N倍系数,严格叫酉矩阵);
已经出现论文讨论将傅里叶矩阵作为格基,之所以这样是有如下好处:
- 格基为正交阵,格基良好,可解决很多格上困难问题(CVP,LWE等);
- 逆矩阵容易求,很容易导出对偶格;
格密码中很多时候需要利用“环版本”,比如RLWE或者Ring-SIS问题。一个环元素本质是一个多项式,两个多项式相乘的计算复杂度为,但如果借助快速傅里叶变换(FFT),其复杂度可以降低到
。
相关文章:
格密码:傅里叶矩阵
目录 一. 铺垫性介绍 1.1 傅里叶级数 1.2 傅里叶矩阵的来源 二. 格基与傅里叶矩阵 2.1 傅里叶矩阵详细解释 2.2 格基与傅里叶矩阵 写在前面:有关傅里叶变换的解释太多了,这篇博客主要总结傅里叶矩阵在格密码中的运用。对于有一定傅里叶变换基础的同…...

flex--伸缩性
1.flex-basis flex-basis 设置的是主轴方向的基准长度,会让宽度或高度失效。 备注:主轴横向:宽度失效;主轴纵向:高度失效 作用:浏览器根据这个属性设置的值,计算主轴上是否有多余空间&#x…...

linux中主从复制的架构和读写分离的方式
读写分离 互相主从架构注意点 双主双从架构注意点 一主多从架构注意点 读写分离概念部署jdk环境上传文件,解压文件配置环境变量 部署mycat环境mycat配置文件给所有数据库创建访问用户配置 server.xml配置 schema.xml启动mycat查看启动端口日志负载均衡测试 遇到的问…...

Ubuntu 22.04.3 Server 设置静态IP 通过修改yaml配置文件方法
目录 1.查看网卡信息 2.修改yaml配置文件 3.应用新的网络配置 4.重新启动网络服务 文章内容 本文介绍Ubuntu 22.04.3 Server系统通过修改yaml配置文件配置静态 ip 的方法。 1.查看网卡信息 使用ifconfig命令查看网卡信息获取网卡名称 如果出现Command ifconfig not fo…...

EasyCVR无人机推流+人数统计AI算法,助力公共场所人群密度管控
一、背景与需求 在公共场所和大型活动的管理中,人数统计和人群密度控制是非常重要的安全问题。传统的方法可能存在效率低下或准确度不足的情况,无法满足现代社会的需求。TSINGSEE青犀可以利用无人机推流AI人流量统计算法,基于计算机视觉技术…...

Kotlin 接口
Kotlin 的接口可以既包含抽象方法的声明也包含实现;接口无法保存状态;可以有属性但必须声明为抽象或提供访问器实现 1、定义 使用关键字 interface 来定义接口 interface MyInterface {fun bar()fun foo() {// 可选的方法体} } 2、 实现接口 一个类…...

Qt前端技术:5.QSS
这个是表示QFrame中的pushButton中的子类和它子类的子类都将背景变为red 写成大于的时候表示只有直接的子类对象才会变 这个图中的QGroupBox和QPushButton都是QFrame的直接的子类 这个中的QGroupBox是QFrame的直接的子类但是QPushButton 是QGroupBox的子类,QPushB…...

在Centos7中利用Shell脚本:实现MySQL的数据备份
目录 自动化备份MySQL 一.备份数据库脚本 1.创建备份目录 2.创建脚本文件 3.新建配置文件(连接数据库的配置文件) 4.给文件权限(mysql_backup.sh) 编辑 5.执行命令 (mysql_backup.sh) 编辑 二.数据库通过备份恢复 1.创建脚…...

大一C语言查缺补漏 12.24
遗留问题: 6-1 1 在C语言中,如果要保留小数的话,一定要除以2.0,而不是2。 设整型变量m,n,a,b的值均为1,执行表达式(m a>b)||(n a<b)后,表达式的值以及变量m和n的值是&#…...

程序员宝典:常用的免费好物API
六位图片验证码生成:包括纯数字、小写字母、大写字母、大小写混合、数字小写、数字大写、数字大小写等情况。 四位图片验证码生成:四位图片验证码生成,包括纯数字、小写字母、大写字母、大小写混合、数字小写、数字大写、数字大小写等情况。…...

关于“Python”的核心知识点整理大全41
目录 scoreboard.py game_functions.py game_functions.py 14.3.8 显示等级 game_stats.py scoreboard.py scoreboard.py scoreboard.py game_functions.py game_functions.py alien_invasion.py 14.3.9 显示余下的飞船数 ship.py scoreboard.py 我们将最高得分圆整…...

java进阶(二)-java小干货
java一些精干知识点分享 2. java小干货2.1循环遍历2.2可变参数2.3 list和数组转化2.3.1 数组转list2.3.2 list转数组 2.4 值传递和地址传递2.4.1值传递2.4.2 地址传递2.4.3易错点总结 2.5 数据类型2.5.1基础知识2.5.2 基础数据和包装类 2.6 字符串2.6.1 char/String区别2.6.2 .…...

layui(iconPickerFa)图标选择器插件,主要用于后台菜单图标管理
话不多说直接上代码 在页面中引入如下代码 <link rel"stylesheet" href"/template/admin/layui-v2.5.6/css/layui.css"> <script type"text/javascript" src"/template/admin/layui-v2.5.6/layui.js"></script> &…...

RabbitMQ入门指南(九):消费者可靠性
专栏导航 RabbitMQ入门指南 从零开始了解大数据 目录 专栏导航 前言 一、消费者确认机制 二、失败重试机制 三、失败处理策略 四、业务幂等性 1.通过唯一标识符保证操作的幂等性 2.通过业务判断保证操作的幂等性 总结 前言 RabbitMQ是一个高效、可靠的开源消息队列系…...

MySQL的聚合函数、MySQL的联合查询、MySQL的左连接右连接内连接
MySQL的聚合函数 MySQL聚合函数是在数据库中对数据进行聚合操作的函数。它们将多行数据作为输入,并返回单个值作为结果。 常用的MySQL聚合函数包括: COUNT:计算符合条件的行数。SUM:对指定列的数值进行求和操作。AVG࿱…...

RKNN Toolkit Lite2 一键安装和测试,sh脚本
RKNN Toolkit Lite2 安装和测试教程 本教程旨在指导用户如何使用提供的shell脚本来安装和测试RKNN Toolkit Lite2,适用于需要在Linux系统上部署和测试AI模型的开发者。 简介 RKNN Toolkit Lite2是一个高效的AI模型转换和推理工具包,专为Rockchip NPU设…...

探索中国制造API接口:解锁无限商机,引领制造业数字化转型
一、概述 中国制造API接口是一种应用程序接口,专门为中国制造行业提供数据和服务。通过使用API接口,开发者可以轻松地获取中国制造的商品信息、供应商数据、生产能力等,从而为他们的应用程序或网站提供更加丰富的内容和功能。 二、API接口的…...

CentOS上安装MySQL 8.0的详细教程
CentOS上安装MySQL 8.0的详细教程 大家好,我是免费搭建查券返利机器人赚佣金就用微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿!今天我将为大家分享一篇关于在CentOS上安装MySQL 8.0的详细教程。MySQL是一个强大…...

[RISCV] 为android14添加一个新的riscv device
本篇博客将基于android-14-r18添加Sifive unmatched板子的支持。 Setup build envoronment Establishing a build environment $ sudo apt install git-core gnupg flex bison build-essential zip curl zlib1g-dev libc6-dev-i386 libncurses5 x11proto-core-dev libx11-de…...

【Fastadmin】通用排序weigh不执行model模型的事件
在model模型类支持的before_delete、after_delete、before_write、after_write、before_update、after_update、before_insert、after_insert事件行为中,我们可以快捷的做很多操作,如删除缓存、逻辑判断等 但是在fastadmin的通用排序weigh拖动中无法触发…...

logstash收集华为、H3C、Cisco交换机日志
网络设备配置 将 syslog-ip 替换成服务器的IP地址。 Huawei info-center loghost source interface info-center loghost syslog-ip local-time facility local6 H3C info-center loghost source interface info-center loghost syslog-ip facility local5 Aruba logging arm …...

云上荆楚丨云轴科技ZStack成功实践精选(湖北)
湖北自古以来有九省通衢的美称,地处长江中游,富有荆楚之美誉,灵秀之蕴意。2022年湖北数字经济强省三年行动计划正式印发,计划到“十四五”末,数字经济核心产业增加值力争达到7000亿元,占GDP的比重超过12%。…...

C语言字符串处理提取时间(ffmpeg返回的时间字符串)
【1】需求 需求:有一个 “00:01:33.90” 这样格式的时间字符串,需要将这个字符串的时间值提取打印出来(提取时、分、秒、毫秒)。 这个时间字符串从哪里来的? 是ffmpeg返回的时间,也就是视频的总时间。 下…...

NC(65)元数据增加字段
以报销单主表er_bxzb表为例,增加15个字段字段以及两个其他业务所需字段 1、先在er_bxzb增加字段 增加字段 alter table er_bxzb add no_invoice char(1) default(N);alter table er_bxzb add is_enabled_taxation_cloud char(1) default(N);alter table er_bxzb a…...

SParC数据集介绍
导语 SParC是Text-to-SQL领域的一个多轮查询数据集。本篇博客将对该数据集论文和数据格式进行简要介绍。 SParC数据集概述 SParC是一个跨领域的多轮Text-to-SQL数据集。它包含有4298个问题轮次,大约有12k的自然语言问句到SQL标注的Question-SQL对。这些问题来自于…...

OpenGL 绘制Mesh数据(Qt)
文章目录 一、简介二、实现代码三、实现效果一、简介 Mesh数据的结构主要就是点与三角面片,因此本质上仍然是对三角面片进行绘制。这里我们借助VCG这个库实现对Mesh数据的读取,这个库相对简单轻巧,很方便使用。 二、实现代码 由于修改的部分很多,我们逐一进行解释一下: --…...

9.传统的轨道画线算法()
轨道画线分为以下步骤: 1.读取摄像头图片 2.图片灰度处理,截取轨道区域的图片 3.中值滤波处理,并区域取均值后做期望差的绝对值。本人通过一些轨道图片实验,用这种方法二值化得到的效果比caany算子等方法的效果好 4.二值化后再…...

F (1164) : B DS二叉排序树_有效的二叉排序树
Description 给你一个二叉树,判断其是否是一个有效的二叉排序树。 有效的二叉排序树定义如下: 1. 结点的左子树只包含小于当前结点的数。 2. 结点的右子树只包含大于当前结点的数。 3. 所有左子树和右子树自身必须也是二叉排序树。 Input 第一行输…...

结合el-upload修改支持上传图片、视频并预览
结合element plus的el-upload标签,实现上传图片和视频,并支持在线预览和放大 1、html部分 <el-form-item label"活动照片、视频"><el-uploadv-model:file-list"state.photoList":action"state.uploadUrl"accept…...

1.SQL - 概述
1. SQL语句分类 • 数据定义语言:简称DDL(Data Definition Language),用来定义数据库对象:数据库,表,列等。关键字:create,alter,drop等 • 数据操作语言:简称DML(Data …...