Cryptography Reference
In-Depth Information
m
x
i
b
i
=
0
.
i
=
1
Otherwise, the
b
i
'saresaidtobe
linearly independent
.
The Gram determinant of
b
1
,...,
n
, denoted by
b
m
∈ R
Δ(
b
1
,...,
b
m
)
,isby
definition the determinant of the Gram matrix
b
j
1
≤
i
,
j
≤
m
. This real number
b
i
,
Δ(
0, and it turns out to be 0 if and only if the
b
i
's are linearly
dependent. The Gram determinant is invariant by any permutation of the
m
vectors,
and by any integral linear transformation of determinant
b
1
,...,
b
m
)
is always
≥
1 such as adding to one of
the vectors a linear combination of the others. The Gram determinant has a very useful
±
geometric interpretation: when the
b
i
's are linearly independent,
√
Δ(
b
1
,...,
b
m
)
is the
m
-dimensional volume of the parallelepiped spanned by the
b
i
's.
12.2.2 Lattices and Lattice Bases
n
For our purposes, a lattice will be any subgroup
L
of
for some
n
(such a
subgroup is sometimes called an integral lattice, to distinguish it from more general
definitions of a lattice). Examples include
(
Z
,
+
)
n
Z
itself, the zero lattice
{
0
}
, and the set
a
Z +
b
Z
of linear combinations of any two integers
a
,
b
∈ Z
(which is simply
gcd
(
a
,
b
)
Z
). For another example, consider
n
integers
a
1
,...,
a
n
, together with a
n
such that
i
=
1
a
i
x
i
modulus
M
. Then the set of all
(
x
1
,...,
x
n
)
∈ Z
≡
0
(
mod
M
)
n
.
is a lattice, as it is clearly a subgroup of
Z
n
. Denote by
L
Let
b
1
,...,
b
m
be arbitrary vectors in
Z
(
b
1
,...,
b
m
)
the set of all
integral linear combinations of the
b
i
's:
m
L
(
b
1
,...,
b
m
)
=
n
i
b
i
:
n
1
,...,
n
m
∈ Z
.
i
=
1
n
, and hence a lattice
L
, called the lattice
generated
or
spanned
by the
b
i
's. When the
b
i
's are linearly independent, we say that
This set is a subgroup of
Z
b
m
)
is a
basis
of the lattice
L
, in which case each lattice vector decomposes itself uniquely
as an integral linear combination of the
b
i
's.
Bases and sets of generators are useful for representing lattices, and for performing
computations. One will typically represent a lattice by some lattice basis, which can
itself be represented by a matrix with integer coefficients. If
(
b
1
,...,
(
b
1
,...,
b
m
)
is a basis
of
L
, with
b
i
=
(
b
i
,
1
,...,
b
i
,
n
)
, we will represent the lattice
L
=
L
(
b
1
,...,
b
m
)
by
the following matrix:
⎛
⎝
⎞
⎠
b
1
,
1
···
b
1
,
n
.
.
b
m
,
1
···
b
m
,
n
whose rows are the coordinates of the
b
i
's.
