Cryptography Reference
In-Depth Information
Exercise 16.2.6
Le
t
a,b
∈ N
. Show that there is a solution
r,s,t
∈ Z
to
r
=
as
+
bt
≤
√
2
b
.
such that
s
2
r
2
+
∈ N
Definition 16.2.7
Let
n
. The smallest real number
γ
n
such that
λ
1
≤
γ
n
det(
L
)
2
/n
for all lattices
L
of rank
n
is called the
Hermite constant
.
2
/
√
3.
Exercise 16.2.8
This exercise is to show that
γ
2
=
1. Let
be a Gauss reduced basis (see Definition
17.1.1
of the next section)
for a dimension 2 lattice in
{
b
1
,
b
2
}
2
. Define the quadratic form
N
(
x,y
)
2
.
R
=
x
b
1
+
y
b
2
ax
2
cy
2
Show that, without loss of generality,
N
(
x,y
)
=
+
2
bxy
+
with
a,b,c
≥
0
c
.
2. Using
N
(1
,
and
a
≤
−
1)
≥
N
(0
,
1) (which follows from the property of being Gauss reduced),
b
2
)
show that 2
b
≤
a
. Hence, show that 3
ac
≤
4(
ac
−
3. Sho
w
that det(
L
)
2
b
2
=|
−
ac
|
. Hence, deduce that Hermite's constant satisfies
γ
2
≤
2
/
√
3.
4. Show
1
/
2
,
√
3
/
2)
2
satisfies
λ
1
=
that
the
lattice
L
⊂ R
with
basis
{
(1
,
0)
,
(
−
}
(2
/
√
3) det(
L
).
(Optional) Show that
L
is equal to the ring of algebraic integers of
(
√
−
Q
3). Show
that centering balls of radius 1
/
2 at each point of
L
gives the most dense lattice packing
of balls in
R
2
.
n
Section 6.5.2 of Nguyen [
409
] lists the first 8 values of
γ
n
, gives the bound
2
πe
+
o
(1)
≤
n
γ
n
≤
πe
(1
+
o
(1)) and gives further references.
R
n
with successive minima
Theorem 16.2.9
(Minkowski) Let L be a lattice of rank n in
λ
1
,...,λ
n
for the Euclidean norm. Then
n
1
/n
<
√
n
det(
L
)
1
/n
.
λ
i
i
=
1
Proof
See Theorem 12.2.2 of [
113
]. (The term
√
n
can be replaced by
√
γ
n
.)
The
Gaussian heuristic
states that the shortest non-zero vector in a “random” lattice
L
of dimension
n
in
n
is expected to have length approximately
n
2
πe
det(
L
)
1
/n
.
R
We refer to Section 6.5.3 of [
409
] and Section 6.5.3 of [
261
] for discussion and references.
