3
$\begingroup$

I want to find an example of a basis of a lattice of dimension $n$ such that LLL algorithm can't find the shortest vector of the lattice, and such that the shortest vector of this lattice, say $b=c_1b_1+\cdots+c_nb_n$, has small $c_i$, i.e., $c_i \in \{-r,\ldots,r\}$ with small $r$.

Note that $b_i \in \mathbb{Z}^n$ and $c_i \in \mathbb{Z}$.

Such example must satisfy $\log_2(2(r+1)) \cdot n \leq 15$, say $n=5$ and $r=4$.

The idea here is to have a treatable value for $2^{\log_2(2(r+1)) \cdot n}$.

I can't find any lattice satisfying this.

Thanks in advance.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Given that LLL guarantees a vector within $2^{(n-1)/2}$ from optimal, and it tends to behave better than that in practice, $15$ is probably too short of a target. Increasing this limit to $25$ makes it easier to find examples. $\endgroup$ Commented Jun 22, 2016 at 1:42
  • $\begingroup$ Thanks for commenting, I agree, $2^{25}$ is "treatable", but instead of 5 minutes of testing all possibilities, with 25 we have to wait 3.5 days... I will try to increase $n$ or $r$ $\endgroup$ Commented Jun 22, 2016 at 22:04

1 Answer 1

Reset to default
7
$\begingroup$

Bruteforce appears to work well enough. The following Sage script finds an instance quickly:

from sage.libs.fplll.fplll import FP_LLL from sage.libs.fplll.fplll import gen_uniform n = 5 # dimension q = 16 # size of matrix entries while True: M = gen_uniform(n, n, q) L = M.LLL(delta=0.999) S = FP_LLL(L).shortest_vector(algorithm='proved') if min([ row.norm() for row in L]) != S.norm(): break print M print L print min([ row.norm() for row in L]) print S print S.norm()

As a concrete example, the lattice (column vectors) $$L = \begin{pmatrix} 16252& 5541& 48769& 2593& 22395\\ 2404& 46418& 5335& 59631& 29390\\ 41816& 27475& 56363& 50417& 62371\\ 27419& 53783& 1412& 42344& 55983\\ 62503& 52719& 22160& 3940& 64256\\ \end{pmatrix} $$ can be reduced with LLL ($\delta = 0.999$) to $$B= \begin{pmatrix} 1855& 31849 & -6182& -5480& 16007\\ 23160& -24484 & 2259& -11807& 10586\\ 29450& -465 & 8167& 2997& -19059\\ 10069& -8429 & 24671& -21117& -18320\\ 4328& -17879 & 30280& 29190& 24708\\ \end{pmatrix} $$ Yet, none of those vectors is the shortest. The shortest vector is $$(-19381, -7964, 16504, -24114, 739),$$ which can be written as $2L_0 - L_1 - L_2 + 2L_3 - L_4$, where $L_i$ is the $i$th row of $L$. So we have $n = 5$ and $r = 2$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for answering, seems nice, I wanted $\delta=3/4$ but $\delta=0.999$ will surely do. Obrigado (?) $\endgroup$ Commented Jun 23, 2016 at 5:38
  • $\begingroup$ I think, if L[0].norm() != S.norm(): , is enough, instead of, if min([ row.norm() for row in L]) != S.norm(): $\endgroup$ Commented Jun 24, 2016 at 8:44
  • 2
    $\begingroup$ L[0] is likely, but not guaranteed, to be the shortest vector in the basis. $\endgroup$ Commented Jun 24, 2016 at 19:33

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.