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
11         bigintmat ** basis;
12 
13         //gram matrix of the lattice
14         bigintmat * gram_matrix;
15 
16         //size of basis
17         int n;
18 
19         //length of basisvectors
20         int m;
21 
22         coeffs coef;
23 
24         //constant for LLL
25         number c;
26 
27         //array of basisvectors of LLL-basis
28         bigintmat ** b;
29 
30         //for LLL, see Cohen 2.6.3
31         bigintmat ** b_star;
32 
33         //array of B_i, see Cohen 2.6.3
34         number * B;
35 
36         //for LLL, see Cohen 2.6.3
37         bigintmat * H;
38 
39         //for LLL, see Cohen 2.6.3
40         bigintmat * my;
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
49         bool trans_matrix;
50 
51         //true if basisvectors should be considered independent
52         bool independentVectors;
53 
54         //true if gram matrix is integral
55         bool integral;
56 
57         //triangular matrix for enumeration
58         bigintmat * Q;
59 
60         //testing element for enumeration
61         bigintmat * x;
62 
63         //bond for x_i in enumeration
64         number * bound;
65 
66         //coef for output
67         coeffs out_coef;
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
104         lattice(bigintmat* basis);
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 
116         bigintmat * get_reduced_basis();
117 
118         bigintmat * get_transformation_matrix();
119 
120         bigintmat * enumerate_all(number a);
121 
122         bigintmat * enumerate_next(number a, bigintmat * x);
123 
124         bigintmat * enumerate_next(number a);
125 
126         bigintmat * enumerate_next(bigintmat * x);
127 
128         bigintmat * enumerate_next();
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
145