Алгоритм приведения базиса решетки Коркина – Золотарева

Не путать с фильтром Колмогорова-Зурбенко .

Коркина -Золотарева ( KZ ) Алгоритм приведения решеточного базиса или Эрмита-Коркина-Золотарева ( HKZ ) алгоритм представляет собой редукции решетки алгоритм .

Для решеток в $\mathbb {R} ^{n}$ это дает решеточный базис с дефектом ортогональности не более $n^{n}$, в отличие от $2^{n^{2}/2}$ граница сокращения LLL . KZ имеет экспоненциальную сложность по сравнению с полиномиальной сложностью алгоритма сокращения LLL , однако он все же может быть предпочтительнее для решения нескольких задач ближайших векторов (CVP) в одной решетке, где он может быть более эффективным.

История

Определение KZ-редуцированного базиса было дано Александром Коркиным и Егором Ивановичем Золотаревым в 1877 году, это усиленная версия эрмитовой редукции . Первый алгоритм построения KZ-редуцированного базиса был предложен в 1983 году Каннаном.

Блочный алгоритм Коркина-Золотарева ( БКЗ ) был представлен в 1987 году.

Определение

KZ-редуцированный базис решетки определяется следующим образом:

Учитывая основу

$\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{n}\},$

определить его процесса Грама – Шмидта ортогональный базис

$\mathbf {B} ^{*}=\{\mathbf {b} _{1}^{*},\mathbf {b} _{2}^{*},\dots ,\mathbf {b} _{n}^{*}\},$

и коэффициенты Грамма-Шмидта

$\mu _{i,j}={\frac {\langle \mathbf {b} _{i},\mathbf {b} _{j}^{*}\rangle }{\langle \mathbf {b} _{j}^{*},\mathbf {b} _{j}^{*}\rangle }}$, для любого $1\leq j<i\leq n$.

Также определите функции проекции

$\pi _{i}(\mathbf {x} )=\sum _{j\geq i}{\frac {\langle \mathbf {x} ,\mathbf {b} _{j}^{*}\rangle }{\langle \mathbf {b} _{j}^{*},\mathbf {b} _{j}^{*}\rangle }}\mathbf {b} _{j}^{*}$

какой проект $\mathbf {x}$ ортогонально на промежутке $\mathbf {b} _{i}^{*},\cdots ,\mathbf {b} _{n}^{*}$.

Тогда основа $B$ является KZ-редуцированным, если выполнено следующее:

1. $\mathbf {b} _{i}^{*}$ — кратчайший ненулевой вектор в $\pi _{i}({\mathcal {L}}(\mathbf {B} ))$
2. Для всех $j<i$, $\left|\mu _{i,j}\right|\leq 1/2$

Обратите внимание, что первое условие можно рекурсивно переформулировать следующим образом: $\mathbf {b} _{1}$ – кратчайший вектор в решетке, а $\{\pi _{2}(\mathbf {b} _{2}),\cdots \pi _{2}(\mathbf {b} _{n})\}$ является KZ-редуцированным базисом решетки $\pi _{2}({\mathcal {L}}(\mathbf {B} ))$.

Также обратите внимание, что второе условие гарантирует, что сокращенный базис будет уменьшен по длине (добавление целого числа, кратного одному базисному вектору, к другому не уменьшит его длину); то же условие используется при уменьшении LLL.

Ссылки

• Коркин А.; Золотарёв Г. (1877). «Sur les образует квадратичные позитивы» . Математические летописи . 11 (2): 242–292. дои : 10.1007/BF01442667 . S2CID   121803621 .

• Лю, Шаньсян; Линг, Конг (2017). «Усиленные алгоритмы KZ и LLL». Транзакции IEEE по обработке сигналов . 65 (18): 4784–4796. arXiv : 1703.03303 . Бибкод : 2017ITSP...65.4784L . дои : 10.1109/TSP.2017.2708020 . S2CID   16832357 .

• Вэнь (2018). «О сокращении KZ» Вэнь , Цзиньмин ; Чанг, Сяо - . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

• Миччанчо, Даниэле; Гольдвассер, Шафи (2002). Сложность решеточных задач . стр. 131–136. дои : 10.1007/978-1-4615-0897-7 . ISBN  978-1-4613-5293-8 .

• Чжан, Вэнь; Цяо, Саньчжэн; Вэй, Имин (2012). «Алгоритмы редукции HKZ и Минковского для обнаружения MIMO с помощью редукции решетки» (PDF) . Транзакции IEEE по обработке сигналов . 60 (11): 5963. Бибкод : 2012ITSP...60.5963Z . дои : 10.1109/TSP.2012.2210708 . S2CID   5962834 .