A Formalization of the LLL Basis Reduction Algorithm

Jose Divasón, Sebastiaan Joosten, René Thiemann, Akihisa Yamada

    Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

    4 Citations (Scopus)
    59 Downloads (Pure)

    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.
    Original languageEnglish
    Title of host publicationInteractive Theorem Proving
    Subtitle of host publication9th International Conference, ITP 2018. Held as Part of the Federated Logic Conference, FloC 2018, Oxford, UK, July 9-12, 2018. Proceedings
    EditorsJeremy Avigad, Assia Mahboubi
    PublisherSpringer
    Chapter10
    Pages160-177
    Number of pages18
    ISBN (Electronic)978-3-319-94821-8
    ISBN (Print)978-3-319-94820-1
    DOIs
    Publication statusPublished - 4 Jul 2018

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer
    Volume10895
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Fingerprint Dive into the research topics of 'A Formalization of the LLL Basis Reduction Algorithm'. Together they form a unique fingerprint.

    Cite this