The Shortest Vector Problem (SVP) corresponds to deterministically solving the following algorithms problem.
Given a lattice \(\Lambda \subseteq \mathbb{R}^{n}\), say by giving out a \(\mathbb{Z}\)-basis of \(\Lambda\), can we find a shortest vector in \(\Lambda\)?
The LLL algorithm is an approximage SVP algorthm. It outputs, in polynomial time, a vector \(v \in \Lambda \setminus \{ 0\}\) such that \[\begin{align} \lambda_1(\Lambda) \le \|v\| \le 2^{n} \lambda_1(\Lambda), \end{align}\] where \(\lambda_1(\Lambda)\) is the length of the smallest vector in \(\Lambda\). See Minkowski’s theorem to know where the notation comes from.
Given an algorithm \(A\) that can solve SVP for those those lattices \(\Lambda\) such that \(\lambda_1(\Lambda) \in [c_1,c_2]\) for some interval \(c_1,c_2 > 0\), we can use \(A\) finitely many times along with the LLL algorithm to get something that works for all \(\Lambda\).
Currently known candidates for algorithm \(A\) have exponential running time in \(n\). The SVP problem is NP-Hard.
This link contains some useful information about time complexity of known algorithms.
This link contains a C++ implementation.
There’s a landmark result of Ajtai about worst case complexity of the SVP being as bad as the average case SVP.
I don’t understand it a lot, but this thesis seems to be useful.
This page was updated on November 21, 2022.
Main Page