1.3. Các heuristic cho lattice

Hai phương pháp heuristic thường được dùng là Gaussian Heuristic (GH) và Geometric Series Assumption (GSA).

1.3.1. Gaussian Heuristic

GH là một ước lượng của \(\lambda_1(\mathcal{L})\). Mật độ các điểm là \(1 / \det(\mathcal{L})\), vì vậy trong một quả cầu bán kính \(r\) ta kỳ vọng có khoảng \(v_n \cdot r^n / \det(\mathcal{L})\) điểm lattice, trong đó \(v_n\) là thể tích quả cầu đơn vị \(n\) chiều.

Cụ thể, \(v_n \lambda_1^n / \det(\mathcal{L}) \approx 1\), do đó \(\lambda_1 \approx (\det(\mathcal{L}) / v_n)^{1/n}\).

Vì thể tích quả cầu đơn vị là:

\[v_n \approx \dfrac{1}{\sqrt{n \pi}} \left( \dfrac{2 \pi e}{n} \right)^{n/2}\]

GH suy ra:

\[\lambda_1 \approx \det(\mathcal{L})^{1/n} \sqrt{\dfrac{n}{2 \pi e}}.\]

1.3.2. Geometric Series Assumption

GSA mô hình hóa độ dài các vector Gram--Schmidt của một cơ sở đã rút gọn như một cấp số nhân. Nếu \(\bm{b}_1^*, \ldots, \bm{b}_n^*\) là các vector Gram--Schmidt, ta giả sử tồn tại \(r \in (0, 1)\) sao cho

\[\lVert \bm{b}_{i+1}^* \rVert^2 \approx r \lVert \bm{b}_i^* \rVert^2.\]

Vì \(\prod_{i=1}^n \lVert \bm{b}_i^* \rVert = \det(\mathcal{L})\), giả định này cho phép ước lượng toàn bộ profile Gram--Schmidt từ định thức và hệ số \(r\). Trong phân tích BKZ, \(r\) thường được biểu diễn qua root-Hermite factor \(\delta_0\):

\[\lVert \bm{b}_i^* \rVert \approx \delta_0^{\,n-2i+1} \det(\mathcal{L})^{1/n}.\]

GH ước lượng độ dài vector ngắn nhất, còn GSA ước lượng hình dạng của cả cơ sở sau rút gọn; hai heuristic thường được dùng cùng nhau khi đánh giá chi phí tấn công lattice.