Решетки и дуални решетки

Решетки в $\mathbb{R}^{n}$

Нека $B=\{\mathbf{b_{1}}, \mathbf{b_{2}}, ..., \mathbf{b_{m}}\}$ e множество от $m$ линейно независими векторa в $\mathbb{R}^{n}$ ($m<=n$). Тогава множеството вектори $L=\{\sum\limits_{i=1}^m c_i*\mathbf{b_i} : c_i \in \mathbb{Z}\}$ се нарича решетка с база $B$. Казано по друг начин, решетката е множеството от всички възможни линейни комбинации на векторите в $B$ с едно специално условие, коефициентите пред векторите в комбинацията трябва да са целочислени.

Геометрично, решетката представлява набор от точки, разположени така, че във всяка една посока, дадена от вектор на базата, те отстоят на равни разстояния една от друга.

Фигура 1. Решетка в $\mathbb{R}^{2}$. Червените точки представляват решетката, а векторите $\mathbf{b_{1}}$ и $\mathbf{b_{2}}$ представляват база на решетката.

Тъй като всеки вектор от решетката е линейна комбинация от векторите на базата, ние можем да го зададем и като произведение между матрица и вектор:

$c_1*\mathbf{b_{1}} + c_2*\mathbf{b_{2}} + ... + c_m*\mathbf{b_{m}} = \mathbf{b_{1}}*c_1 + \mathbf{b_{2}}*c_2 + ... + \mathbf{b_{m}}*c_m = \mathbf{B}*\mathbf{c}$

където $\mathbf{c}$ е вектор в $\mathbb{Z}^n$, а В е матрица, чиито колони са съставени от векторите в базата на решетката:

$\mathbf{B}=\begin{bmatrix} \mathbf{b_1} & \mathbf{b_2} & ... & \mathbf{b_m} \end{bmatrix}$

Това води до еквивалентно определение за решетка:

$L=\{\mathbf{B}\mathbf{c} : \mathbf{c} \in \mathbb{Z}^m \}$

Решетката има размерност и ранг. Ако L е решетка, формирана от $m<=n$ базови вектора в $\mathbb{R}^n$, казваме, че решетката има ранг $m$ и размерност $n$. От особен интерес за криптографията представляват решетките, за които $m=n$. Наричаме тези решетки "решетки от пълен ранг".

Базов паралелепипед на решетката

Векторите на базата формират m-мерен паралелепипед. Дефинираме детерминантата на матрицата $det(L)$ като обема на този паралелепипед. В случай, че решетката е от пълен ранг обемът на паралелепипеда е равен на абсолютната стойност на детерминантата на $B$, $det(L)=|det(B)|$