Geodesic
Implementation of the parallel shortest vector enumeration in the block Korkin–Zolotarev method
Prikladnaya Diskretnaya Matematika. Supplement, no. 6 (2013), pp. 130-131 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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.
Keywords: shortest vector problem, SVP, block Korkin–Zolotarev, lattices, parallel algorithms.
Mots-clés : BKZ 
@article{PDMA_2013_6_a57,
     author = {V. S. Usatyuk},
     title = {Implementation of the parallel shortest vector enumeration in the block {Korkin{\textendash}Zolotarev} method},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {130--131},
     year = {2013},
     number = {6},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2013_6_a57/}
}
TY  - JOUR
AU  - V. S. Usatyuk
TI  - Implementation of the parallel shortest vector enumeration in the block Korkin–Zolotarev method
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2013
SP  - 130
EP  - 131
IS  - 6
UR  - http://geodesic.mathdoc.fr/item/PDMA_2013_6_a57/
LA  - ru
ID  - PDMA_2013_6_a57
ER  - 
%0 Journal Article
%A V. S. Usatyuk
%T Implementation of the parallel shortest vector enumeration in the block Korkin–Zolotarev method
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2013
%P 130-131
%N 6
%U http://geodesic.mathdoc.fr/item/PDMA_2013_6_a57/
%G ru
%F PDMA_2013_6_a57
V. S. Usatyuk. Implementation of the parallel shortest vector enumeration in the block Korkin–Zolotarev method. Prikladnaya Diskretnaya Matematika. Supplement, no. 6 (2013), pp. 130-131. http://geodesic.mathdoc.fr/item/PDMA_2013_6_a57/

[1] Schnorr C. P., “Block reduced lattice bases and successive minima”, Combinatorics, Probability and Computing, 3 (1994), 507–522 | DOI | MR | Zbl

[2] Usatyuk V. S., “Realizatsiya parallelnykh algoritmov ortogonalizatsii v zadache poiska kratchaishego bazisa tselochislennoi reshetki”, Prikladnaya diskretnaya matematika. Prilozhenie, 2012, no. 5, 120–122

[3] Kannan R., “Improved algorithms for integer programming and related lattice problems”, Proc. STOC'83 (New York, NY, USA, 1983), 193–206 | Zbl

[4] Hanrot G. and Stehle D., “Improved analysis of Kannan's shortest lattice vector algorithm”, LNCS, 4622, 2007, 170–186 | MR | Zbl

[5] Kerrisk M., The Linux programming interface: a Linux and UNIX system programming handbook, No Starch Press, San Francisko, USA, 2010, 1552 pp.

[6] Prilozhenie fplll, , 2013 http://perso.ens-lyon.fr/damien.stehle/fplll/index.html

[7] Ideal lattice challenge (SVP, Approx-SVP), , 2012 http://www.latticechallenge.org/ideallattice-challenge/index.php