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
 
Search WWH ::




Custom Search