## § Using LLL to discover minimal polynomial for floating point number

- Explain by example. Let floating point number $f = 1.4142$.
- Clearly, this has a minpoly of $10000x - 14142 = 0$ with coefficients in $Z[x]$.
- However, we know that the correct minpoly is $x^2 - 2 = 0$.
- 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 $b_0 \equiv (1, 0, 0, 1000)$, $b_1 \equiv (0, 1, 0, 1000f)$, and $b_2 \equiv (1000f^2)$. 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 $b'_0 \equiv b_0, b'_1 \equiv b_1$, and $b'_2 \equiv b_2 - 2b_0 = (-1, 0, 1, 1000(f^2 - 2)$. Since $f^2 - 2 \sim 0$, the length of $b'_2$is much smaller than $b_2$, granting us a shorter basis!
- In general, given some rational number $\theta$, we build
`n`

basis vectors `v_i`

of dimension `n+1`

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