3
$\begingroup$

Let $m$, $n$, and $q$ be positive integers, with $m \ge n$. Let $\mathbf{A} \in \mathbb{Z}^{n \times m}_q$ be a matrix.

Consider the following set: $S = \big\{ \mathbf{y} \in \mathbb{Z}^m \mid \mathbf{Ay} \equiv \mathbf{0} \pmod q \big\}$.

It can be easily shown that $S$ constitutes a lattice, because it is a discrete additive subgroup of $\mathbb{R}^m$.

I want to find the basis of this lattice. In other words, I want to find a matrix $\mathbf{B} \in \mathbb{Z}^{m \times m}$, such that the following holds: $S = \{\mathbf{Bx} \mid \mathbf{x} \in \mathbb{Z}^m \}$.

Let me give some examples:

  1. $q=2$, and $\mathbf{A} = [1,1]$ $\quad \xrightarrow{\qquad}\quad$ $\mathbf{B} = \left[ \begin{array}{cc} 2&1 \\ 0&1 \end{array} \right]$

  2. $q=3$, and $\mathbf{A} = \left[ \begin{array}{ccc} 0&1&2 \\ 2&0&1 \end{array} \right]$ $\quad \xrightarrow{\qquad}\quad$ $\mathbf{B} = \left[ \begin{array}{ccc} 3&0&1 \\ 0&3&1 \\ 0&0&1 \end{array} \right]$

  3. $q=4$, and $\mathbf{A} = \left[ \begin{array}{ccc} 0&2&3 \\ 3&1&2 \end{array} \right]$ $\quad \xrightarrow{\qquad}\quad$ $\mathbf{B} = \left[ \begin{array}{ccc} 4&2&1 \\ 0&2&1 \\ 0&0&2 \end{array} \right]$

Note that in all cases, $\mathbf{AB} =\mathbf{0} \pmod q$. However, $\mathbf{B}$ is not an arbitrary solution to this equivalence, since it must span $S$. For instance, in the example 1 above, matrix $\mathbf{\hat B} = \left[ \begin{array}{cc} 2&0\\ 0&2 \end{array} \right]$ satisfies $\mathbf{A \hat B} =\mathbf{0} \pmod 2$, but generates a sub-lattice of $S$.

Also note that if $\mathbf{B}$ is a basis of $S$, any other basis $\mathbf{\bar B}$ is also a basis of $S$, provided that there exists a unimodular matrix $\mathbf{U}$, for which $\mathbf{\bar B} = \mathbf{BU}$.

My questions:

  1. How to obtain $\mathbf{B}$ from $\mathbf{A}$ and $q$?
  2. Is it possible that $\mathbf{B}$ is not full rank, i.e. $\text{Rank}(\mathbf{B})< m$?
  3. Is there any difference between the case where $q$ is prime and the case where it is composite?

Side note: As far as I understood, $S$ is the solution space of a system of linear Diophantine equations. The solution has something to do with Hermite normal forms, but I can't figure out how.

  • 1
    There should be a way to work this out with ordinary linear algebra when $q$ is prime, as you are dealing with a field, every nonzero number has a multiplicative inverse. Other than that, i will need to think about it. The one article that comes to mind is George Leo Watson, Transformations of a Quadratic Form which do not increase the Class-Number, Proc. London Math. Soc. vol. 12 (1962) pages 577-587. Formulas 2.4 and 2.5, then Lemma 2 (ii) are related to your questions but may not be enough. Alright, I wrote "Smith Normal Form" at a few points on my copy, perhaps you should look that up.2012-08-16
  • 0
    @Will: Thanks for the answer. I found this paper: [explicit hard instances of the shortest vector problem](http://eprint.iacr.org/2008/333.pdf), which is trying to solve the same problem. Specially, section 4 describes how B is obtained from A (called Y and X in the paper). But I'm totally confused by their construction, since I can't apply it to any of my numerical examples. Could you please check that out?2012-08-17
  • 0
    @Will: Moreover, if you have any strategy to obtain B from A, given q is a prime, please write it out as an answer. It will be invaluable to me!2012-08-17
  • 0
    When you say that $B$ is not an *arbitrary* solution to $AB \equiv 0 \pmod{q},$ and then show an example of $\hat{B},$ did you notice that the example diag(2, 2) is $\hat{B} \equiv 0 \pmod{q}$? Does all non-zero (modulo $q$) solutions generate only a sub-lattice of S?2012-08-17
  • 0
    *Not sure if this useful.* By [linear algebra over the ring $\Bbb{Z}_q,$](http://books.google.ca/books/about/Linear_Algebra_over_Commutative_Rings.html?id=hkCgw_5wRq4C) we can find a *non-zero* nullspace basis matrix $N \in \mathbb{Z}_q^{m\times m}$ s.t. $A N \equiv 0 \pmod{q}.$ Then for any integer matrix $R,$ $N + qR$ is also a solution to the congruence. I'm not sure how to pick $R$ though, in order to make $N + qR$ a basis of $S$ (or at least to make $N + qR$ full rank & then invoke, say, LLL).2012-08-17
  • 1
    @Jennifer: Thanks for the answer. I checked your idea, but it apparently things are more complicated. Consider, for instance, the matrix $\mathbf{B'} = \left[ \begin{array}{cc} 3&2\\ 3&4 \end{array} \right]$. It is a solution for $\mathbf{AB'} \equiv 0 \pmod{2}$, and it's non-zero modulo 2. However, it generates a sub-lattice of $S$. (For example, the point $(1,1)$ is in the lattice $S$, but cannot be generated by $\mathbf{B'}$.)2012-08-17

3 Answers 3

1

Well, here is how it works over a field. We take $q=5.$ We will start with $A$ as a 2 by 4, $$ A \; = \; \left( \begin{array}{cccc} 2 & 3 & 4 & 1 \\ 3 & 4 & 0 & 1 \end{array} \right) $$ We begin a sequence of elementary row operations, first multiply the first row times 3 and the second by 2, $$ \left( \begin{array}{cccc} 1 & 4 & 2 & 3 \\ 1 & 3 & 0 & 2 \end{array} \right) $$ Next subtract row 1 from row 2. $$ \left( \begin{array}{cccc} 1 & 4 & 2 & 3 \\ 0 & 4 & 3 & 4 \end{array} \right) $$ then multiply the second row by 4, $$ \left( \begin{array}{cccc} 1 & 4 & 2 & 3 \\ 0 & 1 & 2 & 1 \end{array} \right) $$ Finally add row 2 to row 1, $$ \left( \begin{array}{cccc} 1 & 0 & 4 & 4 \\ 0 & 1 & 2 & 1 \end{array} \right). $$ This is the most favorable case. It allows us to place a little 2 by 2 identity matrix at the bottom when writing the null space we need $$ \left( \begin{array}{cc} ? & ? \\ ? & ? \\ 1 & 0 \\ 0 & 1 \end{array} \right) $$ which is then forced to become $$ \left( \begin{array}{cc} 1 & 1 \\ 3 & 4 \\ 1 & 0 \\ 0 & 1 \end{array} \right) $$ This can be readily filled in the way Buchmann, Lindner, Ruckert, Schneider demand at the bottom of page 2, $$ B \; = \; \left( \begin{array}{cccc} 5 & 0 & 1 & 1 \\ 0 & 5 & 3 & 4 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array} \right). $$ You can check that $AB \equiv 0 \pmod 5$ as the matrix of appropriate size.

What happens instead if the row echelon form comes out with staggered nontrivial 1's? Let us begin again with $$ A \; = \; \left( \begin{array}{cccc} 1 & 2 & 0 & 3 \\ 0 & 0 & 1 & 1 \end{array} \right) $$

It is first necessary to stagger the little 2 by 2 identity matrix in the same way, as in $$ \left( \begin{array}{cc} ? & ? \\ 1 & 0 \\ ? & ? \\ 0 & 1 \end{array} \right) $$ and forces us to the penultimate $$ \left( \begin{array}{cc} 3 & 2 \\ 1 & 0 \\ 0 & 4 \\ 0 & 1 \end{array} \right). $$ Note that it is impossible to just place this 4 by 2 as the final two columns of a 4 by 4, BLRS demand nonzero entries on the main diagonal. So what we do is simply stagger the columns with 5's in the same way, giving $$ B \; = \; \left( \begin{array}{cccc} 5 & 3 & 0 & 2 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 5 & 4 \\ 0 & 0 & 0 & 1 \end{array} \right). $$

  • 0
    Could you please give the full reference for Buchmann, Lindner, Ruckert, Schneider, page 2 that you are referring to? Thanks in advance!2015-01-11
  • 0
    @Heterotic, it was referred to by the person asking, in comment above, http://eprint.iacr.org/2008/333.pdf2015-01-11
  • 0
    thanks for that but I still cannot find what I was looking for. In particular, I am confused about how you fill in the ?? in the 4x2 matrices as well as how you go from the 4x2 to the 4x4 matrices. Is there any chance you could expand on these points or maybe suggest another reference where the algorithm is described? Thanks a lot!2015-01-11
  • 0
    @Heterotic, don't know why I would put in extra work on a post from two and a half years ago. If you clarify your posted question on lattices I can probably do something. As you want references, see Watson's first on transformations at http://zakuski.math.utsa.edu/~kap/forms.html2015-01-11
0

Even over a field, a fair amount goes into this. Here are two pages from Linear Algebra and Matrix Theory by Evar D. Nering, second edition:

enter image description here From a row-echelon form for your data matrix $A,$ one can readily find the null space as a certain number of columns by placing $1$'s in certain "free" positions and back-substituting to get the other positions.

Meanwhile, once you have that information, the square matrices you display above are not quite what Buchmann, Lindner, Ruckert, and Schneider want. At the bottom of page 2 they define their HNF for $B$ as being upper triangular as well, where the first several columns have merely a single $q$ on the diagonal element and otherwise $0$'s. So you were close.

Note that, over a field ($q$ prime) there is a well-defined notion of the rank of $A.$ The number of non-trivial columns of $B$ is $m-n,$ as you have illustrated above.

Anyway, I think everything about your problem is in ordinary linear algebra books for fields, then I recommend INTEGRAL MATRICES by Morris Newman.

  • 0
    > "the square matrices you display above are not quite what Buchmann, Lindner, Ruckert, and Schneider want." I converted my B matrices to HNF. Still, I don't see how Buchmann *et al.* algorithm can obtain these matrices.2012-08-18
  • 0
    BTW, Buchmann and Vollmer have a book called " Binary Quadratic Forms: An Algorithmic Approach." I'm reading [page 203](http://books.google.com/books?id=umGYD5jfDOcC&pg=PA203), which seems quite related...2012-08-18
0

Will Jagy has provided an instructive example but no formulae. I will write these here, in case they are still of any interest/use to anyone:

1) We start with the matrix A and we perform elementary row operations to bring it to the form $$A\sim\left[\begin{array}{c c} I |& C \end{array}\right].$$ We are allowed to do all operations $\mod q$.

2) A basis for the lattice $S$ is then given by the matrix $$B=\left[\begin{array}{c c} qI & -C\\ 0 & I\end{array}\right]$$

The above basis is in (almost) Hermite Normal Form. If we do want it in HNF all we have to do is add multiples of q to the entries of -C to bring them to the range $\{0,\cdots,q-1\}$.

In terms of terminology, the S lattice is (the complement of) a q-ary lattice.

The case where we are not able to bring A to the form in 1) is handled in Will Jagy's answer.