§ Using LLL to discover minimal polynomial for floating point number
- Explain by example. Let floating point number .
- Clearly, this has a minpoly of with coefficients in .
- However, we know that the correct minpoly is .
- What's the difference in these two cases? Well, the correct minpoly has "small" coefficients.
- How do we find such a minpoly using LLL?
- Key idea: Build vectors (in our case) of the form , , and . Then LLL, on trying to find a shorter basis for these, will try very hard to make the third component smaller. It will do this by changing the basis vectors to , and . Since , the length of is much smaller than , granting us a shorter basis!
- In general, given some rational number , we build
n basis vectors
v_i of dimension
n+1of the form
v_i[i] = 1,
v_i[n] = 1000(θ^i), and
v_i[-] = 0 otherwise.
- LLLing on these vectors
v_i will attempt to find an integer relation on the last coefficient, which will be the minpoly.