HomeIssuesImplementation of the parallel shortest vector enumeration in the block Korkin — Zolotarev method

Implementation of the parallel shortest vector enumeration in the block Korkin — Zolotarev method | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2013. № 6 (Приложение).

A parallel CPU implementation of Kannan algorithm is presented for solving shortest vector problem in block Korkin — Zolotarev lattice reduction method. The implementation is based on Native POSIX Thread Library and shows the linear decrease of runtime with the number of threads.
Download file
Counter downloads: 212
  • Title Implementation of the parallel shortest vector enumeration in the block Korkin — Zolotarev method
  • Headline Implementation of the parallel shortest vector enumeration in the block Korkin — Zolotarev method
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 6 (Приложение)
  • Date:
  • DOI
Keywords
решётка, проблема поиска кратчайшего вектора, блочный метод Коркина — Золотарева, shortest vector problem, SVP, block Korkin — Zolotarev, BKZ, lattices, parallel algorithms
Authors
References
Schnorr C. P. Block reduced lattice bases and successive minima // Combinatorics, Probability and Computing. 1994. V.3. P. 507-522.
Усатюк В. С. Реализация параллельных алгоритмов ортогонализации в задаче поиска кратчайшего базиса целочисленной решетки // Прикладная дискретная математика. Приложение. 2012. №5. С. 120-122.
Kannan R. Improved algorithms for integer programming and related lattice problems // Proc. STOC'83. New York, NY, USA, 1983. P. 193-206.
Hanrot G. and Stehle D. Improved analysis of Kannan's shortest lattice vector algorithm // LNCS. 2007. V. 4622. P. 170-186.
Kerrisk M. The Linux programming interface: a Linux and UNIX system programming handbook. San Francisko, USA: No Starch Press, 2010. 1552 p.
http://perso.ens-lyon.fr/damien.stehle/fplll/index.html — Приложение fplll. 2013.
http://www.latticechallenge.org/ideallattice-challenge/index.php — Ideal lattice challenge (SVP, Approx-SVP). 2012.
Implementation of the parallel shortest vector enumeration in the block Korkin — Zolotarev method | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2013. № 6 (Приложение).
Implementation of the parallel shortest vector enumeration in the block Korkin — Zolotarev method | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2013. № 6 (Приложение).
Download full-text version
Counter downloads: 1889
Download file