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

正定矩阵在格密码中的应用（知识铺垫）

news 2025/8/22 19:32:36

目录

一. 写在前面

二. 最小值点

三. 二次型结构

四. 正定与非正定讨论

4.1 对参数a的要求

4.2 对参数c的要求

4.3 对参数b的要求

五. 最小值，最大值与奇异值

5.1 正定型（positive definite）

5.2 负定型（negative definite）

5.3 奇异型

六. 鞍点（saddle point）

七. 矩阵二次型

7.1 介绍

7.2 举例

例题1

例题2

例题3

八. 正定矩阵与格密码

一. 写在前面

格密码中有时要求格基矩阵是正定的，本文章将从方程和矩阵角度来解释正定性，辅助格密码的理解。

推荐可以先看下这篇文章：

格密码与线性代数-CSDN博客

对称矩阵一定有实数特征值（real eigenvalue）,本文章尝试在不计算矩阵特征值的情况下，快速判断矩阵特征值是否全为正数，其中涉及三个矩阵的基本概念：矩阵的主元（pivot），行列式，特征值。

二. 最小值点

在微分方程中，如果特征值为负数，那么以下函数单调递减：

e^{\lambda t}

在密码学或计算机领域的优化问题（optimization）经常需要判断N维情况下的最小值，数学知识告诉我们这与二阶导（second derivative test）相关，举两个例子：

尝试求这两个二维函数F(x,y),f(x,y)的最小值。

首先可计算：

F(0,0)=7,\quad f(0,0)=0

很明显，最小值肯定要求一阶导数为0，也就是所谓的关注linear term，发现（0,0）该点符合要求，如下：

也就是（0,0）为这两个函数的极值点（stationary point）。

第一个平面z=F(x,y)与水平面z=7相切；

第二个平面z=f(x,y)与水平面z=0相切；

一阶导分析完毕来看下在（0,0）位置的二阶导，如下：

这两个二维函数的二阶导值一样，说明两个函数的性质相同。实际上F(x,y)的最高次幂为-x^3，所以其最小值为-\infty，接下来我们把重心放在f(x,y)。

三. 二次型结构

以上讨论中f(x,y）的形式为二次型：

f=ax^2+2bxy+cy^2

易得在（0,0）处，该类函数的一阶微分：

\frac{\partial f}{\partial x}=\frac{\partial f}{\partial y}=0

也就是该类二次型，原点一定是其极值点。

如果极小值点（local minimum）也是最小值点（global minimum），那么可得此类平面的图形像一个碗，碗的底部就是原点，如下图：

如果极值点不在原点处，而在其他任意点处，比如在x=\alpha,y=\beta，其二阶导如下：

除了原点外，如果函数严格为正数，那么称之为正定（positive definite）。

四. 正定与非正定讨论

对于单变量的函数来讲，二阶大于0，函数拥有最小值，如下：

\frac{\partial^2 F}{\partial x^2}>0

反之，则函数有最大值。

对于二维函数来讲，函数拥有三个二阶导函数：

F_{xx}\quad F_{xy}=F_{yx}\quad F_{yy}

期待利用这三个数来判断函数拥有最小值还是最大值。

目标：什么情况下，二次型f(x,y)=ax^2+2bxy+cy^2为正定的？

4.1 对参数a的要求

当x=1,y=0时，可得：

ax^2+2bxy+cy^2=a

正定性要求a为正数，利用导数的观点解释则是：

\frac{\partial^2 F}{\partial x^2}>0

也就是该曲面沿着x轴向上弯曲。

4.2 对参数c的要求

当x=0时，沿着y轴方向可得：

f(0,y)=cy^2

很明显正定性要求c>0

举两个简单例子，大家可以快速判断下：

例1

f(x,y)=x^2-10xy+y^2

例2

f(x,y)=2x^2+4xy+y^2

解：

例1非正定，因为f(1,1)=-8

例2非正定，因为f(1,-1)=-1

4.3 对参数b的要求

将二次型结构转变为如下完全平方差形式：

观察右边第二项，要想函数正定，则必须：

c-\frac{b^2}{a}>0

也就是：

ac>b^2

五. 最小值，最大值与奇异值

5.1 正定型（positive definite）

根据以上讨论，要想二次型ax^2+2bxy+cy^2为正定，需要满足：

a>0,ac>b^2

如果要求某点处的最小值，那么：

\frac{\partial f}{\partial x}=\frac{\partial f}{\partial y}=0

并且要求：

\frac{\partial^2 F}{\partial x^2}>0\quad [\frac{\partial^2 F}{\partial x^2}][\frac{\partial^2 F}{\partial y^2}]>[\frac{\partial^2 F}{\partial x\partial y}]

5.2 负定型（negative definite）

负定型的要求与正定型刚好相反，如下：

a<0,ac>b^2

由此可求该函数的最大值

5.3 奇异型

当a,b,c满足：

ac=b^2

易得当a>0时，该函数为半正定（positive semi-definite）

当a<0时，该函数为半负定（negative semi-definite）

也就是当x=b,y=-a时，该函数可以取0。原始的平面z=f(x,y)像一个碗，奇异情况下像一个山谷，举例：

f=(x+y)^2

六. 鞍点（saddle point）

鞍点要求：

ac<b^2

举例两个函数：

来看一个图像：

这种二次型既可以取正数，也可以取负数，所以为非定型（indifinite）。从图形上看，此时的极值点既不是最小值，也不是最大值，该点则被称之为鞍点（saddle point）。

七. 矩阵二次型

7.1 介绍

总结以上我们发现，二阶导数其实可以形成一个对称矩阵。将ax^2和cy^2放在对角线，将2bxy分成一半，放在剩下的两个位置上，由此二次型函数f(x,y)即可以表示成一个2行2列的矩阵，如下：

将此处的2维扩展到n维，便可以从矩阵的角度来理解函数的最大值与最小值。假定有n个变量x_1,\cdots,x_n，将其写成列向量x的形式，那么对任意对称矩阵A，矩阵向量相乘与二次型之间是互相等效的，如下：

x^TAx\quad f(x_1,\cdots,x_n)

更具体来讲，如下：

对角线的元素a_{11}\sim a_{nn}与x_1^2\sim x_n^2相乘。对称形式a_{ij}=a_{ji}合并后再相乘可得2a_{ij}x_ix_j，即可以还原函数为：

f=a_{11}x_1^2+2a_{12}x_1x_2+\cdots+a_{nn}x_n^2

注意每一项都是二次型，当x=(0,0,\cdots,0)时，函数的一阶导函数一定为0.该函数的切面是水平的，也就是其极值点。、

借助此理论即可判断当向量x为0时，函数f=x^TAx存在最大值，最小值，还是鞍点。

7.2 举例

例题1

函数f=2x^2+4xy+y^2，其对应矩阵如下：

A=\begin{bmatrix} 2 &2 \\ 2& 1 \end{bmatrix}

很明显为鞍点

例题2

函数f=2xy，其对应矩阵：

A=\begin{bmatrix} 0 &1 \\1& 0 \end{bmatrix}

很明显鞍点

例题3

给定函数如下：

f=2x_1^2-2x_1x_2+2x_2^2-2x_2x_3+2x_3^2

该函数拥有最小值，写成矩阵格式如下：

其实矩阵A可以看成二阶导的矩阵，也就是满足：

a_{ij}=\frac{\partial^2 F}{\partial x_i\partial x_j}

同理可得：

a_{ji}=\frac{\partial^2 F}{\partial x_j\partial x_i}

从这个角度也可以理解矩阵A为对称矩阵，很明显当原函数存在最小值时，矩阵A则为正定的。

八. 正定矩阵与格密码

正定矩阵与特征值有关，格基特征值的大小会影响格密码中光滑参数的大小，从而影响安全性。具体这方面的知识会陆续更新。

http://www.lryc.cn/news/273224.html

相关文章：

  • 关于使用Selenium获取网页控制台的数据
  • vue2和vue3中的路由使用及传参方式
  • 论文管理器
  • postfix配置tls加密
  • 虚拟专线网络(IP-VPN)
  • 【Unity动画系统】Unity动画系统Animation详解,参数细节你是否弄清？
  • K8S Helm安装RocketMQ standalone单机版，配置外网地址注册到nameserver中方便本地开发
  • 分布式基础概念
  • 蓝桥杯python比赛历届真题99道经典练习题 （89-99）
  • 蚂蚁矿机AntMiner T9+引出IO定义
  • 浅析 Dockerfile 构建缓存：原理与优化方法
  • 隐藏层节点数对分类准确率的影响
  • 【水浸传感器】软硬件一体水浸监测整套方案远程监测解决各种环境漏水问题
  • 知虾会员**成为知虾会员，尊享专属权益**
  • 好代码网同款wordpress主题，适合搭建资源分享类网站，自带五六百的精品资源数据
  • Java多线程＜三＞常见的多线程设计模式
  • JavaScript 基础二part1.运算符：赋值、一元、比较、逻辑运算符
  • Linux 进程(八) 进程的退出码
  • Go语言中支持的internal目录配置与组织内私网包配置详解
  • 如何使用Nmap加强网络安全？
  • LeetCode 2487. 从链表中移除节点：单调栈
  • LabVIEW在高精度机器人视觉定位系统中的应用
  • Arm CCA机密计算扩展
  • 【Unity入门】热更新框架之xLua
  • 大数据Doris（四十五）：物化视图选择最优
  • PostgreSQL10数据库源码安装及plpython2u、uuid-ossp插件安装
  • 如何成为ChatGPT 优质Prompt创作者
  • LeetCode第71题 - 简化路径
  • VSCode上远程调试代码出现的问题
  • 【langchain】入门初探实战笔记（Chain, Retrieve, Memory, Agent）