svp
SVP问题概述
The SVP is simply: given a lattice Lrepresented by a basis, find a nonzerov ∈Lsuch that||v||is Minimized, where||▪||denotes a particular norm onRn.
对于一个基于B的格，找到一个属于L的最小非零向量v
这里也摘录了一些文献中SVP的一些相关定义、定理
我们知道SVP是一个NP-COMPLETE问题，但是如何分析它呢？根据众多文献的引用，我找到一篇根文献，Generating Hard instances of Lattice problems并展开了我的SVP学习之旅。这篇文章详细阐述了SVP问题。
关于SVP问题，有一些著名的算法。
非常著名的一个就是LLL算法。参考文献：Factoring Polynomials with Rational Coefficients
该算法在多项式时间内, 输出近似因子为的最短向量，解决了近似最短向量问题。LLL 算法的提出对格理论的研究, 特别是公钥密码算法分析起到了很大的推动作用, 不仅是在密码
领域, LLL 算法在计算代数、计算数论等领域也有广泛的应用, 已被公认为是 20 世纪最重要的算法之一。