Cryptography Reference
In-Depth Information
Lemma 16.1.9
The determinant of a lattice is independent of the choice of basis matrix B
and the choice of projection P.
Proof
Let
P
and
P
be two projection matrices corresponding to orthogonal bases
{
v
1
,...,
v
n
}
. Then, by Lemma
A.10.3
,
P
=
v
1
,...,
v
n
}
and
{
for
V
=
span
{
b
1
,...,
b
n
}
PW
for some orthogonal matrix
W
(hence, det(
W
)
=±
1). It follows that
|
det(
BP
)
|
does
not depend on the choice of
P
.
Let
B
and
B
be two basis matrices for a lattice
L
. Then
B
=
UB
where
U
is an
n
×
n
det(
B
P
)
matrix such that det(
U
)
=±
1. Then det(
L
)
=|
det(
BP
)
|=|
det(
UBP
)
|=|
.
|
We have seen that there are many different choices of basis for a given lattice
L
.A
fundamental problem is to compute a “nice” lattice basis for
L
; specifically one where the
vectors are relatively short and close to orthogonal. The following exercise shows that these
properties are intertwined.
2
Exercise 16.1.10
Let
L
be a rank 2 lattice in
R
and let
{
b
1
,
b
2
}
be a basis for
L
.
1. Show that
det(
L
)
=
b
1
b
2
|
sin(
θ
)
|
(16.1)
where
θ
is the angle between
b
1
and
b
2
.
2. Hence, deduce that the product
b
1
b
2
is minimised over all choices
{
b
1
,
b
2
}
of basis
for
L
when the angle
θ
is closest to
±
π/
2.
m
of rank
n
with basis matrix
B
.The
Gram
Definition 16.1.11
Let
L
be a lattice in
R
matrix
of
B
is
BB
T
.Thisisan
n
×
n
matrix whose (
i,j
)th entry is
b
i
,
b
j
.
m
of rank n with basis matrix B. Then
det(
L
)
L
emma 16.
1.12
Let L be a lattice in
R
=
det(
BB
T
)
.
n
. Then det(
L
)
2
det(
B
) det(
B
T
)
det(
BB
T
)
Proof
Consider first the case
m
=
=
=
=
det(
B
(
B
)
T
). Now, the (
i,j
)th entry
det((
b
i
,
b
j
)
i,j
). Hence, when
m>n
, det(
L
)
=
of
B
(
B
)
T
=
(
BP
)(
BP
)
T
is
, which is equal to the (
i,j
)th entry of
BB
T
by
b
i
P,
b
j
P
Lemma 16.1.5.
Note that an integer lattice of non-full rank may not have integer determinant.
2
whose determinant is not an
Exercise 16.1.13
Find an example of a lattice of rank 1 in
Z
integer.
m
and let
b
1
,...,
b
n
Lemma 16.1.14
Let
b
1
,...,
b
n
be an ordered basis for a lattice L in
R
=
i
=
1
b
i
be the Gram-Schmidt orthogonalisation. Then
det(
L
)
.
Proof
The case
m
=
n
is already proved in Lemma
A.10.8
. For the general case let
b
i
/
b
i
v
i
=
be the orthonormal basis required for the construction of the projection
P
.
Then
P
(
b
i
)
b
i
e
i
. Write
B
and
B
∗
for the
n
=
×
m
matrices formed by the rows
b
i
and
