gso.h
Go to the documentation of this file.
1/* Copyright (C) 2005-2008 Damien Stehle.
2 Copyright (C) 2007 David Cade.
3 Copyright (C) 2011 Xavier Pujol.
4
5 This file is part of fplll. fplll is free software: you
6 can redistribute it and/or modify it under the terms of the GNU Lesser
7 General Public License as published by the Free Software Foundation,
8 either version 2.1 of the License, or (at your option) any later version.
9
10 fplll is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU Lesser General Public License for more details.
14
15 You should have received a copy of the GNU Lesser General Public License
16 along with fplll. If not, see <http://www.gnu.org/licenses/>. */
17
18#ifndef FPLLL_GSO_H
19#define FPLLL_GSO_H
20
21#include "gso_interface.h"
22#include "nr/matrix.h"
23#include "util.h"
24
26
33template <class ZT, class FT> class MatGSO : public MatGSOInterface<ZT, FT>
34{
35public:
36 using MatGSOInterface<ZT, FT>::d;
39 using MatGSOInterface<ZT, FT>::u;
41 using MatGSOInterface<ZT, FT>::cols_locked; // maybe scratch.
45 using MatGSOInterface<ZT, FT>::u_inv_t;
46 using MatGSOInterface<ZT, FT>::sym_g;
47 using MatGSOInterface<ZT, FT>::mu;
48 using MatGSOInterface<ZT, FT>::r;
49 using MatGSOInterface<ZT, FT>::ztmp1;
50 using MatGSOInterface<ZT, FT>::ztmp2;
52 using MatGSOInterface<ZT, FT>::alloc_dim;
53 using MatGSOInterface<ZT, FT>::get_mu;
54 using MatGSOInterface<ZT, FT>::get_r;
55 using MatGSOInterface<ZT, FT>::gptr;
57 using MatGSOInterface<ZT, FT>::gf;
58 using MatGSOInterface<ZT, FT>::bf;
62 using MatGSOInterface<ZT, FT>::row_expo;
65
68 using MatGSOInterface<ZT, FT>::update_gso;
70 using MatGSOInterface<ZT, FT>::row_addmul;
72
73#ifdef DEBUG
74 /* Used only in debug mode. */
75 using MatGSOInterface<ZT, FT>::row_op_first;
76 using MatGSOInterface<ZT, FT>::row_op_last;
77 using MatGSOInterface<ZT, FT>::in_row_op_range;
78#endif
79
112 MatGSO(Matrix<ZT> &arg_b, Matrix<ZT> &arg_u, Matrix<ZT> &arg_uinv_t, int flags)
113 : MatGSOInterface<ZT, FT>(arg_u, arg_uinv_t, flags), b(arg_b)
114 {
116 d = b.get_rows();
117 if (enable_row_expo)
118 {
119 tmp_col_expo.resize(b.get_cols());
120 }
121 if (enable_int_gram)
122 {
123 gptr = &g;
124 }
125 size_increased();
126#ifdef DEBUG
127 row_op_first = row_op_last = -1;
128#endif
129 }
130
131public:
140
141 virtual inline ZT &sqnorm_coordinates(ZT &sqnorm, vector<ZT> coordinates);
142
143 virtual inline long get_max_exp_of_b();
144 virtual inline bool b_row_is_zero(int i);
145 virtual inline int get_cols_of_b() const;
146 virtual inline int get_rows_of_b() const;
147 virtual inline void negate_row_of_b(int i);
148
149 virtual inline void create_rows(int n_new_rows);
150 virtual inline void remove_last_rows(int n_removed_rows);
151
152 virtual void move_row(int old_r, int new_r);
153
163 // --> moved to interface
164 // virtual inline void row_addmul(int i, int j, const FT &x);
165
175 virtual void row_addmul_we(int i, int j, const FT &x, long expo_add);
176
177 // b[i] += b[j] / b[i] -= b[j] (i > j)
178 virtual void row_add(int i, int j);
179 virtual void row_sub(int i, int j);
180
181 // virtual inline void printparam(ostream &os);
182 virtual inline FT &get_gram(FT &f, int i, int j);
183
184 virtual inline ZT &get_int_gram(ZT &z, int i, int j);
185
186 // b[i] <-> b[j] (i < j)
187 virtual void row_swap(int i, int j);
188
198 void to_canonical(vector<FT> &w, const vector<FT> &v, long start = 0);
199
210 void from_canonical(vector<FT> &v, const vector<FT> &w, long start = 0, long dimension = -1);
211
221 void virtual babai(vector<ZT> &v, int start = 0, int dimension = -1, bool gso = false);
222
233 void virtual babai(vector<ZT> &w, const vector<FT> &v, int start = 0, int dimension = -1,
234 bool gso = false);
235
236private:
237 /* Allocates matrices and arrays whose size depends on d (all but tmp_col_expo).
238 When enable_int_gram=false, initializes bf. */
239 virtual void size_increased();
240
241 virtual void discover_row();
242
243 /* Upates the i-th row of bf. It does not invalidate anything, so the caller
244 must take into account that it might change row_expo. */
245 virtual void update_bf(int i);
246 /* Marks g(i, j) for all j <= i (but NOT for j > i) */
247 virtual void invalidate_gram_row(int i);
248
249 // b[i] <- b[i] + x * b[j] (i > j)
250 virtual void row_addmul_si(int i, int j, long x);
251 // b[i] <- b[i] + (2^expo * x) * b[j] (i > j)
252 virtual void row_addmul_si_2exp(int i, int j, long x, long expo);
253 virtual void row_addmul_2exp(int i, int j, const ZT &x, long expo);
254};
255
256template <class ZT, class FT>
257inline ZT &MatGSO<ZT, FT>::sqnorm_coordinates(ZT &sqnorm, vector<ZT> coordinates)
258{
259 vector<ZT> tmpvec;
260 ZT tmp;
261 sqnorm = 0;
262 vector_matrix_product(tmpvec, coordinates, b);
263 for (size_t j = 0; j < tmpvec.size(); j++)
264 {
265 tmp.mul(tmpvec[j], tmpvec[j]);
266 sqnorm.add(sqnorm, tmp);
267 }
268 return sqnorm;
269}
270
271template <class ZT, class FT> inline long MatGSO<ZT, FT>::get_max_exp_of_b()
272{
273 return b.get_max_exp();
274}
275
276template <class ZT, class FT> inline bool MatGSO<ZT, FT>::b_row_is_zero(int i)
277{
278 return b[i].is_zero();
279}
280template <class ZT, class FT> inline int MatGSO<ZT, FT>::get_cols_of_b() const
281{
282 return b.get_cols();
283}
284
285template <class ZT, class FT> inline int MatGSO<ZT, FT>::get_rows_of_b() const
286{
287 return b.get_rows();
288}
289
290template <class ZT, class FT> inline void MatGSO<ZT, FT>::negate_row_of_b(int i)
291{
292
293 for (int j = 0; j < get_cols_of_b(); j++)
294 {
295 b[i][j].neg(b[i][j]);
296 }
297 if (enable_int_gram)
298 {
299 for (int j = 0; j < get_rows_of_b(); j++)
300 {
301 if (j < i)
302 {
303 g(i, j).neg(g(i, j));
304 }
305 else if (j > i)
306 {
307 g(j, i).neg(g(j, i));
308 }
309 }
310 }
311}
312
313template <class ZT, class FT> inline FT &MatGSO<ZT, FT>::get_gram(FT &f, int i, int j)
314{
315 FPLLL_DEBUG_CHECK(i >= 0 && i < n_known_rows && j >= 0 && j <= i && j < n_source_rows &&
316 !in_row_op_range(i));
317 if (enable_int_gram)
318 {
319 f.set_z(g(i, j));
320 }
321 else
322 {
323 if (gf(i, j).is_nan())
324 {
325 bf[i].dot_product(gf(i, j), bf[j], n_known_cols);
326 }
327 f = gf(i, j);
328 }
329 return f;
330}
331
332template <class ZT, class FT> inline ZT &MatGSO<ZT, FT>::get_int_gram(ZT &z, int i, int j)
333{
334 FPLLL_DEBUG_CHECK(i >= 0 && i < n_known_rows && j >= 0 && j <= i && j < n_source_rows &&
335 !in_row_op_range(i));
336 if (enable_int_gram)
337 {
338 z = g(i, j);
339 }
340 else
341 {
342
343 b[i].dot_product(z, b[j], n_known_cols);
344 }
345 return z;
346}
347
348template <class ZT, class FT> inline void MatGSO<ZT, FT>::create_rows(int n_new_rows)
349{
350 FPLLL_DEBUG_CHECK(!cols_locked);
351 int old_d = d;
352 d += n_new_rows;
353 b.set_rows(d);
354 for (int i = old_d; i < d; i++)
355 {
356 for (int j = 0; j < b.get_cols(); j++)
357 {
358 b[i][j] = 0;
359 }
360 }
361 if (enable_transform)
362 {
363 u.set_rows(d);
364 for (int i = old_d; i < d; i++)
365 for (int j = 0; j < u.get_cols(); j++)
366 u[i][j] = 0;
367 }
368 size_increased();
369 if (n_known_rows == old_d)
370 discover_all_rows();
371}
372
373template <class ZT, class FT> inline void MatGSO<ZT, FT>::remove_last_rows(int n_removed_rows)
374{
375 FPLLL_DEBUG_CHECK(!cols_locked && d >= n_removed_rows);
376 d -= n_removed_rows;
377 n_known_rows = min(n_known_rows, d);
378 n_source_rows = n_known_rows;
379 b.set_rows(d);
380 if (enable_transform)
381 u.set_rows(d);
382}
383
385
386#endif
Definition: gso_interface.h:60
vector< long > row_expo
Definition: gso_interface.h:167
int alloc_dim
Definition: gso_interface.h:558
virtual void row_addmul(int i, int j, const FT &x)
Definition: gso_interface.h:746
bool cols_locked
Definition: gso_interface.h:557
vector< int > gso_valid_cols
Definition: gso_interface.h:605
const bool enable_int_gram
Definition: gso_interface.h:480
Matrix< FT > mu
Definition: gso_interface.h:572
Matrix< FT > bf
Definition: gso_interface.h:545
FT & get_r(FT &f, int i, int j)
Definition: gso_interface.h:721
const bool enable_inverse_transform
Definition: gso_interface.h:493
bool update_gso()
Definition: gso_interface.h:764
int n_known_rows
Definition: gso_interface.h:554
void invalidate_gso_row(int i, int new_valid_cols=0)
Definition: gso_interface.cpp:26
int n_source_rows
Definition: gso_interface.h:555
bool update_gso_row(int i, int last_j)
Definition: gso_interface.cpp:131
Matrix< FT > gf
Definition: gso_interface.h:601
int n_known_cols
Definition: gso_interface.h:556
Matrix< ZT > * gptr
Definition: gso_interface.h:597
void remove_last_row()
Definition: gso_interface.h:753
void discover_all_rows()
Definition: gso_interface.h:758
const bool enable_row_expo
Definition: gso_interface.h:483
FT & get_mu(FT &f, int i, int j)
Definition: gso_interface.h:691
ZT ztmp1
Definition: gso_interface.h:611
Matrix< ZT > & u_inv_t
Definition: gso_interface.h:548
vector< int > init_row_size
Definition: gso_interface.h:551
const bool row_op_force_long
Definition: gso_interface.h:499
int d
Definition: gso_interface.h:114
vector< long > tmp_col_expo
Definition: gso_interface.h:615
Matrix< FT > r
Definition: gso_interface.h:586
void print_mu_r_g(ostream &os)
Definition: gso_interface.h:645
void symmetrize_g()
Definition: gso_interface.h:629
ZT & sym_g(int i, int j)
Definition: gso_interface.h:661
const bool enable_transform
Definition: gso_interface.h:486
Matrix< ZT > & u
Definition: gso_interface.h:547
ZT ztmp2
Definition: gso_interface.h:613
Definition: gso.h:34
virtual void create_rows(int n_new_rows)
Definition: gso.h:348
virtual void babai(vector< ZT > &v, int start=0, int dimension=-1, bool gso=false)
Definition: gso.cpp:482
virtual FT & get_gram(FT &f, int i, int j)
Definition: gso.h:313
virtual void row_addmul_we(int i, int j, const FT &x, long expo_add)
Definition: gso.cpp:237
virtual int get_rows_of_b() const
Definition: gso.h:285
void to_canonical(vector< FT > &w, const vector< FT > &v, long start=0)
Definition: gso.cpp:406
void from_canonical(vector< FT > &v, const vector< FT > &w, long start=0, long dimension=-1)
Definition: gso.cpp:437
virtual void negate_row_of_b(int i)
Definition: gso.h:290
Matrix< ZT > & b
Definition: gso.h:135
virtual ZT & sqnorm_coordinates(ZT &sqnorm, vector< ZT > coordinates)
Definition: gso.h:257
virtual void row_add(int i, int j)
Definition: gso.cpp:84
virtual long get_max_exp_of_b()
Definition: gso.h:271
virtual int get_cols_of_b() const
Definition: gso.h:280
virtual void move_row(int old_r, int new_r)
Definition: gso.cpp:289
virtual void remove_last_rows(int n_removed_rows)
Definition: gso.h:373
MatGSO(Matrix< ZT > &arg_b, Matrix< ZT > &arg_u, Matrix< ZT > &arg_uinv_t, int flags)
Definition: gso.h:112
virtual void row_swap(int i, int j)
Definition: gso.cpp:264
virtual ZT & get_int_gram(ZT &z, int i, int j)
Definition: gso.h:332
virtual bool b_row_is_zero(int i)
Definition: gso.h:276
virtual void row_sub(int i, int j)
Definition: gso.cpp:107
Matrix< ZT > g
Definition: gso.h:139
int get_cols() const
Definition: matrix.h:156
int get_rows() const
Definition: matrix.h:154
#define FPLLL_END_NAMESPACE
Definition: defs.h:117
#define FPLLL_DEBUG_CHECK(x)
Definition: defs.h:109
#define FPLLL_BEGIN_NAMESPACE
Definition: defs.h:114
void vector_matrix_product(vector< ZT > &result, const vector< ZT > &x, const Matrix< ZT > &m)
Definition: util.h:41