LLL Algorithm and it’s Application in Diophantine Approximation and Polynomial Factorization

Abstract

This thesis presents an expository study of the Lenstra–Lenstra–Lov´asz (LLL) algorithm and its important applications in Diophantine approximation and polynomial factorization. The LLL algorithm is a fundamental lattice basis reduction method that produces short and nearly orthogonal basis vectors in polynomial time, making it a powerful tool in computational number theory and algebra. Although the algorithm does not solve the Shortest Vector Problem exactly, it provides an efficient approximation by finding sufficiently short lattice vectors and reduced bases. Further, the thesis explores applications of the LLL algorithm in Diophantine approximation, particularly in simultaneous rational approximation and problems involving integer relations. Its role in polynomial factorization is also examined, with emphasis on the factorization of polynomials over integers through lattice-based methods. Illustrative examples are included to demonstrate the theoretical and practical effectiveness of the algorithm.