Finding shortest non-zero vector $x$ satisfying $Ax=0 \pmod q$

Question

Let $n$, $m$, and $q$ be positive integers (with $m > n$), and $A$ be a matrix over $\mathbb{Z}_q^{n \times m}$. Using Mathematica, I want to find the shortest non-zero vectors $x \in \mathbb{Z}_q^m$ such that:

$$Ax=0 \pmod q$$

Note: By "shortest," I mean the vector with the smallest Euclidean norm. I'm not sure if this vector is unique. If it's not, I want a list of vectors with smallest Euclidean norm.

---

Example:

Let: $n=2, m=3, q=7, A = \left(\begin{matrix} 2 & 1 & 6\\ 1 & 3 & 1 \end{matrix} \right)$. Then, the following vectors are solutions to

{1,1,3} $\quad$ Norm = $\sqrt{11}$

{3,3,2} $\quad$ Norm = $\sqrt{22}$

{2,2,6} $\quad$ Norm = $\sqrt{44}$

{5,5,1} $\quad$ Norm = $\sqrt{51}$

{4,4,5} $\quad$ Norm = $\sqrt{57}$

{6,6,4} $\quad$ Norm = $\sqrt{88}$

Therefore, the vector {1,1,3} is the shortest solution.

---

PS: I used an exhaustive search to find the above solutions. My approach takes a long time for even small choices of $n$ and $m$, say $n=2, m=8$. Please offer an approach which can at least find solutions for such small parameters.

Edit: As Michael suggested in a comment, I demonstrate the "exhaustive search" code I used. I'm not proud of it at all, as I just wrote the code to find an example for this question.

A = RandomInteger[6, {2, 3}];
x = {a, b, c};
Table[
  If[Mod[A.x, 7] == {0, 0}, Print[{x, x // Norm}]], 
    {a, 0, 6}, {b, 0, 6}, {c, 0, 6}]

Answer 1

One way to approach this is to use the Null space of the matrix a, which is a basis for all elements x such that a.x=0. For the OPs problem, this can be done by first finding the null space:

a = {{2, 1, 6}, {1, 3, 1}};
n = First[NullSpace[a, Modulus -> 7]]

{5, 5, 1}

Now, observe that a.x=0 is true exactly when a.(c*x)=0, so it is possible to list all the answers (mod 7) to this problem by

Mod[# n, 7] & /@ Range[7]

{{5, 5, 1}, {3, 3, 2}, {1, 1, 3}, {6, 6, 4}, {4, 4, 5}, {2, 2, 6}}

To find the one with smallest norm, apply the norm to each element,

Norm /@ (Mod[# n, 7] & /@ Range[6])

{Sqrt[51], Sqrt[22], Sqrt[11], 2 Sqrt[22], Sqrt[57], 2 Sqrt[11]}

which gives the same answer as the OP found by search.

More generally, the NullSpace of a is a collection of $m-n$ vectors, and it will be necessary to search over all linear combinations of these $m-n$ vectors (mod $q$) for the one with the smallest norm. While this may still be large, it is certainly smaller than search over $m$ dimensions as in the brute force approach.

Answer 2

Using Solve helps a bit. If vars is the list of variables, then

Solve[A.vars == ConstantArray[0, n], vars, Modulus -> q]

finds all solutions in terms of parameters C[1], C[2], etc. depending on the dimension of the solution space.

Another bottleneck is computing the values of the general solution at all possible combinations of values for the parameters C[i] modulo q. The possible combinations can be computed with

Tuples[Range[0, q - 1], n]

where n is the number of parameters C[i]. The result is certainly reasonably fast for the small values of m, n, q mentioned in the question.

Finally Nearest will return the shortest nonzero vector (the zero vector having been deleted).

findSols[q_, A_] := 
 Module[{m, n, vars, x, sol, vals, params, vecs},
  {n, m} = Dimensions@A;
  vars = Array[x, m];
  sol = vars /. First @ Solve[A.vars == ConstantArray[0, n], vars, Modulus -> q];
  (* Print@sol; *) (*optional output*)
  params = Union@Cases[sol, _C, Infinity];
  (* Print@params; *) (*optional output*)
  vals = Transpose @ Tuples[Range[0, q - 1], Length@params];
  vecs = DeleteCases[
    Mod[#, q] &@ Transpose[sol /. MapThread[Rule, {params, vals}]], 
    ConstantArray[0, m]];
  Nearest[vecs, ConstantArray[0, m]]
  ]

Example in OP:

A = {{2, 1, 6}, {1, 3, 1}};
findSols[7, A] // Timing
(* {0.000675, {{1, 1, 3}}} *)

Additional example with $m=8$. (Over 117000 solutions, still less than a second.)

SeedRandom[2];
A = RandomInteger[6, {2, 8}]

findSols[7, A] // Timing
(* {{5, 6, 1, 6, 2, 2, 6, 5}, {2, 1, 5, 5, 0, 0, 6, 4}} *)
(* {0.289682, {{0, 1, 0, 0, 1, 0, 1, 0}, {0, 1, 0, 0, 0, 1, 1, 0}}} *)

Note that for q = 17 there will be over 24,000,000 solutions -- I killed the kernel when it went past 20GB.