undefined | Better HN

0 pointsaruss8y ago0 comments

So, solving CVP? That's a pretty neat application, though.

0 comments

pbsd8y ago

The typical way you'd solve that would be to take

    [K * pi      1 0 0]
    [K * e       0 1 0]
    [K * sqrt(2) 0 0 1]
    [K * 194.927424491 0 0 0]

for some large-ish K, say 2^20, and look for a short(est) vector of this lattice. Basically you're minimizing the norm of (a * pi + b * e + c * sqrt(2) + d * 194.927424491, a, b, c) while giving the majority of the weight to the first component, which you hope to be near 0.

cperciva8y ago

look for a short(est) vector of this lattice

Just to elaborate slightly on this: Finding the shortest vector in a lattice is (in general) hard, but finding a vector which is no more than a constant times the length of the shortest vector is easy. So techniques which rely on lattice reduction usually construct a lattice such that the shortest vector is much shorter than the second-shortest vector -- in other words, the shortest vector is the only one which satisfies the "no more than X times the length of the shortest vector" condition.

In the case of integer relation finding, this translates into having enough digits and making the value K large enough.

j / k navigate · click thread line to collapse