# Questions tagged [lenstra-lenstra-lovasz]

The Lenstra–Lenstra–Lovász (LLL) lattice basis reduction algorithm efficiently finds a short, nearly orthogonal lattice basis form an arbitrary one

18 questions
Filter by
Sorted by
Tagged with
2 votes
1 answer
78 views

### Algorithm to solve SVP (shortest vector problem) using LLL reduction

I'm trying to write a C++ program to solve the shortest vector problem. The program is given a basis of a vector space V and needs to find the shortest non-zero vector in V. Right now I'm using the ...
0 votes
0 answers
46 views

### Does randomization make a big difference in the output of the BKZ algorithm?

We all know that block Korkine-Zolotarev (BKZ) algorithm is essentially a deterministic lattice reduction algorithm. However, in the actual implementation, the BKZ algorithm contains some ...
• 179
2 votes
1 answer
109 views

### LLL on Knapsack-eque problem

Given integers $s_1, \dots , s_n$ and target integer $t$, I'm trying to find small integer coefficients $x_1, \dots , x_n$ such that: $$t \approx x_1 s_1 + \dots +x_ns_n$$ Taking inspiration from ...
• 123
3 votes
1 answer
180 views

### How does the lengths of the Gram-Schmidt orthogonal basis of a lattice basis change after lll reduction?

Assuming there is a lattice basis $B=\{b_1,...,b_n\}$, we use $B^*=\{b_1^*,...,b_n^*\}$ to denote the Gram-Schmidt orthogonal basis, where $b_i^*=\pi_i(b_i)$ and $\pi_i(b_i)$ denotes the projection of ...
• 75
1 vote
2 answers
147 views

### How "unorthogonal" can a LLL-reduced basis be?

I have been recently studying LLL-reduction. I get from the size condition and Lovasz condition that the basis are guaranteed to be somewhat orthogonal. But I couldn't figure out how orthogonal the ...
• 21
2 votes
2 answers
286 views

• 285