格中困难问题

SVP

定义：最短向量问题，给定一个格，找出其中长度最短的非零向量

精确SVP：找到格中最短向量使$∥v∥=λ1(L)$

γ-SVP近似最短向量：找到格中一个向量使$||v||≤γ*λ1(L)$，γ为近似因子，γ≥1

CVP

$$ (CVP_γ,搜索):在\mathcal{L}(B)里找一个点x，让x到t的距离，不超过格里其他点到t的距离的γ倍，||x-t||≤γ⋅||y-t||\\ (CVP_γ,优化):找一个数r，使得r属于最短距离和最短距离的γ倍之间,dist(t,L(B))≤r≤γ⋅dist(t,L(B))\\ (CVP_γ,判断):给定一个数r，来判断最短距离 ≤ r|最短距离＞γ⋅r，dist(t,L(B))≤r|dist(t,L(B))≥γ⋅r $$

上面γ≥1为近似因子。当γ=1时，为精确cvp问题

LWE

给定任意数量长度相同的随机向量$a_i$和表达式$(as_i+e_i)$，其中$e_i$为一个随机小误差，从中找s

$$ t=As+e $$

傅里叶导论

一维傅里叶变换

定义1：满足

$$ f_{-∞}^{∞}|f(x)|dx<∞ $$

那么$f∈L^1(R)$

定义2：对任意满足$f∈L^1(R)$，定义它的傅里叶变换为函数

n维傅里叶变换

定义：定义$L^1(R^n)$，为所有满足$∫_{Rn}∣f(x)∣dx<∞$，的函数$f:R^n→C$的集合

定义其傅里叶变换为：

$$ f(y)=∫_{Rn}f(x)e^{−2πi⟨x,y⟩}dx $$

傅里叶级数

不同的几个波叠加起来，ak,bk表示波的个数，k表示波的频率

整数规划

整数规划概念

整数规划问题(IP)：指的是判断是否存在一个解，使其满足给定的一组关于多个变量的有理数不等式

给定一个矩阵$A∈Q^{m*n}$，和向量$b∈Q^m$判断是否存在$z∈Z^n$,使Az≤b，等价于：

$$ Z^n∩ \{x∈R^n|Ax≤b\} $$

Lenstra 算法

是整数规划问题的推广版本

给定一个凸体K∈R^n^，找一个点K∩Z^n^，或者判断这个是空集

凸体：一个内部有界的，凸的，内部非空的集合

凸性：对任意x,y∈K，α∈[0,1]，都满足αx+(1-α)y∈K

John 定理

表明了任意凸体都可以被椭圆近似

存在一对同心椭圆(E’,E)满足E’⊆ K ⊆ E，并且E=n⋅E’，这样的椭圆称为Lowner-John对