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
bool quadratic_supplement()
Definition: lattice.cc:775
int rank
Definition: lattice.h:46
bigintmat * Q
Definition: lattice.h:58
bigintmat * gram_matrix
Definition: lattice.h:14
~lattice()
Definition: lattice.cc:90
bool trans_matrix
Definition: lattice.h:49
const poly a
Definition: syzextra.cc:212
int n
Definition: lattice.h:17
void SWAPG(int k, int k_max)
Definition: lattice.cc:357
bigintmat * enumerate_all(number a)
Definition: lattice.cc:507
number * d
Definition: lattice.h:43
bigintmat * enumerate_next()
Definition: lattice.cc:691
number enumerate_get_next()
Definition: lattice.cc:718
bigintmat ** b
Definition: lattice.h:28
lattice(bigintmat *basis)
Definition: lattice.cc:52
Matrices of numbers.
Definition: bigintmat.h:51
bigintmat * my
Definition: lattice.h:40
number * bound
Definition: lattice.h:64
coeffs out_coef
Definition: lattice.h:67
void gram_schmidt_MLLL(int k)
Definition: lattice.cc:454
number scalarproduct(bigintmat *a, bigintmat *b)
Definition: lattice.cc:915
bool gram_schmidt(int k)
Definition: lattice.cc:430
bigintmat ** b_star
Definition: lattice.h:31
bigintmat * x
Definition: lattice.h:61
void RED(int k, int l)
Definition: lattice.cc:276
int k
Definition: cfEzgcd.cc:93
bool independentVectors
Definition: lattice.h:52
number squareroot(number a, coeffs coef, int iteration)
Definition: lattice.cc:1111
void compute_gram_matrix()
Definition: lattice.cc:828
The main handler for Singular numbers which are suitable for Singular polynomials.
bigintmat ** basis
Definition: lattice.h:11
bigintmat * minkowksi(bigintmat **elementarray, int size_elementarray, number *poly, int deg, coeffs coef, int precision)
Definition: lattice.cc:948
bigintmat * get_basis()
Definition: lattice.cc:874
bigintmat * get_transformation_matrix()
Definition: lattice.cc:890
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
void SWAP(int k, int k_max)
Definition: lattice.cc:315
bigintmat * H
Definition: lattice.h:37
bool LLL()
Definition: lattice.cc:133
bool ImagGreaterZero(number a, coeffs coef)
Definition: lattice.cc:1104
number c
Definition: lattice.h:25
int m
Definition: lattice.h:20
bool IsReal(number a, coeffs coef)
Definition: lattice.cc:1097
coeffs coef
Definition: lattice.h:22
void increase_x(int index)
Definition: lattice.cc:841
number check_bound(int index)
Definition: lattice.cc:855
polyrec * poly
Definition: hilb.h:10
const poly b
Definition: syzextra.cc:213
Definition: lattice.h:6
bool integral
Definition: lattice.h:55
number * B
Definition: lattice.h:34
int l
Definition: cfEzgcd.cc:94
bigintmat * get_reduced_basis()
Definition: lattice.cc:882