3 ms·
For context: I'm a computer science MSc student. The notation is easy to understand (and as far as mathematical notation goes, really quite tame). I don't kno
by nightcracker 6y ago
For context: I'm a computer science MSc student.
The notation is easy to understand (and as far as mathematical notation goes, really quite tame). I don't know what a nearly shortest vector of a lattice is in this context, but I do understand everything else. Note that means I have no idea how the actual method works, but I can understand what's being claimed.
- sterlind 6y agoNot an expert at all, but you can think of lattices as evenly-spaced grid points in a vector space. Given a set of basis vectors b0..bn, and arbitrary integers a0..an, a0b0 + ... + anbn are points on the lattice b. You can have a "good basis" where the norms for b are low, or an equivalent "bad basis" with the same lattice points but with high norms. That's one hard problem (lattice reduction), but there are polynomial-time approximations. The shortest vector problem, iirc, is to find the vector with the smallest norm in the best possible basis of that lattice.