News for hackers. Stuff that matters.
Re:Did Schnorr destroy RSA? Show me the factors by sterlind on Wednesday March 03, 2021 @05:10PM (#26335423)
Not 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.

There are no comments on this comment yet.