arrow-left

All pages
gitbookPowered by GitBook
1 of 1

Loading...

HKZ reduced

hashtag
Definition

Let πi\pi_iπi​as the projection to the orthogonal complement of {bj}j=1i−1\left\{b_j\right\}_{j=1}^{i-1}{bj​}j=1i−1​.Then the basis is HKZ-reduced if it is size-reduced and ∣∣bi∗∣∣=λ1(πi(L))||b_i^*||=\lambda_1\left(\pi_i(L)\right)∣∣bi∗​∣∣=λ1​(πi​(L)). This definition gives us a relatively simple way to compute a HKZ-reduced basis by iteratively finding the shortest vector in orthogonal projections.

hashtag
Bounds

4i+3≤(∣∣bi∣∣λi(L))2≤i+34\frac4{i+3}\leq\left(\frac{||b_i||}{\lambda_i(L)}\right)^2\leq\frac{i+3}4i+34​≤(λi​(L)∣∣bi​∣∣​)2≤4i+3​