Cryptography Reference
In-Depth Information
n
.The
fundamental paral-
Definition A.10.7
Let
b
1
,...,
b
n
be a set of vectors in
R
lelepiped
of the set is
n
λ
i
<
1
.
λ
i
b
i
:0
≤
i
=
0
Lemma A.10.8
Let the notation be as above.
1. The volume of the fundamental parallelepiped of
{
b
1
,...,
b
n
}
is
|
det(
b
1
,...,
b
n
)
|
.
|=
i
=
1
where
b
i
are the Gram-Schmidt vectors.
Proof
The first claim is Theorem 19.12 of Curtis [
151
]. The second claim is Exercise 19.11
(also see Theorem 19.13) of [
151
].
b
i
2.
|
det(
b
1
,...,
b
n
)
n
. The first is to
perform Gaussian elimination to diagonalise and then take the product of the diagonal
elements. The second is to apply Gram-Schmidt (using floating-point arithmetic) and then
the determinant is just the product of the norms. Over
There are two methods to compute the determinant for vectors in
R
, both methods only give an
approximation to the determinant. To compute the determinant for vectors with entries in
Z
R
Q
(this gives an exact solution but suffers from coefficient explosion). Alternatively, one can
compute the determinant modulo
p
i
for many small or medium sized primes
p
i
and use the
Chinese remainder theorem.
or
Q
one can use Gaussian elimination or Gram-Schmidt with exact arithmetic in
A.11 Hermite normal form
Definition A.11.1
An
n
×
m
integer matrix
A
=
(
A
i,j
)isin(row)
Hermite normal form
(
HNF
) if there is some integer 1
≤
r
≤
n
and a strictly increasing map
f
:
{
1
,...,n
−
r
}→{
1
,...,m
}
(i.e.,
f
(
i
+
1)
>f
(
i
)) such that:
1. the last
r
rows of
A
are zero,
2. 0
≤
≤
j<i
and
A
j,f
(
i
)
=
≤
A
j,f
(
i
)
<A
i,f
(
i
)
for 1
0for
i<j
n
.
In particular, an
n
×
n
matrix that is upper triangular and that satisfies the condition
0
≤
n
is in Hermite normal form.
The HNF
A
of an integer matrix
A
is unique and there is an
n
A
j,i
<A
i,i
for 1
≤
j<i
≤
×
n
unimodular matrix
1) such that
A
=
U
(i.e.,
U
is a matrix with integer entries and determinant
UA
.For
more details of the Hermite normal form see Section 2.4.2 of Cohen [
127
] or Section 4.1
of Schrijver [
478
] (though note that both topics use columns rather than rows).
±
A.12 Orders in quadratic fields
(
√
d
) where
d
A quadratic field is
0
,
1 is a square-free integer. If
d<
0 then the field
is called an
imaginary quadratic field
.The
discriminant
of
K
Q
=
(
√
d
)is
D
= Q
=
d
if
d
≡
1(mod4)or
D
=
4
d
oth
erwise. The
ring of integers
of a quadratic field of discriminant
+
√
D
)
/
2].
An
order
in a field
D
is
O
K
= Z
[(
D
k
containing
Q
is a subring
R
of
k
that is finitely generated
as a
Z
-module and is such that
R
⊗
Z
Q = k
. Every order in a quadratic field is of the