# Recognizing Algebraic Numbers using Lattice Basis Reduction (LLL)

Suppose you somehow compute a decimal approximation to some rational number and from this wish to recover . For concreteness, say

and you compute

Now suppose given only that you would like to recover . A standard technique is to use continued fractions, which yields a sequence of good rational approximations for ; by truncating right before a surprisingly big partial quotient, we obtain :
sage: v = continued_fraction(0.056555)
sage: continued_fraction(0.056555)
[0, 17, 1, 2, 6, 1, 23, 1, 1, 1, 1, 1, 2]
sage: convergents([0, 17, 1, 2, 6, 1])
[0, 1/17, 1/18, 3/53, 19/336, 22/389]


Generalizing this, suppose next that somehow you numerically approximate an algebraic number, e.g., by evaluating a special function and get a decimal approximation to an algebraic number . For concreteness, suppose :

sage: N(1/3 + 3^(1/4), digits=50)
1.64940734628582579415255223513033238849340192353916

Now suppose you very much want to find the (rescaled) minimal polynomial of just given this numerical approximation . This is of great value even without proof, since often in practice once you know a potential minimal polynomial you can verify that it is in fact right. Exactly this situation arises in the explicit construction of class fields (a more advanced topic in number theory) and in the construction of Heegner points on elliptic curves. As we will see, the LLL algorithm provides a polynomial time way to solve this problem, assuming has been computed to sufficient precision.

Subsections
William Stein 2012-09-24