Class 19: Lattice Reductions

I'm going to use these old SAGE notes for most of this, but here is my plan and a FLAG:

NOTES ON CLOUD.SAGEMATH.COM (now cocalc)

• What's a lattice?
• GCD is actually mini lattice reduction
• The Knapsack Problem with LLL
• Minimal Polynomials

What's a Lattice

It's all integer combinations of some vectors. It looks like this:

To play with one we think of vectors and start adding them up.

Find Me: Let \(v_1 = (-502, 469, -111)\) and \(v_2 = (101, -95, 23)\) what is the smallest integer combination of those two you can find?

xGCD style

Find Me: Let \(v_1 = (1, 0, 3920)\) and \(v_2 = (0, 1, 4200)\) what is the smallest integer combination of those two you can find?

LLL

Make a matrix in Sage and call M.LLL()

Retry those two problems using LLL.

A Minpoly Flag