We shall now concentrate on three applications of the LLL–algorithm. The first we give just as a bit of fun. We then turn to show how to use LLL to solve subset-sum problems. Subset-sum (or knapsack) problems are known to belong to the class of NP-complete problems, hence they are considered to be very hard in practice to solve. They are more than just of theoretical interest as one can build public-key cryptosystems from knapsack problems. We shall show that you can often break such a crypt osy stem using the LLL–algorithm.

Finally we turn our attention to determining whether a linear form can become exponentially small. It is this last application which forms the back-bone of the method to solve diophantine equations via Baker's theory of linear forms in logarithms. The LLL–algorithm reduces the astronomical bounds from Baker's theory to something more manageable.

A ‘fun’ application

We have seen, in V.I, how to produce rational numbers, p/q, with small numerator and denominator which are close to π. We can think of this as finding polynomials of degree one, i.e. qX – p, with small height and with a root close to π. One natural.generalization of this would be to try and look for polynomials of higher degree, with integer coefficients of small height, and which have a root very close to π.