Korkine–Zolotarev lattice basis reduction algorithm
The Korkine–Zolotarev (KZ) lattice basis reduction algorithm is a lattice reduction algorithm invented by A. Korkine and G. Zolotareff in 1877.
Although the KZ reduction has exponential complexity versus the polynomial complexity of the LLL reduction algorithm, it is preferred for solving sequences of Closest Vector Problems (CVPs) in a lattice, where it may be more efficient.
References
- Korkine, A.; Zolotareff, G. (1877). "Sur les formes quadratiques positives".
{{cite journal}}: Cite journal requires|journal=(help)
- Lyu, Shanxiang; Ling, Cong (2017). "Boosted KZ and LLL Algorithms" (PDF).
{{cite journal}}: Cite journal requires|journal=(help)
- Wen, Jinming; Chang, Xiao-Wen (2018). "On the KZ Reduction" (PDF).
{{cite journal}}: Cite journal requires|journal=(help)
- Micciancio, Daniele; Goldwasser, Shafi (2002). Complexity of Lattice Problems. pp. 131–136.