The implementation of the parallel shortest vector enumerate in the block Korkin-Zolotarev method

2013/04/06 by Usatyuk, Vasily, Vasily Usatyuk
Computer Science · Engineering · #Advanced Data Processing Techniques #Discrete Mathematics (cs.DM) #Electric Power Systems and Control #FOS: Computer and information sciences #cs.DM

paper · pdf · doi:10.48550/arxiv.1304.1900

3 pages, in Russian, Will appear in SIBECRYPT'13 conference

arxiv created 2013/04/06 · openalex publication_date 2013/04/06 · arxiv updated 2013/04/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This article present a parallel CPU implementation of Kannan algorithm for solving shortest vector problem in Block Korkin-Zolotarev lattice reduction method. Implementation based on Native POSIX Thread Library and show linear decrease of runtime from number of threads.

Related

• Block Korkin-Zolotarev algorithm generalization and their practical implementation (Russian)
• A hierarchy of polynomial time lattice basis reduction algorithms
• Upper and lower bound on the cardinality containing shortest vectors in a lattice reduced by block Korkin-Zolotarev method (Russian)
• Faster Lattice Enumeration
• LLL Algorithm for Lattice Basis Reduction