格理论和密码学（一）

最近在学格，这里开个坑，尽量实训结束前搞完

格理论和密码学（一）

• 格的定义
• • 基础区域
  • 格的行列式
  • 基的转换
  • 格的两大难题
  • • 最短向量问题
    • 最近向量问题
• 重要定理
• • Hadamard不等式
  • • Hadamard比率
  • Hermite定理
  • Minkowski定理

格的定义

格的定义可以从向量空间引申出来：

一组线性无关的的向量v1，v2，...，vn，它们的线性组合a1v1+a2v2+...+anvn可以
表示一个空间，如果a1,a2，...，an全为整数，则生成了一个格L。则这组向量称为
格的基，向量个数称为格的维数。

基础区域

格的基础区域为即当a1，an，,，an为0或1组成的一个区域。格中任意一个向量可以由格的基础区域和唯一格外的一个向量表示。基础区域是格很重要的概念。

格的行列式

格的行列式就是基础区域的n维体积，记作$det(L)$

基的转换

设以v1，v2，…，vn为行向量构成的n阶矩阵为A，某一行列式等于1的n阶矩阵为 U，则矩阵B=UA中的行向量也是格L的一组基。
从线性变换的本质来看，线性变换是对空间进行伸缩或者翻转的操作（可惜大多数高校的非数学专业是不会讲这些的，具体可以看b站3b1b的搬运，有关线性代数的本质的介绍，可以给我们很直观的理解），由于U的行列式为1，那么变换后的基础区域体积不变。

格的两大难题

均为NP完全问题

最短向量问题

简称SVP，在格中寻找一个非零向量，使它的范数最小。

最近向量问题

简称CVP，给定一个不在格中的向量，找到格中一个向量使它最接近给定的向量，即欧几里得范数最小。

重要定理

Hadamard不等式

格L的基础区域为F，对于它任意一个基 v 1 v_1 v1​, v 2 v_2 v2​,…, v n v_n vn​有：
$det(L)=vol(F)\le$|| v 1 v_1 v1​||*|| v 2 v_2 v2​||*…*|| v n v_n vn​||
基向量越接近正交，则上式越接近等式

Hadamard比率

H ( L ) = ( d e t ( L ) ∣ ∣ v 1 ∣ ∣ ∗ ∣ ∣ v 2 ∣ ∣ ∗ . . . ∗ ∣ ∣ v n ∣ ∣ ) 1 / n H(L)=(\frac{det(L)}{||v_1||*||v_2||*...*||v_n||})^{1/n} H(L)=(∣∣v1​∣∣∗∣∣v2​∣∣∗...∗∣∣vn​∣∣det(L)​)1/n
当这个值越接近1，则基越接近两两正交

Hermite定理

所有n维的格L都包含一个非0向量$v\in$L，满足||$v$||$\le$ γ n \gamma_n γn​ d e t ( L ) 1 / n det(L)^{1/n} det(L)1/n
对于给定的维度n，Hermite常量 γ n \gamma_n γn​是一个最小值，它可以使所有n维格L都包含非零向量$v\in$L满足上式
其中Hertmite常量 γ n \gamma_n γn​满足：
n 2 Π e ≤ γ n ≤ n Π e \frac{n}{2Πe}\leq\gamma_n\leq\frac{n}{Πe} 2Πen​≤γn​≤Πen​

Minkowski定理

设 L ⊂ R n L\subset\R^n L⊂Rn是一个n维的格，S ⊂ R n \subset\R^n ⊂Rn是一个对称凸面集合，其体积满足：
vol(S) > 2 n d e t ( L ) >2^ndet(L) >2ndet(L)
如果S满足封闭性，则上式等式成立。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！