Skip to Main content Skip to Navigation
Journal articles

Approximating the densest sublattice from Rankin's inequality

Jianwei Li 1, 2 Phong Q. Nguyen 1, 2
2 CRYPT - Cryptanalyse
LIAMA - Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées, Inria Paris-Rocquencourt
Abstract : We present a higher-dimensional generalization of the Gama{Nguyen algorithm (STOC '08) for approximating the shortest vector problem in a lattice. This generalization approximates the densest sublattice by using a subroutine solving the exact problem in low dimension, such as the Dadush{Micciancio algorithm (SODA '13). Our approximation factor corresponds to a natural inequality on Rankin's constant derived from Rankin's inequality.
Document type :
Journal articles
Complete list of metadata
Contributor : Phong Q. Nguyen <>
Submitted on : Monday, August 25, 2014 - 11:33:19 AM
Last modification on : Wednesday, June 2, 2021 - 3:39:52 AM

Links full text




Jianwei Li, Phong Q. Nguyen. Approximating the densest sublattice from Rankin's inequality. LMS Journal of Computation and Mathematics, London Mathematical Society, 2014, Special Issue A (Algorithmic Number Theory Symposium XI), 7 (A), pp.92-111. ⟨10.1112/S1461157014000333⟩. ⟨hal-01057710⟩



Record views