type
status
date
summary
password
category
slug
icon
接着上一篇继续写,格中计算困难性问题
🧐最短距离🤩距离函数(Distance Function)🫣覆盖半径(Covering Radius)🥀格的平滑参数浅浅理解高斯平滑的作用:❓为什么要用到平滑参数?🥹Lattice的几何构造❓为什么要构造📑如何构造📑Lattice Rounding(取整)问题🤔格中计算困难性问题✍️最短向量问题 (Shortest Vector Problem,SVP)γ-近似最短向量问题 (SVP-γ) 最短线性无关向量问题 (Shortest Independent Vector Problem, SIVP)连续最小长度问题 (Successive Minima Problem, SMP)唯一最短向量问题 (Unique Shortest Vector Problem, uSVP-γ)✍️最近向量问题 (Closest Vector Problem,CVP)📎 参考文章
🧐最短距离
除了行列式,格的另一个基本量是格上最短非零向量的长度,即格中最短距离,其定义为
如图,两两格点构成的向量都可以通过平移得到起始点为原点的向量,通过找到距离原点最近的格点即可计算出格中最短距离。格中最短距离也称为第一连续极小,记为1
同理可定义第二至第n连续极小,2,3……n
在二维格上,可以用多项式时间算法求解出1,但在多维格上求解1则十分困难。注意,给定一组格基,最短向量不一定是格基之一
🤩距离函数(Distance Function)
给定任意一个点t(这个点不需要在Lattice上),我们可以定义距离函数为这个点到附近的Lattice点的最短距离。
🫣覆盖半径(Covering Radius)
左右移动t的位置,然后就可以找到在这个Lattice中可以得到的最大的。我们一般称这个最大值叫覆盖半径(Covering Radius)
假设在这个Lattice中,以每个格点为圆心画很多个圆,
如果逐渐把圆的半径扩大的话, 那么所有的圆就会逐渐开始覆盖整个空间
🥀格的平滑参数
如果在每个格点上叠加一个圆形范围内取值的随机噪音(生成一个随机值,将这个随机值与圆形范围内的所有格点元的半径相加或替换),那么当圆的半径达到覆盖半径之后,这个Lattice本身就和背后的连续空间合二为一了
浅浅理解高斯平滑的作用:
缩小r的值,半径对应的向量的每个分向量仅略大
❓为什么要用到平滑参数?
实际上,平滑参数只是定义了一个临界值,当格上的离散高斯分布的标准方差大于此参数时,那么从此分布中选取的点在模格的单元平行多面体中后,几乎将服从均匀随机分布,而当小于此参数时,则不服从均匀随机分布。
🥹Lattice的几何构造
❓为什么要构造
最简单的笛卡尔坐标系整数格,其基向量都是相互垂直的(orthogonal basis),如果我们可以把一个任意的LatticeΛ转换为一个垂直基的格,那么可以更方便简单的在几何空间分析格,比如找到一个格中一个距离t(随意给定的目标值)最近的非零向量v,将其转化为几何空间,只需要通过上下取整,就可以快速找到。
📑如何构造
把一个Lattice的基进行变换,找到一组非常接近垂直的基的,这一过程称之为Lattice Basis Reduction。
比较常见的Basis Reduction方法是Gram-Schmidt正交化过程
回忆上一篇提到n维空间得到一组基
📑Lattice Rounding(取整)问题
刚刚Lattice的几何构造提到一个例子,“找到一个格中一个距离t(随意给定的目标值)最近的非零向量v,将其转化为几何空间,只需要通过上下取整,就可以快速找到”
那如何取整呢??
👉,那么我们通过取整操作就能解决 👉如果落点在外圈圆的话,那么很有可能就会被取整到隔壁的格点上去,那么那个点就不是最近的了
🤔格中计算困难性问题
- 最短向量问题 (Shortest Vector Problem,SVP)
- γ-近似最短向量问题 (SVP-γ)
- 连续最小长度问题 (Successive Minima Problem, SMP):
- 最短线性无关向量问题 (Shortest Independent Vector Problem, SIVP)
- 唯一最短向量问题 (Unique Shortest Vector Problem, uSVP-γ)
- 最近向量问题 (Closest Vector Problem,CVP)
👇👇👇👇👇
✍️最短向量问题 (Shortest Vector Problem,SVP)
给定格L及其基向量B,找到格L中的非零向量v使得对于格中的任意其它非零向量u,。
γ-近似最短向量问题 (SVP-γ)
给定格L,找到格L中的非零向量v使得对于格中的任意其它非零向量u,
当时,就有多个结果啦
最短线性无关向量问题 (Shortest Independent Vector Problem, SIVP)
定一个秩为n的格L,找到格L中n个线性无关向量 ,满足。
就是找到格中n个向量,这n个向量全都小于格中最长向量
连续最小长度问题 (Successive Minima Problem, SMP)
给定秩为n的格L,找到格L中n 个线性无关向量 ,满足 。
唯一最短向量问题 (Unique Shortest Vector Problem, uSVP-γ)
给定格L及其基向量B,找到格L中的非零向量v使得对于格中的任意其它非零向量u,。
✍️最近向量问题 (Closest Vector Problem,CVP)
给定格L和目标向量 ,找到一个格中的非零向量v,使得对于格中的任意非零向量 u,满足.
📎 参考文章
我爱密码!!!!爱格密码!!! 🥲😅😥🤐🙃😖😭 今天半只脚踏进去了……接下来做题去,小师傅给滴,他说很简单,不知道我会不会难哭,浅浅不期待🫣