My Project  debian-1:4.1.1-p2+ds-4build3
lattice.h
Go to the documentation of this file.
1 #ifndef LATTICE_HPP
2 #define LATTICE_HPP
3 
4 // Algorithms based on chapter 2.6 of
5 // "A course in computational algebraic numbertheory" by Henry Cohen
6 class lattice {
7 
8  private:
9 
10  //array of basisvectors
12 
13  //gram matrix of the lattice
15 
16  //size of basis
17  int n;
18 
19  //length of basisvectors
20  int m;
21 
23 
24  //constant for LLL
25  number c;
26 
27  //array of basisvectors of LLL-basis
29 
30  //for LLL, see Cohen 2.6.3
32 
33  //array of B_i, see Cohen 2.6.3
34  number * B;
35 
36  //for LLL, see Cohen 2.6.3
38 
39  //for LLL, see Cohen 2.6.3
41 
42  //for integral LLL, see Cohen 2.6.7
43  number * d;
44 
45  //rank of the lattice
46  int rank;
47 
48  //if true transformation matrix H will be computed
50 
51  //true if basisvectors should be considered independent
53 
54  //true if gram matrix is integral
55  bool integral;
56 
57  //triangular matrix for enumeration
59 
60  //testing element for enumeration
62 
63  //bond for x_i in enumeration
64  number * bound;
65 
66  //coef for output
68 
69 
70 // int precision;
71 
72 
73 
74  //for LLL, see Cohen 2.6.3
75  inline void RED(int k, int l);
76 
77  //for LLL, see Cohen 2.6.3
78  inline void SWAP(int k, int k_max);
79 
80  //for MLLL, see Cohen 2.6.8
81  inline void SWAPG(int k, int k_max);
82 
83  //for LLL, see Cohen 2.6.3
84  inline bool gram_schmidt(int k);
85 
86  //for MLLL, see Cohen 2.6.8
87  inline void gram_schmidt_MLLL(int k);
88 
89 // inline void INSERT(int k, int i);
90 // inline bool gram_matrix(int k);
91 
92  inline void compute_gram_matrix();
93 
94  inline number enumerate_get_next();
95 
96  inline bool quadratic_supplement();
97 
98  inline void increase_x(int index);
99  inline number check_bound(int index);
100 
101  public:
102 
103  //constructor creates new lattice spanned by columns of b
105 
106  //destructor
107  ~lattice();
108 
109  //LLL with c=3/4
110  bool LLL();
111 
112  bool LLL(number& c);
113 
114  bigintmat * get_basis();
115 
117 
119 
120  bigintmat * enumerate_all(number a);
121 
122  bigintmat * enumerate_next(number a, bigintmat * x);
123 
124  bigintmat * enumerate_next(number a);
125 
127 
129 
130 // void set_precision(int a);
131 
132 };
133 
134 
135 //NOTE: could be moved to bigintmat
136 inline number scalarproduct(bigintmat * a, bigintmat * b);
137 
138 //minkowski
139 bigintmat * minkowksi(bigintmat ** elementarray,int size_elementarray, number * poly,int deg, coeffs coef, int precision);
140 bool IsReal(number a, coeffs coef);
141 bool ImagGreaterZero(number a, coeffs coef);
142 number squareroot(number a, coeffs coef, int iteration);// iteration in Heron algorithm
143 
144 #endif
lattice::get_basis
bigintmat * get_basis()
Definition: lattice.cc:874
lattice
Definition: lattice.h:6
lattice::check_bound
number check_bound(int index)
Definition: lattice.cc:855
lattice::x
bigintmat * x
Definition: lattice.h:61
k
int k
Definition: cfEzgcd.cc:92
bigintmat
Definition: bigintmat.h:52
lattice::out_coef
coeffs out_coef
Definition: lattice.h:67
lattice::n
int n
Definition: lattice.h:17
lattice::quadratic_supplement
bool quadratic_supplement()
Definition: lattice.cc:775
lattice::get_reduced_basis
bigintmat * get_reduced_basis()
Definition: lattice.cc:882
lattice::SWAPG
void SWAPG(int k, int k_max)
Definition: lattice.cc:357
lattice::integral
bool integral
Definition: lattice.h:55
lattice::compute_gram_matrix
void compute_gram_matrix()
Definition: lattice.cc:828
lattice::coef
coeffs coef
Definition: lattice.h:22
lattice::b_star
bigintmat ** b_star
Definition: lattice.h:31
lattice::H
bigintmat * H
Definition: lattice.h:37
lattice::bound
number * bound
Definition: lattice.h:64
b
CanonicalForm b
Definition: cfModGcd.cc:4044
lattice::increase_x
void increase_x(int index)
Definition: lattice.cc:841
scalarproduct
number scalarproduct(bigintmat *a, bigintmat *b)
Definition: lattice.cc:915
lattice::b
bigintmat ** b
Definition: lattice.h:28
lattice::basis
bigintmat ** basis
Definition: lattice.h:11
lattice::get_transformation_matrix
bigintmat * get_transformation_matrix()
Definition: lattice.cc:890
lattice::B
number * B
Definition: lattice.h:34
coeffs
squareroot
number squareroot(number a, coeffs coef, int iteration)
Definition: lattice.cc:1111
lattice::lattice
lattice(bigintmat *basis)
Definition: lattice.cc:52
lattice::my
bigintmat * my
Definition: lattice.h:40
lattice::gram_schmidt
bool gram_schmidt(int k)
Definition: lattice.cc:430
lattice::gram_schmidt_MLLL
void gram_schmidt_MLLL(int k)
Definition: lattice.cc:454
minkowksi
bigintmat * minkowksi(bigintmat **elementarray, int size_elementarray, number *poly, int deg, coeffs coef, int precision)
Definition: lattice.cc:948
lattice::~lattice
~lattice()
Definition: lattice.cc:90
lattice::enumerate_all
bigintmat * enumerate_all(number a)
Definition: lattice.cc:507
lattice::Q
bigintmat * Q
Definition: lattice.h:58
lattice::enumerate_get_next
number enumerate_get_next()
Definition: lattice.cc:718
lattice::SWAP
void SWAP(int k, int k_max)
Definition: lattice.cc:315
IsReal
bool IsReal(number a, coeffs coef)
Definition: lattice.cc:1097
lattice::d
number * d
Definition: lattice.h:43
lattice::c
number c
Definition: lattice.h:25
lattice::trans_matrix
bool trans_matrix
Definition: lattice.h:49
lattice::rank
int rank
Definition: lattice.h:46
l
int l
Definition: cfEzgcd.cc:93
lattice::independentVectors
bool independentVectors
Definition: lattice.h:52
lattice::m
int m
Definition: lattice.h:20
ImagGreaterZero
bool ImagGreaterZero(number a, coeffs coef)
Definition: lattice.cc:1104
lattice::enumerate_next
bigintmat * enumerate_next()
Definition: lattice.cc:691
lattice::gram_matrix
bigintmat * gram_matrix
Definition: lattice.h:14
index
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
lattice::LLL
bool LLL()
Definition: lattice.cc:133
lattice::RED
void RED(int k, int l)
Definition: lattice.cc:276