## Abstract

The LLL basis reduction algorithm was the first polynomial-time algorithm to compute a reduced basis of a given lattice, and hence also a short vector in the lattice. It thereby approximates an NP-hard problem where the approximation quality solely depends on the dimension of the lattice, but not the lattice itself. The algorithm has several applications in number theory, computer algebra and cryptography.

In this paper, we develop the first mechanized soundness proof of the LLL algorithm using Isabelle/HOL. We additionally integrate one application of LLL, namely a verified factorization algorithm for univariate integer polynomials which runs in polynomial time.

In this paper, we develop the first mechanized soundness proof of the LLL algorithm using Isabelle/HOL. We additionally integrate one application of LLL, namely a verified factorization algorithm for univariate integer polynomials which runs in polynomial time.

Original language | English |
---|---|

Title of host publication | Interactive Theorem Proving |

Subtitle of host publication | 9th International Conference, ITP 2018. Held as Part of the Federated Logic Conference, FloC 2018, Oxford, UK, July 9-12, 2018. Proceedings |

Editors | Jeremy Avigad, Assia Mahboubi |

Publisher | Springer |

Chapter | 10 |

Pages | 160-177 |

Number of pages | 18 |

ISBN (Electronic) | 978-3-319-94821-8 |

ISBN (Print) | 978-3-319-94820-1 |

DOIs | |

Publication status | Published - 4 Jul 2018 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer |

Volume | 10895 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |