Cryptography Reference
In-Depth Information
We define the
dimension
or
rank
of a lattice
L
, denoted by dim
(
L
)
, as the dimen-
sion
d
of the vector space span
. The dimension is the maximal number of linearly
independent lattice vectors. Any lattice basis of
L
must have exactly
d
elements. It
is clear that there exist
d
linearly independent lattice vectors, but such vectors do not
necessarily form a basis, as in to the case of vectors spaces. However, it is in fact
always possible to find a basis of
L
: in other words, lattices of dimension
d
in
(
L
)
n
Z
n
are exactly all subsets of
Z
of the form
L
=
L
(
b
1
,...,
b
d
)
n
.
for some linearly independent vectors
b
1
,...,
b
d
∈ Z
12.2.3 Lattice Volume
n
. An elementary
(
b
1
,...,
b
d
)
(
c
1
,...,
c
d
)
R
Let
and
be two bases of a lattice
L
in
×
=
(
u
i
,
j
)
1
≤
i
,
j
≤
d
∈
M
d
(
Z
)
result states that there exists a
d
d
integral matrix
U
=
j
=
1
u
i
,
j
b
j
for all 1
of determinant
±
1 such that
c
i
≤
i
≤
d
. It follows that the
Gram determinant of those two bases are equal:
Δ(
b
1
,...,
b
d
)
=
Δ(
c
1
,...,
c
d
)>
0
.
The
volume
of the lattice
L
is then defined as
1
/
2
vol
(
L
)
=
Δ(
b
1
,...,
b
d
)
,
which is independent of the choice of the lattice basis
. It corresponds
to the
d
-dimensional volume of the parallelepiped spanned by any basis. In the
important case of full-dimensional lattices where dim
(
b
1
,...,
b
d
)
n
,the
volume is also equal to the absolute value of the determinant of any lattice basis.
If an explicit basis is known, computing the lattice volume amounts to computing
a determinant. However, in some cases, we may not know any explicit lattice basis;
in such as cases, the following elementary result may be useful for computing the
volume nonetheless. If
L
1
and
L
2
are two lattices in
(
L
)
=
n
=
dim
(
R
)
n
Z
of the same dimension such
that
L
1
⊂
L
2
, then
L
2
/
L
1
is a finite group of order denoted by
[
L
2
:
L
1
]
which
satisfies
vol
(
L
1
)
=[
L
2
:
L
1
]·
vol
(
L
2
).
a
n
, together with a modulus
M
.We
have seen in Sect.
12.2.2
that the set
L
of all
For example, consider
n
integers
a
1
,...,
n
(
x
1
,...,
x
n
)
∈ Z
such that
i
=
1
a
i
x
i
≡
n
, but it is not obvious how to explicitly
write down a basis of
L
. However, note that
L
0
(
mod
M
)
is a lattice in
Z
n
⊂ Z
and that the dimension of
L
n
. It follows that vol
n
is
n
because
L
contains
M
Z
(
L
)
=[Z
:
L
]
. Furthermore, the
