Timeline for Main problems on lattice-basis reduction algorithms (such as LLL)?
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 30, 2013 at 3:33 | comment | added | Daniele Micciancio | The constant in (1.4) cannot be set to less than 1/2. Choosing values higher than 1/2 can help with numerical stability (when using floating point numbers), but other than that 1/2 is the optimal value. The constant in (1.5) can be set to $\approx 1$, but this only improves the approximation factor to $(2/\sqrt{3})^{n}$. In order to get $(1+\epsilon)^n$ approximation you need better algorithms than LLL. (E.g., Schnorr's.) | |
| Sep 30, 2013 at 3:26 | comment | added | Daniele Micciancio | The constant in (1.4) cannot be set to less than 1/2. | |
| Sep 7, 2013 at 8:55 | history | answered | domotorp | CC BY-SA 3.0 |