Block Korkin-Zolotarev algorithm generalization and their practical implementation (Russian)

2012/10/24 by Vasiliy Usatyuk, Usatyuk, Vasiliy
Computer Science · Mathematics · #Advanced Algebra and Geometry #Coding theory and cryptography #Cryptography and Data Security #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM

paper · pdf · doi:10.48550/arxiv.1210.6502

arxiv created 2012/10/24 · openalex publication_date 2012/10/24 · arxiv updated 2012/10/25 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

Abstract

We propose a practical algorithm for block Korkin-Zolotarev reduction, a concept introduced by Schnorr, using CPU arbitrary length Householder QR-decomposition for orthogonalization and double precision OpenCL GPU Finke-Post shortest vector enumeration. Empirical tests was used on random lattices in the sense of Goldstein and Mayer.

Citations

• Factoring polynomials with rational coefficients

Related

• The implementation of the parallel shortest vector enumerate in the block Korkin-Zolotarev method
• Upper and lower bound on the cardinality containing shortest vectors in a lattice reduced by block Korkin-Zolotarev method (Russian)
• A hierarchy of polynomial time lattice basis reduction algorithms
• Worst-Case Hermite-Korkine-Zolotarev Reduced Lattice Bases
• Application of lattice reduction block Korkin-Zolotarev method to MIMO-decoding