Cryptography Reference
In-Depth Information
Lemma 16.1.5
Let B be an n
×
m basis matrix for a lattice L where m>n. Then there
m
n
such that P
(
L
)
is a rank n lattice and
is a linear map P
:
R
→ R
P
(
v
)
=
v
for all
v
∈
L. Furthermore,
b
i
,
b
j
=
b
i
P,
b
j
P
for all
1
≤
i<j
≤
n.
If the linear map is represented by an m
×
n matrix P then a basis matrix for the image
of L under the projection P is the n
×
n matrix BP, which is invertible.
m
,
which has dimension
n
by assumption. Choose (perhaps by running the Gram-Schmidt
algorithm) a basis
v
1
,...,
v
n
for
V
that is orthonormal with respect to the inner product
in
Proof
Given the
n
×
m
basis matrix
B
with rows
b
i
, define
V
=
span
{
b
1
,...,
b
n
}⊂R
m
. Define the linear map
P
:
V
n
by
P
(
v
i
)
e
i
and
P
(
V
⊥
)
R
→ R
=
={
0
}
.For
v
=
i
=
1
x
i
=
=
i
=
1
x
i
v
i
∈
. Since the vectors
b
i
form
a basis for
V
, the vectors
b
i
P
are linearly independent. Hence,
BP
is an invertible matrix
and
P
(
L
) is a lattice of rank
n
.
V
we have
v
v
,
v
=
v
P
We can now prove the following fundamental result.
m matrices B and B
generate the same lattice L if and only if
B and B
are related by a
unimodular matrix
, i.e. B
=
Lemma 16.1.6
Two n
×
UB where U is an n
×
n matrix
with integer entries and determinant
±
1
.
) Every row of
B
is an integer linear combination
Proof
(
⇒
n
b
i
=
u
i,j
b
j
j
=
1
of the rows in
B
. This can be represented as
B
=
UB
for an
n
×
n
integer matrix
U
.
U
B
=
U
UB
. Now applying the projection
P
of Lemma
16.1.5
we have
Similarly,
B
=
U
UBP
and, since
BP
is invertible,
U
U
I
n
(the identity matrix). Since
U
and
U
BP
=
=
have integer entries it follows that det(
U
)
,
det(
U
)
. From det(
U
) det(
U
)
∈ Z
=
det(
I
n
)
=
1
it follows that det(
U
)
=±
1.
n
we have
x
B
:
x
n
n
(
⇐
) Since
U
is a permutation of
Z
{
∈ Z
}={
x
B
:
x
∈ Z
}
.
The Hermite normal form is defined in Section
A.11
. The following result is a direct
consequence of Lemma
16.1.6
and the remarks in Section
A.11
.
Lemma 16.1.7
If B is the basis matrix of a lattice L then the Hermite normal form of B
is also a basis matrix for L.
The
determinant
of a lattice
L
is the volume of the fundamental parallelepiped of any
basis
B
for
L
. When the lattice has full rank then using Definition
A.10.7
and Lemma
A.10.8
we have det(
L
)
=|
det(
B
)
|
. For the case
n<m
our definition uses Lemma
16.1.5
.
Definition 16.1.8
Let the notation be as above. The
determinant
(or
volume
) of a lattice
L
with basis matrix
B
is
|
det(
BP
)
|
, where
P
is a matrix representing the projection of
Lemma
16.1.5
.
