0
$\begingroup$

I understand the LLL algorithm for finding approximate shortest vector in $\mathbb{Z}$-lattices (where the norm function is either $\ell_\infty$ or $\ell_2$), as well as finding the shortest vector in $\mathbb{F}_q[X]$-lattices (where $\mathbb{F}_q$ is a finite field, and the norm function is maximum of the component degrees).

Is there a standard/well-studied norm function for $\mathbb{Z}[X]$-lattices, and known results about the complexity of the LLL algorithm for such lattices?

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ a Z[X] lattice is a Z-lattice, just consider the lattice of coefficients of polynomials $\endgroup$ Commented May 1 at 12:31
  • $\begingroup$ Sure, but this will not account for the $\mathbb{Z}[X]$-module structure. For instance, the space of all bivariate polynomials in $\mathbb{Z}[X,Y]$ with $Y$-degree at most $k$, is a rank-($k+1$) lattice over $\mathbb{Z}[X]$, but it is an infinite dimensional $\mathbb{Z}$-lattice. My motivation is the known uses of LLL algorithms for $\mathbb{F}_q[X]$-lattices, for instance, in arxiv.org/abs/1008.1284 . I wish to know if there are similar useful instances of LLL algorithm applied to $\mathbb{Z}[X]$-lattices. $\endgroup$ Commented May 2 at 8:42
  • $\begingroup$ There are “module LLL” algorithms, see this, for example. $\endgroup$ Commented Jul 27 at 0:00

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.