Алгоритм Теруи-Кашивабары-Ханаоки

Свойства и структура алгоритма

Математическое описание алгоритма

Алгоритм Теру-Кашивабары-Ханаоки использует параллельные вычисления для решения задачи SVP. В основу алгоритма лег алгоритм Фукаши-Кашивабары.

Глобальные хранилища векторов

Для корректной работы алгоритма требуется два глобальных хранилища векторов, доступ к которым будут иметь все процессы. Первое из них назовем глобальным хранилищем запасных векторов, а второе - глобальным хранилищем соединительных векторов.

Генерация векторов решетки

На вход принимается базис решетки [math]\displaystyle{ B }[/math] и набор представлений в виде натуральных чисел векторов решетки. Далее генерируется набор векторов из данной решетки, которые соответствуют описанным выше представлениям. При этом понятно, что для разных базисов одной и той же решетки при одном и том же наборе представлений в виде натуральных чисел, будут сгенерированы разные вектора.

Редукция базиса

В алгоритме редукции базиса на вход поступают базис решетки [math]\displaystyle{ B }[/math], набор [math]\displaystyle{ S' }[/math] представлений в виде натуральных чисел, целые числа [math]\displaystyle{ \ell_{\mathrm{fc}}, \ell_{\mathrm{lc}} }[/math], вещественные значения [math]\displaystyle{ \delta_{\mathrm{stock}}, \delta, \delta', \delta'' }[/math] и целочисленное значение pui (process-unique information).

До начала работы алгоритма заводится массив переменных [math]\displaystyle{ \delta'_i, i =\ell_{\mathrm{lc}} + 1, \ldots, n }[/math] все элементы которого изначально равны [math]\displaystyle{ \delta' }[/math].

На первом шаге генерируется набор векторов решетки [math]\displaystyle{ V }[/math] по набору [math]\displaystyle{ S' }[/math] и для каждого [math]\displaystyle{ \vec{v} \in V }[/math] вычисляется [math]\displaystyle{ \delta_{\mathrm{stock}} }[/math]-индекс вставки равный [math]\displaystyle{ i }[/math]. Если таковой удовлетворяет условию [math]\displaystyle{ 1 \le i \le \ell_{\mathrm{fc}} }[/math], то вектор [math]\displaystyle{ \vec{v} }[/math] записывается в глобальное хранилище запасных векторов. Далее, по [math]\displaystyle{ V }[/math] строится набор [math]\displaystyle{ V' = (\vec{v_1}, \ldots, \vec{v_N}) }[/math], для всех векторов которого [math]\displaystyle{ \delta }[/math]-индекс вставки больше [math]\displaystyle{ \ell_{\mathrm{lc}} }[/math].

На следующем шаге производится модификация исходного базиса решетки. Исходный базис [math]\displaystyle{ B }[/math] сохраняется в переменной [math]\displaystyle{ B' }[/math]. После чего ищется вектор [math]\displaystyle{ \vec{v_i} \in V' }[/math] для которого выполнены условия:

[math]\displaystyle{ j = h_{\delta'_{j}}(\vec{v}) \text{ где }\ell_{\mathrm{lc}} \lt j \le n, }[/math]

[math]\displaystyle{ \| \vec{b_{j}^{*}} \|^2 - \| \pi_{B, i}(\vec{v_i}) \|^2 \rightarrow \max. }[/math]

Если такой [math]\displaystyle{ \vec{v_i} }[/math] не найден, то алгоритм переходит к следующему шагу. Иначе к [math]\displaystyle{ B }[/math] применяется [math]\displaystyle{ \delta }[/math]-LLL алгоритм по индексу [math]\displaystyle{ j }[/math] c вектором [math]\displaystyle{ \vec{v_i} }[/math]. Далее обновляются значения [math]\displaystyle{ \delta'_k, {k = \ell_{\mathrm{lc}} + 1, \ldots, n} }[/math] по следующим правилам:

[math]\displaystyle{ \delta'_{k} = \delta'_{k} - \delta'' \text{ для всех } k = \ell_{\mathrm{lc}} + 1, \ldots, j - 1, }[/math]

[math]\displaystyle{ \delta'_{k} = \delta' \text{ для всех } k = j, \ldots, n. }[/math]

Если [math]\displaystyle{ (i + \text{pui}) \bmod N \equiv 0 }[/math], то выполняется переход к шагу 3. В противном случае, к модифицированному базису [math]\displaystyle{ B }[/math] снова применяется шаг 2.

На третьем шаге проверяется условие [math]\displaystyle{ B = B' }[/math]. В случае успеха алгоритм завершает свою работу с результатом [math]\displaystyle{ B }[/math]. В противном случае алгоритм продолжает свою работу с шага 1.

Алгоритм Теруи-Кашивабары-Ханаоки

На вход алгшоритма поступют базис решетки [math]\displaystyle{ B }[/math], наборы [math]\displaystyle{ S }[/math] и [math]\displaystyle{ S' }[/math] представлений в виде натуральных чисел, целые числа [math]\displaystyle{ \ell_{\mathrm{fc}}, \ell_{\mathrm{lc}}, \ell_{\mathrm{link}} }[/math], вещественные значения [math]\displaystyle{ \delta_{\mathrm{stock}}, \delta, \delta', \delta'', \Theta }[/math] и целочисленное значение pui (process-unique information).

На первом шаге алгоритма в переменную [math]\displaystyle{ B' }[/math] сохраняется исходный базис [math]\displaystyle{ B }[/math]. После чего к [math]\displaystyle{ B }[/math] применяется алгоритм редукции базиса. Далее, генерируется набор векторов решетки [math]\displaystyle{ V }[/math] по базису [math]\displaystyle{ B }[/math] и набору представлений в виде натуральных чисел [math]\displaystyle{ S }[/math]. Для каждого [math]\displaystyle{ \vec{v} \in V }[/math] вычисляется [math]\displaystyle{ \delta_{\mathrm{stock}} }[/math]-индекс вставки равный [math]\displaystyle{ i }[/math]. Если таковой удовлетворяет условию [math]\displaystyle{ 1 \le i \le \ell_{\mathrm{fc}} }[/math], то вектор [math]\displaystyle{ \vec{v} }[/math] записывается в глобальное хранилище запасных векторов.

На втором шаге вычисляется следующая оценочная функция:

[math]\displaystyle{ \mathrm{Eval}(B, \Theta) = \sum_{i = 1}^{n} \Theta^{i} \| \vec{b_{i}^{*}} \|^2. }[/math]

После чего базис [math]\displaystyle{ B }[/math] модифицируется так, чтобы функция [math]\displaystyle{ \mathrm{Eval}(B, \Theta) }[/math] достигала на нем своего минимума. Чтобы этого достичь, к [math]\displaystyle{ B }[/math] применяется алгоритм [math]\displaystyle{ \delta }[/math]-LLL по индексу [math]\displaystyle{ i }[/math] с вектором [math]\displaystyle{ \vec{v} }[/math], где [math]\displaystyle{ \vec{v} }[/math] - вектор из глобального хранилища запасных векторов, для которого выполнено [math]\displaystyle{ {h_{\delta_{\mathrm{stock}}}(\vec{v}) = i \le \ell_{\mathrm{fc}}} }[/math].

На третьем шаге сохраняем базисные вектора с индексами от [math]\displaystyle{ 1 }[/math] до [math]\displaystyle{ \ell_\mathrm{link} }[/math] в глобальное хранилище соединительных векторов. Далее выгружаем все глобальное хранилище соединительных векторов. Из векторов хранилища и векторов базиса [math]\displaystyle{ B }[/math] собираем наименьший базис решетки [math]\displaystyle{ B'' }[/math] в лексикографическом порядке. Затем заменяем базис [math]\displaystyle{ B }[/math] базисом [math]\displaystyle{ B'' }[/math]. Если существует вектор [math]\displaystyle{ \vec{v} }[/math] из глобального хранилища запасных векторов такой, что [math]\displaystyle{ \| \vec{v} \| \lt 1.05 \cdot (\Gamma(n / 2 + 1) \cdot \det(\Lambda))^{1 / n} / \sqrt{\pi} }[/math], то алгоритм возвращает вектор [math]\displaystyle{ \vec{v} }[/math]. Если [math]\displaystyle{ B' = B }[/math], то алгоритм возвращает базис [math]\displaystyle{ B }[/math]. В противном случае алгоритм продолжает свою работу с шага 1.