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.
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.