Implementation of the parallel shortest vector enumeration in the block Korkin — Zolotarev method | Applied Discrete Mathematics. Supplement. 2013. № 6.

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

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: 286

Keywords

решётка, проблема поиска кратчайшего вектора, блочный метод Коркина — Золотарева, shortest vector problem, SVP, block Korkin — Zolotarev, BKZ, lattices, parallel algorithms

Authors

Name	Organization	E-mail
Usatyuk V. S.	Bratsk State University	L@Lcrypto.com

Всего: 1

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.