Cryptography Reference
In-Depth Information
b
i
respectively. It follows that
B
∗
P
is an
n
b
i
×
n
diagonal matrix with diagonal entries
.
Finally, by the Gram-Schmidt construction,
B
∗
=
UB
for some
n
×
n
matrix
U
such that
1. Combining these facts gives
1
det(
U
)
=
i
=
1
n
det(
B
∗
P
)
b
i
det(
L
)
=|
det(
BP
)
|=|
det(
UBP
)
|=|
|=
.
m
and let
b
1
,...,
b
n
}
Exercise 16.1.15
Let
{
b
1
,...,
b
n
}
be an ordered lattice basis in
R
{
b
i
be the Gram-Schmidt orthogonalisation. Show that
b
i
≥
and hence det(
L
)
≤
i
=
1
b
i
.
m
.The
orthogonality
Definition 16.1.16
Let
{
b
1
,...,
b
n
}
be a basis for a lattice
L
in
R
defect
of the basis is
n
/
det(
L
)
.
i
=
1
b
i
Exercise 16.1.17
Show that the orthogonality defect of
{
b
1
,...,
b
n
}
is 1 if and only if the
basis is orthogonal.
Definition 16.1.18
Let
L
⊂ R
m
be a lattice of rank
n
.The
successive minima
of
L
are
λ
1
,...,λ
n
∈ R
such that, for 1
≤
i
≤
n
,
λ
i
is minimal such that there exist
i
linearly
independent vectors
v
1
,...,
v
i
∈
L
with
v
j
≤
λ
i
for 1
≤
j
≤
i
.
λ
n
. In general, there is not a basis consisting of vectors
whose lengths are equal to the successive minima, as the following example shows.
It follows that 0
<λ
1
≤
λ
2
···≤
n
be the set
Example 16.1.19
Let
L
⊂ Z
L
={
(
x
1
,...,x
n
):
x
1
≡
x
2
≡···≡
x
n
(mod 2)
}
.
It is easy to check that this is a lattice. The vectors 2
e
i
∈
n
are linearly
independent and have length 2. Every other vector
x
∈
L
with even
en
tries has length
L
for 1
≤
i
≤
≥
2.
≥
√
n
.
Every vector
x
∈
L
with odd entries has all
x
i
=
0 a
n
d so
x
λ
2
=
√
2 and if
n
If
n
=
2 the success
iv
e minima are
λ
1
=
=
3 the successive minima
λ
3
=
√
3. When
n
are
λ
1
=
4 one can
construct a basis for the lattice with vectors of lengths equal to the successive minima.
When
n>
4 there is no basis for
L
consisting of vectors of length 2, since a basis must
contain at least one vector having odd entries.
λ
2
=
≥
4 then
λ
1
=
λ
2
=···=
λ
n
=
2. For
n
≤
=
Exercise 16.1.20
For
n
2
,
3
,
4 in Example
16.1.19
write down a basis for the lattice
consisting of vectors of lengths equal to the successive minima.
Exercise 16.1.21
For
n>
4 in Example
16
.1
.19
show there is a basis for the lattice such
that
b
n
=
√
n
.
b
i
=
λ
i
for 1
≤
i<n
and
1
The formula
BP
=
U
−
1
(
B
∗
P
) is the QR decomposition of
BP
.
