ГлавнаяАрхивРеализация параллельного алгоритма поиска кратчайшего вектора в блочном методе Коркина — Золотарева

Реализация параллельного алгоритма поиска кратчайшего вектора в блочном методе Коркина — Золотарева | Прикладная дискретная математика. 2013. № 6 (Приложение).

Предложена параллельная реализация алгоритма Каннана для решения задач поиска кратчайшего и короткого векторов в решётке. Алгоритм может применяться как в составе блочного метода Коркина — Золотарева, так и независимо. Эксперимент показал трёхкратное ускорение работы блочного метода Коркина — Золотарева на четырёхъядерной системе.
  • Title Реализация параллельного алгоритма поиска кратчайшего вектора в блочном методе Коркина — Золотарева
  • Headline Реализация параллельного алгоритма поиска кратчайшего вектора в блочном методе Коркина — Золотарева
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 6 (Приложение)
  • Date:
  • DOI
Ключевые слова
решётка, проблема поиска кратчайшего вектора, блочный метод Коркина — Золотарева, shortest vector problem, SVP, block Korkin — Zolotarev, BKZ, lattices, parallel algorithms
Авторы
Ссылки
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.
Реализация параллельного алгоритма поиска кратчайшего вектора в блочном методе Коркина — Золотарева | Прикладная дискретная математика. 2013. № 6 (Приложение).
Реализация параллельного алгоритма поиска кратчайшего вектора в блочном методе Коркина — Золотарева | Прикладная дискретная математика. 2013. № 6 (Приложение).
Полнотекстовая версия