On the KZ Reduction

DOI10.1109/TIT.2018.2868945MaRDI QIDQ4629944zbMATH OpenOpenAlexFDO

Authors Jinming Wen, Xiao-Wen Chang

Publication date 28 March 2019

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1702.08152

Mathematics Subject Classification ID

Canonical forms, reductions, classification (15A21) Integer programming (90C10) Quadratic programming (90C20) Decoding (94B35)

Abstract: The Korkine-Zolotareff (KZ) reduction is one of the often used reduction strategies for lattice decoding. In this paper, we first investigate some important properties of KZ reduced matrices. Specifically, we present a linear upper bound on the Hermit constant which is around $frac78$ times of the existing sharpest linear upper bound, and an upper bound on the KZ constant which is {em polynomially} smaller than the existing sharpest one. We also propose upper bounds on the lengths of the columns of KZ reduced matrices, and an upper bound on the orthogonality defect of KZ reduced matrices which are even {em polynomially and exponentially} smaller than those of boosted KZ reduced matrices, respectively. Then, we derive upper bounds on the magnitudes of the entries of any solution of a shortest vector problem (SVP) when its basis matrix is LLL reduced. These upper bounds are useful for analyzing the complexity and understanding numerical stability of the basis expansion in a KZ reduction algorithm. Finally, we propose a new KZ reduction algorithm by modifying the commonly used Schnorr-Euchner search strategy for solving SVPs and the basis expansion method proposed by Zhang {em et al.} Simulation results show that the new KZ reduction algorithm is much faster and more numerically reliable than the KZ reduction algorithm proposed by Zhang {em et al.}, especially when the basis matrix is ill conditioned.

Cited in

(7)

• Solitons for the modified (2 + 1)-dimensional Konopelchenko-Dubrovsky equations
• Sharper bounds on four lattice constants
• Euclidean minima of algebraic number fields
• A sharper lower bound on Rankin's constant
• A complete analysis of the BKZ lattice reduction algorithm
• On the ability to approximate k-DSP of HKZ, BKZ and slide reduction
• Simple sufficient conditions for integer stabilizability of discrete-time systems with relative degree one

This page was built for publication: On the KZ Reduction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4629944)