Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Korkine–Zolotarev lattice basis reduction algorithm
open-in-new
<h2 id="history">History</h2> <p>The definition of a KZ-reduced basis was given by <a href="/facts/Aleksandr_Korkin/3oNhWrly">Aleksandr Korkin</a> and <a href="/facts/Yegor_Ivanovich_Zolotarev/pCXfRy4x">Yegor Ivanovich Zolotarev</a> in 1877, a strengthened version of <a href="/facts/Hermite_normal_form/uKELrY5K">Hermite reduction</a>. The first algorithm for constructing a KZ-reduced basis was given in 1983 by Kannan.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> </p><p>The block Korkine-Zolotarev (BKZ) algorithm was introduced in 1987.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> </p> <h2 id="definition">Definition</h2> <p>A KZ-reduced basis for a lattice is defined as follows:<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> </p><p>Given a <a href="/facts/Basis_(linear_algebra)/89IPoN6c">basis</a> </p> B = { b 1 , b 2 , … , b n } , {\displaystyle \mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{n}\},} <p>define its <a href="/facts/Gram%25E2%2580%2593Schmidt_process/vRNpld3t">Gram–Schmidt process</a> orthogonal basis </p> B ∗ = { b 1 ∗ , b 2 ∗ , … , b n ∗ } , {\displaystyle \mathbf {B} ^{*}=\{\mathbf {b} _{1}^{*},\mathbf {b} _{2}^{*},\dots ,\mathbf {b} _{n}^{*}\},} <p>and the Gram-Schmidt coefficients </p> μ i , j = ⟨ b i , b j ∗ ⟩ ⟨ b j ∗ , b j ∗ ⟩ {\displaystyle \mu _{i,j}={\frac {\langle \mathbf {b} _{i},\mathbf {b} _{j}^{*}\rangle }{\langle \mathbf {b} _{j}^{*},\mathbf {b} _{j}^{*}\rangle }}} , for any 1 ≤ j < i ≤ n {\displaystyle 1\leq j<i\leq n} . <p>Also define projection functions </p> π i ( x ) = ∑ j ≥ i ⟨ x , b j ∗ ⟩ ⟨ b j ∗ , b j ∗ ⟩ b j ∗ {\displaystyle \pi _{i}(\mathbf {x} )=\sum _{j\geq i}{\frac {\langle \mathbf {x} ,\mathbf {b} _{j}^{*}\rangle }{\langle \mathbf {b} _{j}^{*},\mathbf {b} _{j}^{*}\rangle }}\mathbf {b} _{j}^{*}} <p>which project x {\displaystyle \mathbf {x} } orthogonally onto the span of b i ∗ , ⋯ , b n ∗ {\displaystyle \mathbf {b} _{i}^{*},\cdots ,\mathbf {b} _{n}^{*}} . </p><p>Then the basis B {\displaystyle B} is KZ-reduced if the following holds: </p> <ol><li> b i ∗ {\displaystyle \mathbf {b} _{i}^{*}} is the shortest nonzero vector in π i ( L ( B ) ) {\displaystyle \pi _{i}({\mathcal {L}}(\mathbf {B} ))} </li> <li>For all j < i {\displaystyle j<i} , | μ i , j | ≤ 1 / 2 {\displaystyle \left|\mu _{i,j}\right|\leq 1/2} </li></ol> <p>Note that the first condition can be reformulated recursively as stating that b 1 {\displaystyle \mathbf {b} _{1}} is a shortest vector in the lattice, and { π 2 ( b 2 ) , ⋯ π 2 ( b n ) } {\displaystyle \{\pi _{2}(\mathbf {b} _{2}),\cdots \pi _{2}(\mathbf {b} _{n})\}} is a KZ-reduced basis for the lattice π 2 ( L ( B ) ) {\displaystyle \pi _{2}({\mathcal {L}}(\mathbf {B} ))} . </p><p>Also note that the second condition guarantees that the reduced basis is length-reduced (adding an integer multiple of one basis vector to another will not decrease its length); the same condition is used in the LLL reduction. </p> <h2 id="notes">Notes</h2> <ul><li>Korkine, A.; Zolotareff, G. (1877). <a href="https://zenodo.org/record/1896288">"Sur les formes quadratiques positives"</a>. <i>Mathematische Annalen</i>. 11 (2): 242–292. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF01442667">10.1007/BF01442667</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:121803621">121803621</a>.</li></ul> <ul><li>Lyu, Shanxiang; Ling, Cong (2017). "Boosted KZ and LLL Algorithms". <i>IEEE Transactions on Signal Processing</i>. 65 (18): 4784–4796. <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/1703.03303">1703.03303</a>. <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/2017ITSP...65.4784L">2017ITSP...65.4784L</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1109%2FTSP.2017.2708020">10.1109/TSP.2017.2708020</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:16832357">16832357</a>.</li></ul> <ul><li>Wen, Jinming; Chang, Xiao-Wen (2018). "On the KZ Reduction". <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/1702.08152">1702.08152</a>. {{cite journal}}: Cite journal requires |journal= (help)</li></ul> <ul><li>Micciancio, Daniele; Goldwasser, Shafi (2002). <i>Complexity of Lattice Problems</i>. pp. 131–136. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-1-4615-0897-7">10.1007/978-1-4615-0897-7</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-1-4613-5293-8.</li></ul> <ul><li>Zhang, Wen; Qiao, Sanzheng; Wei, Yimin (2012). <a href="http://www.cas.mcmaster.ca/~qiao/publications/ZQW12a.pdf">"HKZ and Minkowski Reduction Algorithms for Lattice-Reduction-Aided MIMO Detection"</a> (PDF). <i>IEEE Transactions on Signal Processing</i>. 60 (11): 5963. <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/2012ITSP...60.5963Z">2012ITSP...60.5963Z</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1109%2FTSP.2012.2210708">10.1109/TSP.2012.2210708</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:5962834">5962834</a>.</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>https://sites.math.washington.edu/~rothvoss/lecturenotes/IntOpt-and-Lattices.pdf, pp. 18-19 <a href="https://sites.math.washington.edu/~rothvoss/lecturenotes/IntOpt-and-Lattices.pdf" target="_blank">https://sites.math.washington.edu/~rothvoss/lecturenotes/IntOpt-and-Lattices.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Zhang et al 2012, p.1 <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Yasuda, Masaya (2021). "A Survey of Solving SVP Algorithms and Recent Strategies for Solving the SVP Challenge". International Symposium on Mathematics, Quantum Theory, and Cryptography. Mathematics for Industry. Vol. 33. pp. 189–207. doi:10.1007/978-981-15-5191-8_15. ISBN 978-981-15-5190-1. S2CID 226333525. <a href="978-981-15-5190-1" target="_blank">978-981-15-5190-1</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Micciancio & Goldwasser, p.133, definition 7.8 <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> </ol>