格密码:傅里叶矩阵

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

目录

一. 铺垫性介绍

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日
    浏览(50)
  • 线性代数:线性方程求解、矩阵的逆、线性组合、线性独立

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

    2024年02月08日
    浏览(50)
  • 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日
    浏览(56)
  • 线性代数2:矩阵(1)

    目录 矩阵: 矩阵的定义: 0矩阵 方阵  同型矩阵: 矩阵相等的判定条件  矩阵的三则运算: 乘法的适用条件 矩阵与常数的乘法: 矩阵的乘法: 矩阵的乘法法则:  Note1:  Note2:  Note3:  向量与矩阵的关系: 转置矩阵:  矩阵多项式: 矩阵的重要性质:  性质2:  性质

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

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

    2023年04月08日
    浏览(257)
  • 线性代数——求逆矩阵

    利用计算技巧凑出公式:两边加E、提取公因式、没有公因式可提时利用隐形的E=AA^(-1),因为E可看作系数1 主对角线有矩阵(副对角线是0矩阵),则分别逆后放在原位置 副对角线有矩阵(主对角线是0矩阵),则分别逆后互换位置

    2024年02月11日
    浏览(52)
  • 线性代数基础【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日
    浏览(52)
  • 线性代数_对称矩阵

    对称矩阵是线性代数中一种非常重要的矩阵结构,它具有许多独特的性质和应用。下面是对称矩阵的详细描述: ### 定义 对称矩阵,即对称方阵,是指一个n阶方阵A,其转置矩阵等于其本身,即A^T = A。这意味着方阵A中的元素满足交换律,即对于任意的i和j(i ≤ j),都有A[

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

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

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

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

    2024年02月11日
    浏览(46)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包