格密码:傅里叶矩阵

这篇具有很好参考价值的文章主要介绍了格密码:傅里叶矩阵。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一. 铺垫性介绍

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也可以取复数。

根据以上讨论,傅里叶矩阵:

  1. N维方阵;
  2. 对称矩阵(关于对角线);
  3. 正交阵(注意差N倍系数,严格叫酉矩阵);

已经出现论文讨论将傅里叶矩阵作为格基,之所以这样是有如下好处:

  1. 格基为正交阵,格基良好,可解决很多格上困难问题(CVP,LWE等);
  2. 逆矩阵容易求,很容易导出对偶格;

格密码中很多时候需要利用“环版本”,比如RLWE或者Ring-SIS问题。一个环元素本质是一个多项式,两个多项式相乘的计算复杂度为,但如果借助快速傅里叶变换(FFT),其复杂度可以降低到。文章来源地址https://www.toymoban.com/news/detail-771655.html

到了这里,关于格密码:傅里叶矩阵的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 线性代数本质系列(一)向量,线性组合,线性相关,矩阵

    本系列文章将从下面不同角度解析线性代数的本质,本文是本系列第一篇 向量究竟是什么? 向量的线性组合,基与线性相关 矩阵与线性相关 矩阵乘法与线性变换 三维空间中的线性变换 行列式 逆矩阵,列空间,秩与零空间 克莱姆法则 非方阵 点积与对偶性 叉积 以线性变换

    2024年02月04日
    浏览(54)
  • 线性代数:线性方程求解、矩阵的逆、线性组合、线性独立

    本文参考www.deeplearningbook.org一书第二章2.3 Identity and Inverse Matrices 2.4 Linear Dependence and Span 本文围绕 线性方程求解 依次介绍矩阵的逆、线性组合、线性独立等线性代数的基础知识点。 本文主要围绕求解线性方程展开,我们先把线性方程写出来,方程如下: 其中,是已知的;,

    2024年02月08日
    浏览(54)
  • 0203逆矩阵-矩阵及其运算-线性代数

    定义7 对于 n n n 阶矩阵A,如果有一个 n n n 阶矩阵B,使 A B = B A = E AB=BA=E A B = B A = E 则说矩阵A是可逆的,并把矩阵B称为A的逆矩阵,简称逆阵。 定理1 若矩阵A可逆,则 ∣ A ∣ ≠ 0 vert Avert not = 0 ∣ A ∣  = 0 证明: A 可逆,即有 A − 1 ,使得 A A − 1 = E ∣ A A − 1 ∣ = ∣ A

    2024年04月13日
    浏览(60)
  • 线性代数3:矩阵

    目录 矩阵研究的是什么呢? 逆阵 什么叫做逆阵?  例题1:  例题2:  逆阵的存在性 定理1: 定理2: 定理3: 定理4: 拉普拉茨方程 方阵可以的条件  例题3:  Note1: 例题4  Note2:  Note3: Note4:  Note5:  Note6: Note7:  例题5:  逆矩阵的求法: 方法1:伴随矩阵法:  方

    2024年02月13日
    浏览(58)
  • 线性代数基础--矩阵

     矩阵是由排列在矩形阵列中的数字或其他数学对象组成的表格结构。它由行和列组成,并且在数学和应用领域中广泛使用。 元素:矩阵中的每个数字称为元素。元素可以是实数、复数或其他数学对象。 维度:矩阵的维度表示矩阵的行数和列数。一个 m × n 的矩阵有 m 行和

    2024年02月11日
    浏览(47)
  • 线性代数基础【2】矩阵

    一、基本概念 ①矩阵 像如下图示的为矩阵,记为A=(aij)m*n ②同型矩阵及矩阵相等 若A、B为如下两个矩阵 如果A和B的行数和列数相等,那么A和B为同型矩阵,且A和B的元素相等(即:aij=bij),则称A和B相等 ③伴随矩阵 设A为n阶矩阵(如上图所示),设A的行列式|A|,则A中aij的余子式为Mij,代数余

    2024年02月04日
    浏览(53)
  • 线性代数——矩阵

    学习高等数学和线性代数需要的初等数学知识 线性代数——行列式 线性代数——矩阵 线性代数——向量 线性代数——线性方程组 线性代数——特征值和特征向量 线性代数——二次型 本文大部分内容皆来自李永乐老师考研教材和视频课。 从矩阵的转置章节到方阵和行列式

    2023年04月08日
    浏览(271)
  • 线性代数(七) 矩阵分析

    从性线变换我们得出,矩阵和函数是密不可分的。如何用函数的思维来分析矩阵。 通过这个定义我们就定义了矩阵序列的 收敛性 。 研究矩阵序列收敛性的常用方法,是用《常见向量范数和矩阵范数》来研究矩阵序列的极限。 长度是范数的一个特例。事实上,Frobenius范数对

    2024年02月08日
    浏览(50)
  • 投影矩阵推导【线性代数】

    如果两个向量垂直,那么满足。但如果两个向量不垂直,我们就将 b 投影到 a 上,就得到了二者的距离,我们也称为向量 b 到直线 a 的误差。这样就有出现了垂直:                (1) 投影向量 p 在直线上,不妨假设  ,那么误差 。带入式(1)中得到: 投影矩阵:  

    2024年02月06日
    浏览(61)
  • 线性代数-矩阵的本质

    线性代数-矩阵的本质

    2024年02月11日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包