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

2024-01-04 23:52

本文主要是介绍正定矩阵在格密码中的应用(知识铺垫),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

一. 写在前面

二. 最小值点

三. 二次型结构

四. 正定与非正定讨论

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^2cy^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.chinasem.cn/article/571000

相关文章

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

Python Dash框架在数据可视化仪表板中的应用与实践记录

《PythonDash框架在数据可视化仪表板中的应用与实践记录》Python的PlotlyDash库提供了一种简便且强大的方式来构建和展示互动式数据仪表板,本篇文章将深入探讨如何使用Dash设计一... 目录python Dash框架在数据可视化仪表板中的应用与实践1. 什么是Plotly Dash?1.1

Android Kotlin 高阶函数详解及其在协程中的应用小结

《AndroidKotlin高阶函数详解及其在协程中的应用小结》高阶函数是Kotlin中的一个重要特性,它能够将函数作为一等公民(First-ClassCitizen),使得代码更加简洁、灵活和可... 目录1. 引言2. 什么是高阶函数?3. 高阶函数的基础用法3.1 传递函数作为参数3.2 Lambda

Java中&和&&以及|和||的区别、应用场景和代码示例

《Java中&和&&以及|和||的区别、应用场景和代码示例》:本文主要介绍Java中的逻辑运算符&、&&、|和||的区别,包括它们在布尔和整数类型上的应用,文中通过代码介绍的非常详细,需要的朋友可... 目录前言1. & 和 &&代码示例2. | 和 ||代码示例3. 为什么要使用 & 和 | 而不是总是使

Python循环缓冲区的应用详解

《Python循环缓冲区的应用详解》循环缓冲区是一个线性缓冲区,逻辑上被视为一个循环的结构,本文主要为大家介绍了Python中循环缓冲区的相关应用,有兴趣的小伙伴可以了解一下... 目录什么是循环缓冲区循环缓冲区的结构python中的循环缓冲区实现运行循环缓冲区循环缓冲区的优势应用案例Python中的实现库

SpringBoot整合MybatisPlus的基本应用指南

《SpringBoot整合MybatisPlus的基本应用指南》MyBatis-Plus,简称MP,是一个MyBatis的增强工具,在MyBatis的基础上只做增强不做改变,下面小编就来和大家介绍一下... 目录一、MyBATisPlus简介二、SpringBoot整合MybatisPlus1、创建数据库和

python中time模块的常用方法及应用详解

《python中time模块的常用方法及应用详解》在Python开发中,时间处理是绕不开的刚需场景,从性能计时到定时任务,从日志记录到数据同步,时间模块始终是开发者最得力的工具之一,本文将通过真实案例... 目录一、时间基石:time.time()典型场景:程序性能分析进阶技巧:结合上下文管理器实现自动计时

SpringSecurity 认证、注销、权限控制功能(注销、记住密码、自定义登入页)

《SpringSecurity认证、注销、权限控制功能(注销、记住密码、自定义登入页)》SpringSecurity是一个强大的Java框架,用于保护应用程序的安全性,它提供了一套全面的安全解决方案... 目录简介认识Spring Security“认证”(Authentication)“授权” (Auth

Java逻辑运算符之&&、|| 与&、 |的区别及应用

《Java逻辑运算符之&&、||与&、|的区别及应用》:本文主要介绍Java逻辑运算符之&&、||与&、|的区别及应用的相关资料,分别是&&、||与&、|,并探讨了它们在不同应用场景中... 目录前言一、基本概念与运算符介绍二、短路与与非短路与:&& 与 & 的区别1. &&:短路与(AND)2. &:非短

国内环境搭建私有知识问答库踩坑记录(ollama+deepseek+ragflow)

《国内环境搭建私有知识问答库踩坑记录(ollama+deepseek+ragflow)》本文给大家利用deepseek模型搭建私有知识问答库的详细步骤和遇到的问题及解决办法,感兴趣的朋友一起看看吧... 目录1. 第1步大家在安装完ollama后,需要到系统环境变量中添加两个变量2. 第3步 “在cmd中