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

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

相关文章

C语言中位操作的实际应用举例

《C语言中位操作的实际应用举例》:本文主要介绍C语言中位操作的实际应用,总结了位操作的使用场景,并指出了需要注意的问题,如可读性、平台依赖性和溢出风险,文中通过代码介绍的非常详细,需要的朋友可以参... 目录1. 嵌入式系统与硬件寄存器操作2. 网络协议解析3. 图像处理与颜色编码4. 高效处理布尔标志集合

Windows 上如果忘记了 MySQL 密码 重置密码的两种方法

《Windows上如果忘记了MySQL密码重置密码的两种方法》:本文主要介绍Windows上如果忘记了MySQL密码重置密码的两种方法,本文通过两种方法结合实例代码给大家介绍的非常详细,感... 目录方法 1:以跳过权限验证模式启动 mysql 并重置密码方法 2:使用 my.ini 文件的临时配置在 Wi

一文详解Java异常处理你都了解哪些知识

《一文详解Java异常处理你都了解哪些知识》:本文主要介绍Java异常处理的相关资料,包括异常的分类、捕获和处理异常的语法、常见的异常类型以及自定义异常的实现,文中通过代码介绍的非常详细,需要的朋... 目录前言一、什么是异常二、异常的分类2.1 受检异常2.2 非受检异常三、异常处理的语法3.1 try-

Java中的Lambda表达式及其应用小结

《Java中的Lambda表达式及其应用小结》Java中的Lambda表达式是一项极具创新性的特性,它使得Java代码更加简洁和高效,尤其是在集合操作和并行处理方面,:本文主要介绍Java中的La... 目录前言1. 什么是Lambda表达式?2. Lambda表达式的基本语法例子1:最简单的Lambda表

Python结合PyWebView库打造跨平台桌面应用

《Python结合PyWebView库打造跨平台桌面应用》随着Web技术的发展,将HTML/CSS/JavaScript与Python结合构建桌面应用成为可能,本文将系统讲解如何使用PyWebView... 目录一、技术原理与优势分析1.1 架构原理1.2 核心优势二、开发环境搭建2.1 安装依赖2.2 验

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

SpringShell命令行之交互式Shell应用开发方式

《SpringShell命令行之交互式Shell应用开发方式》本文将深入探讨SpringShell的核心特性、实现方式及应用场景,帮助开发者掌握这一强大工具,具有很好的参考价值,希望对大家有所帮助,如... 目录引言一、Spring Shell概述二、创建命令类三、命令参数处理四、命令分组与帮助系统五、自定

SpringBoot应用中出现的Full GC问题的场景与解决

《SpringBoot应用中出现的FullGC问题的场景与解决》这篇文章主要为大家详细介绍了SpringBoot应用中出现的FullGC问题的场景与解决方法,文中的示例代码讲解详细,感兴趣的小伙伴可... 目录Full GC的原理与触发条件原理触发条件对Spring Boot应用的影响示例代码优化建议结论F

MySQL 分区与分库分表策略应用小结

《MySQL分区与分库分表策略应用小结》在大数据量、复杂查询和高并发的应用场景下,单一数据库往往难以满足性能和扩展性的要求,本文将详细介绍这两种策略的基本概念、实现方法及优缺点,并通过实际案例展示如... 目录mysql 分区与分库分表策略1. 数据库水平拆分的背景2. MySQL 分区策略2.1 分区概念

Spring Shell 命令行实现交互式Shell应用开发

《SpringShell命令行实现交互式Shell应用开发》本文主要介绍了SpringShell命令行实现交互式Shell应用开发,能够帮助开发者快速构建功能丰富的命令行应用程序,具有一定的参考价... 目录引言一、Spring Shell概述二、创建命令类三、命令参数处理四、命令分组与帮助系统五、自定义S