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