Алгоритм Теруи-Кашивабары-Ханаоки: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Dralles (обсуждение | вклад) |
Dralles (обсуждение | вклад) |
||
| Строка 5: | Строка 5: | ||
Алгоритм Теруи-Кашивабары-Ханаоки <ref>Parallel</ref> использует параллельные вычисления для решения задачи SVP. | Алгоритм Теруи-Кашивабары-Ханаоки <ref>Parallel</ref> использует параллельные вычисления для решения задачи SVP. | ||
В основу алгоритма лег алгоритм Фукаши-Кашивабары<ref>NNR</ref>. | В основу алгоритма лег алгоритм Фукаши-Кашивабары<ref>NNR</ref>. | ||
| + | |||
| + | ===Обозначения=== | ||
| + | Пусть <math>B = (\vec{b_1}, \ldots, \vec{b_n})</math> - базис решетки. | ||
| + | Соответствующие ортоганальные вектора Грама-Шмидта обозначим | ||
| + | <math>\vec{b_{1}^{*}}, \ldots, \vec{b_{1}^{*}} \in \mathbb{R}^{n}</math>. | ||
| + | Данные вектора определяются следующим образом: | ||
| + | <math>{ \vec{{b}_{i}^{*}} = \vec{b_i} - \sum_{j = 1}^{i - 1} \mu_{B, i, j} \vec{{b}_{j}^{*}} }</math>, где | ||
| + | <math>{ \mu_{B, i, j} = \langle \vec{b_i}, \vec{{b}_{j}^{*}} \rangle / \| \vec{{b}_{j}^{*}} \|^2 }</math>. | ||
| + | |||
| + | Определим отображение | ||
| + | <math>\pi_{B, i} : \mathbb{R}^n \rightarrow \mathscr{L}^{\perp}(\vec{b_1}, \ldots, \vec{b_{i - 1}})</math> | ||
| + | следующим образом: | ||
| + | :<math>\forall \vec{v} \in \mathbb{R}^n ~ \pi_{B, i}(\vec{v}) = \vec{v} - \sum_{j = 1}^{i - 1} v_{ j} \vec{{b}_{j}^{*}}, | ||
| + | \text{ где } v_{ i} = \langle \vec{v}, \vec{{b}_{j}^{*}} \rangle / \| \vec{{b}_{j}^{*}} \|^2.</math> | ||
| + | |||
| + | Через <math>\Lambda_{B, i}</math> будем обозначать следующее множество : | ||
| + | :<math>\Lambda_{B, i} = \pi_{B, i}(\Lambda) = \{ \pi_{B, i}(\vec{v}) ~|~ \vec{v} \in \Lambda \}</math> | ||
| + | |||
| + | ===Представление в виде натуральных чисел=== | ||
| + | |||
| + | Пусть <math>B = (\vec{b_1}, \ldots, \vec{b_n})</math> - базис решетки <math>\Lambda</math>. | ||
| + | ''Представлением в виде натуральных чисел'' вектора решетки | ||
| + | <math>\vec{v} = \sum_{i = 1}^{n} \nu_i \vec{{b}_{i}} \in \Lambda</math> в базисе <math>B</math> называется вектор | ||
| + | из неотрицательных целых чисел <math>(\mathfrak{n}_1, \ldots, \mathfrak{n}_n) \in \mathbb{N}^n</math>, такой, что | ||
| + | <math>{-(\mathfrak{n}_i + 1) / 2 < \nu_i \le - \mathfrak{n}_i / 2}</math> или | ||
| + | <math>{\mathfrak{n}_i / 2 < \nu_i \le (\mathfrak{n}_i + 1) / 2}</math>. | ||
| + | |||
| + | Пусть <math>B = (\vec{b_1}, \ldots, \vec{b_n})</math> - базис решетки <math>\Lambda</math> и | ||
| + | <math>{\vec{v} = \sum_{i = 1}^{n} \nu_i \vec{{b}_{i}} \in \Lambda}</math>. | ||
| + | Для любого <math>\vec{v} \in \Lambda</math> его представление в виде натуральных чисел определено однозначно, | ||
| + | а отображение <math>{\bf{n}}_{B} ~ \Lambda \rightarrow \mathbb{N}^{n}</math>, задающиеся как | ||
| + | <math>{\bf{n}}_{B}(v) = (\mathfrak{n}_1, \ldots, \mathfrak{n}_n)</math>, является биекцией<ref>NNR</ref>. | ||
| + | |||
| + | ===Индекс вставки=== | ||
| + | |||
| + | Пусть <math>B = (\vec{b_1}, \ldots, \vec{b_n})</math> - базис решетки <math>\Lambda</math>, <math>\vec{v} \in \Lambda</math>. | ||
| + | <math>\delta</math>''-индексом вставки'' вектора <math>\vec{v}</math> для базиса <math>B</math> назовем число | ||
| + | :<math>h_{\delta}(\vec{v}) = \min( \{ i ~ | ~ \| \pi_{B, i}(\vec{v}) \|^2 < \delta \| \vec{{b}^{*}_{i}} \|^2\} \cup \infty)</math> | ||
===Глобальные хранилища векторов=== | ===Глобальные хранилища векторов=== | ||
Версия 17:30, 19 октября 2019
Содержание
1 Свойства и структура алгоритма
1.1 Математическое описание алгоритма
Алгоритм Теруи-Кашивабары-Ханаоки [1] использует параллельные вычисления для решения задачи SVP. В основу алгоритма лег алгоритм Фукаши-Кашивабары[2].
1.1.1 Обозначения
Пусть B = (\vec{b_1}, \ldots, \vec{b_n}) - базис решетки. Соответствующие ортоганальные вектора Грама-Шмидта обозначим \vec{b_{1}^{*}}, \ldots, \vec{b_{1}^{*}} \in \mathbb{R}^{n}. Данные вектора определяются следующим образом: { \vec{{b}_{i}^{*}} = \vec{b_i} - \sum_{j = 1}^{i - 1} \mu_{B, i, j} \vec{{b}_{j}^{*}} }, где { \mu_{B, i, j} = \langle \vec{b_i}, \vec{{b}_{j}^{*}} \rangle / \| \vec{{b}_{j}^{*}} \|^2 }.
Определим отображение \pi_{B, i} : \mathbb{R}^n \rightarrow \mathscr{L}^{\perp}(\vec{b_1}, \ldots, \vec{b_{i - 1}}) следующим образом:
- \forall \vec{v} \in \mathbb{R}^n ~ \pi_{B, i}(\vec{v}) = \vec{v} - \sum_{j = 1}^{i - 1} v_{ j} \vec{{b}_{j}^{*}}, \text{ где } v_{ i} = \langle \vec{v}, \vec{{b}_{j}^{*}} \rangle / \| \vec{{b}_{j}^{*}} \|^2.
Через \Lambda_{B, i} будем обозначать следующее множество :
- \Lambda_{B, i} = \pi_{B, i}(\Lambda) = \{ \pi_{B, i}(\vec{v}) ~|~ \vec{v} \in \Lambda \}
1.1.2 Представление в виде натуральных чисел
Пусть B = (\vec{b_1}, \ldots, \vec{b_n}) - базис решетки \Lambda. Представлением в виде натуральных чисел вектора решетки \vec{v} = \sum_{i = 1}^{n} \nu_i \vec{{b}_{i}} \in \Lambda в базисе B называется вектор из неотрицательных целых чисел (\mathfrak{n}_1, \ldots, \mathfrak{n}_n) \in \mathbb{N}^n, такой, что {-(\mathfrak{n}_i + 1) / 2 \lt \nu_i \le - \mathfrak{n}_i / 2} или {\mathfrak{n}_i / 2 \lt \nu_i \le (\mathfrak{n}_i + 1) / 2}.
Пусть B = (\vec{b_1}, \ldots, \vec{b_n}) - базис решетки \Lambda и {\vec{v} = \sum_{i = 1}^{n} \nu_i \vec{{b}_{i}} \in \Lambda}. Для любого \vec{v} \in \Lambda его представление в виде натуральных чисел определено однозначно, а отображение {\bf{n}}_{B} ~ \Lambda \rightarrow \mathbb{N}^{n}, задающиеся как {\bf{n}}_{B}(v) = (\mathfrak{n}_1, \ldots, \mathfrak{n}_n), является биекцией[3].
1.1.3 Индекс вставки
Пусть B = (\vec{b_1}, \ldots, \vec{b_n}) - базис решетки \Lambda, \vec{v} \in \Lambda. \delta-индексом вставки вектора \vec{v} для базиса B назовем число
- h_{\delta}(\vec{v}) = \min( \{ i ~ | ~ \| \pi_{B, i}(\vec{v}) \|^2 \lt \delta \| \vec{{b}^{*}_{i}} \|^2\} \cup \infty)
1.1.4 Глобальные хранилища векторов
Для корректной работы алгоритма требуется два глобальных хранилища векторов, доступ к которым будут иметь все процессы. Первое из них назовем глобальным хранилищем запасных векторов, а второе - глобальным хранилищем соединительных векторов.
1.1.5 Генерация векторов решетки
На вход принимается базис решетки B и набор представлений в виде натуральных чисел векторов решетки. Далее генерируется набор векторов из данной решетки, которые соответствуют описанным выше представлениям. При этом понятно, что для разных базисов одной и той же решетки при одном и том же наборе представлений в виде натуральных чисел, будут сгенерированы разные вектора.
1.1.6 Редукция базиса
В алгоритме редукции базиса на вход поступают базис решетки B, набор S' представлений в виде натуральных чисел, целые числа \ell_{\mathrm{fc}}, \ell_{\mathrm{lc}} , вещественные значения \delta_{\mathrm{stock}}, \delta, \delta', \delta'' и целочисленное значение pui (process-unique information).
До начала работы алгоритма заводится массив переменных \delta'_i, i =\ell_{\mathrm{lc}} + 1, \ldots, n все элементы которого изначально равны \delta'.
На первом шаге генерируется набор векторов решетки V по набору S' и для каждого \vec{v} \in V вычисляется \delta_{\mathrm{stock}}-индекс вставки равный i. Если таковой удовлетворяет условию 1 \le i \le \ell_{\mathrm{fc}}, то вектор \vec{v} записывается в глобальное хранилище запасных векторов. Далее, по V строится набор V' = (\vec{v_1}, \ldots, \vec{v_N}), для всех векторов которого \delta-индекс вставки больше \ell_{\mathrm{lc}}.
На следующем шаге производится модификация исходного базиса решетки. Исходный базис B сохраняется в переменной B'. После чего ищется вектор \vec{v_i} \in V' для которого выполнены условия:
- j = h_{\delta'_{j}}(\vec{v}) \text{ где }\ell_{\mathrm{lc}} \lt j \le n,
- \| \vec{b_{j}^{*}} \|^2 - \| \pi_{B, i}(\vec{v_i}) \|^2 \rightarrow \max.
Если такой \vec{v_i} не найден, то алгоритм переходит к следующему шагу. Иначе к B применяется \delta-LLL алгоритм[4] по индексу j c вектором \vec{v_i}. Далее обновляются значения \delta'_k, {k = \ell_{\mathrm{lc}} + 1, \ldots, n} по следующим правилам:
- \delta'_{k} = \delta'_{k} - \delta'' \text{ для всех } k = \ell_{\mathrm{lc}} + 1, \ldots, j - 1,
- \delta'_{k} = \delta' \text{ для всех } k = j, \ldots, n.
Если (i + \text{pui}) \bmod N \equiv 0, то выполняется переход к шагу 3. В противном случае, к модифицированному базису B снова применяется шаг 2.
На третьем шаге проверяется условие B = B'. В случае успеха алгоритм завершает свою работу с результатом B. В противном случае алгоритм продолжает свою работу с шага 1.
1.1.7 Алгоритм Теруи-Кашивабары-Ханаоки
На вход алгшоритма поступют базис решетки B, наборы S и S' представлений в виде натуральных чисел, целые числа \ell_{\mathrm{fc}}, \ell_{\mathrm{lc}}, \ell_{\mathrm{link}}, вещественные значения \delta_{\mathrm{stock}}, \delta, \delta', \delta'', \Theta и целочисленное значение pui (process-unique information).
На первом шаге алгоритма в переменную B' сохраняется исходный базис B. После чего к B применяется алгоритм редукции базиса. Далее, генерируется набор векторов решетки V по базису B и набору представлений в виде натуральных чисел S. Для каждого \vec{v} \in V вычисляется \delta_{\mathrm{stock}}-индекс вставки равный i. Если таковой удовлетворяет условию 1 \le i \le \ell_{\mathrm{fc}}, то вектор \vec{v} записывается в глобальное хранилище запасных векторов.
На втором шаге вычисляется следующая оценочная функция:
- \mathrm{Eval}(B, \Theta) = \sum_{i = 1}^{n} \Theta^{i} \| \vec{b_{i}^{*}} \|^2.
После чего базис B модифицируется так, чтобы функция \mathrm{Eval}(B, \Theta) достигала на нем своего минимума. Чтобы этого достичь, к B применяется алгоритм \delta-LLL[5]по индексу i с вектором \vec{v}, где \vec{v} - вектор из глобального хранилища запасных векторов, для которого выполнено {h_{\delta_{\mathrm{stock}}}(\vec{v}) = i \le \ell_{\mathrm{fc}}}.
На третьем шаге сохраняем базисные вектора с индексами от 1 до \ell_\mathrm{link} в глобальное хранилище соединительных векторов. Далее выгружаем все глобальное хранилище соединительных векторов. Из векторов хранилища и векторов базиса B собираем наименьший базис решетки B'' в лексикографическом порядке. Затем заменяем базис B базисом B''. Если существует вектор \vec{v} из глобального хранилища запасных векторов такой, что \| \vec{v} \| \lt 1.05 \cdot (\Gamma(n / 2 + 1) \cdot \det(\Lambda))^{1 / n} / \sqrt{\pi}, то алгоритм возвращает вектор \vec{v}. Если B' = B, то алгоритм возвращает базис B. В противном случае алгоритм продолжает свою работу с шага 1.
