Techniques in Lattice Basis Reduction
DOI:
https://doi.org/10.32674/hgbk7442Keywords:
Lattice bases, unimodular matrices, right permutations, LLL algorithm, BKZ algorithm.Abstract
The shortest vector and closest vector problems, presently considered intractable, are algorithmic tasks that lie at the core of many theoretical and applied problems. We investigate the efficacy of new optimization techniques to be used along with the LLL algorithm. The techniques we propose are: i) hill climbing and ii) lattice diffusion-sub lattice fusion . The first technique relies on the sensitivity of LLL to permutations of the input basis B, and optimization ideas over the symmetric group Σm and the second technique relies on partitioning the lattice into sublattices, performing basis reduction on the sublattice blocks, fusing the sublattices, and repeating. Our approach provides better results for finding shortest vectors, than LLL and other traditional methods.
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Bal Kumar Khadka, Spyros S Magliveras (Author)

This work is licensed under a Creative Commons Attribution 4.0 International License.