Implementation of the parallel shortest vector enumeration in the block Korkin — Zolotarev method.pdf Определение 1. Базис B = {b1,b2,... , bm} решётки L С приведён блочным методом Коркина — Золотарева (BKZ, Block Korkin — Zolotarev method [1]) с блоком в, если: 1) базис B приведён по длине; 2) || || = A1(Li), i = 1,..., m, где A1(Li) — длина кратчайшего вектора в обратной (сопряжённой) решётке Li, образованной ортогональным дополнением векторного пространства с базисом ..., bmin(i+e-1,m). BKZ-метод содержит две основные процедуры, которые могут быть распараллелены: ортогонализация базиса решётки и поиск кратчайшего вектора. Вопрос распараллеливания алгоритмов ортогонализации базиса рассматривался в работе [2]. Алгоритм поиска кратчайшего вектора представляет собой вариант метода ветвей и границ и заключается в переборе линейных комбинаций базисных векторов решётки, дающих вектор с нормой, ограниченной сверху некоторым положительным числом A, которое может уменьшаться в процессе поиска. На начальном этапе можно принять A = min -^/Ym ■ (det L)m , ||6*|| j- , где Ym — константа Эрмита; 6* — наименьший по норме вектор в исходном базисе решётки. Можно показать [3, 4], что координаты кратчайшего вектора удовлетворяют следующей системе неравенств: ^ A2, 2 \ы x; г—1xm) У 6m— 11 ^ A xm 2 (xm-1 + 6 (1) 2 (x1 + E x^ij)2 ^b1i=2 ^ A2 -E j, j=2 где {j}m_1 —ортогональный базис решётки, полученный из исходного базиса, например в результате процедуры ортогонализации Грама — Шмидта (через ^ j обозначены / m ч 2 2 коэффициенты Грама — Шмидта), j = (xj + Е xi^i,H ||&^|| . V i=j+1 ' Для решения системы (1) используем метод ветвей и границ, то есть организуем поиск решения в виде дерева. Корень дерева помечен переменной xm. Из корня выходит N ветвей, каждая из которых соответствует конкретному решению первого неравенства в (1). Пусть am — произвольное решение этого неравенства. Ветвь дерева поиска, соответствующую данному решению, будем называть ат-ветвью. Следующая вершина ат-ветви помечается переменной xm-1. Данная вершина является корнем дерева поиска для системы неравенств, полученной из (1) подстановкой xm = am. Если хотя бы одно из неравенств в (1) при этом не выполняется, то рассматриваемая ветвь отсекается (поскольку заведомо не содержит решения, дающего меньшую верхнюю границу, чем текущая). Описанный процесс по аналогии продолжается далее. Если найден вектор со значением нормы, меньшим текущей верхней границы, то значение верхней границы (рекорд) обновляется. Описанный алгоритм реализован с использованием потоковой модели NPTL (Native POSIX Thread Library [5]) под CentOS 6.3. Каждый из потоков осуществляет вычисление своей ат-ветви, исходящей из корня дерева. На задаче приведения 103-мерной решётки BKZ-методом с размером блока в = 52 на четырёх потоках, выполняемых на AMD Phenom 965/8 Gb DDR2-800, он продемонстрировал трёхкратное ускорение в сравнении с последовательным BKZ-решателем fplll-4.0.1 [6]. Предложенный алгоритм применялся в составе решателя, который занял 1-е и 6-е места на международных конкурсах поиска коротких векторов [7] для Г (т/2 + 1)1/т норм A = т ■ det(L)1/т и A = 1,05 1 ^ ' ^-det(L)1/т соответственно. yjn

Скачать электронную версию публикации