# Finding the basis of the transpose of a q-ary lattice

Given $$q$$ and a matrix $$A \in \mathbb{Z}_q^{n \times m}$$, the $$q$$-ary lattice is defined as $$\Lambda(A)=\{x \in \mathbb{Z}^m:Ax=0 \bmod q\}$$ An instance of a q-ary lattice and its short basis is computed in Generating short basis for hard random lattices. Once the short basis $$T_A$$ for $$\Lambda(A)$$ is given, computing the short vector $$s$$ in $$\Lambda (A)$$ is given in SamplePre algorithm.

Is it possible to find a short basis for $$\Lambda(A^T)$$, if we are given a short basis of $$\Lambda(A)$$?

Basically I want to find the short vector $$s^\prime$$ such that $$A^Ts^\prime=0 \bmod q$$.

• It is highly unlikely that such a short (nonzero) vector $s’$ exists, for a uniformly random $A$ and typical dimensions $m \gg n$. – Chris Peikert Jul 6 '19 at 14:48

If $$n then for almost all matrices $$A$$ the columns of $$A^T$$ will be linearly independent and in that case $$\Lambda(A^T)$$ is the lattice generated by the basis $$qI$$ (which is the shortest possible basis for this lattice).
• The basis would not be $qI$ because that does not include the columns of $A^T$. – Chris Peikert Jul 6 '19 at 14:50
• The notations are confusing, but the question asks about the kernel lattice of $A^T$, so I don't see why that lattice should include the columns of $A^T$. – LeoDucas Jul 9 '19 at 15:12