- #1

Peter_Newman

- 155

- 11

Hi together!

Say we have ## \Lambda_q{(A)} = \{\mathbf{x} \in \mathbb{Z}^m: \mathbf{x} = A^T\mathbf{s} \text{ mod }q \text{ for some } \mathbf{s} \in \mathbb{Z}^n_q\} ##.

How can we proof that this is a subgroup of ##\mathbb{Z}^m## ?

For a sufficient proof we need to check, closure, identity, inverse.

1.) (closure): Say ##x,y \in \Lambda_q{(A)}## by definition both are elements of ##\mathbb{Z}^m##, we need to show ##x+y \in \mathbb{Z}^m##, but does this follow directly from the definition, or is there more to be shown here?

2.) (identity): The identity is given with the zero element 0, we need to show ##x + 0 = x##, let ##x,0 \in \Lambda_q{(A)}## then for ##x+ 0## we have ##x + 0 = A^T\mathbf{s} \text{ mod }q## rewriting ##(x \text{ mod }q + 0 \text{ mod }q ) \text{ mod }q = A^T\mathbf{s} \text{ mod }q ##, i used linearity to rewrite the expression, by assumption, there must be an ##s## for each case. And moreover ##0 \text{ mod }q = 0##, so that ##x = A^T\mathbf{s} \text{ mod }q## follows and ##x + 0 = x## is shown.

3.) For the inverse I have no idea yet how to show this, but it should be ##-x##.

Thanks for any help!

Say we have ## \Lambda_q{(A)} = \{\mathbf{x} \in \mathbb{Z}^m: \mathbf{x} = A^T\mathbf{s} \text{ mod }q \text{ for some } \mathbf{s} \in \mathbb{Z}^n_q\} ##.

How can we proof that this is a subgroup of ##\mathbb{Z}^m## ?

For a sufficient proof we need to check, closure, identity, inverse.

1.) (closure): Say ##x,y \in \Lambda_q{(A)}## by definition both are elements of ##\mathbb{Z}^m##, we need to show ##x+y \in \mathbb{Z}^m##, but does this follow directly from the definition, or is there more to be shown here?

2.) (identity): The identity is given with the zero element 0, we need to show ##x + 0 = x##, let ##x,0 \in \Lambda_q{(A)}## then for ##x+ 0## we have ##x + 0 = A^T\mathbf{s} \text{ mod }q## rewriting ##(x \text{ mod }q + 0 \text{ mod }q ) \text{ mod }q = A^T\mathbf{s} \text{ mod }q ##, i used linearity to rewrite the expression, by assumption, there must be an ##s## for each case. And moreover ##0 \text{ mod }q = 0##, so that ##x = A^T\mathbf{s} \text{ mod }q## follows and ##x + 0 = x## is shown.

3.) For the inverse I have no idea yet how to show this, but it should be ##-x##.

Thanks for any help!

Last edited: