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 #include "wrapper.h"
19 #include "hlll.h"
20 #include "lll.h"
21 #include "util.h"
22
23 FPLLL_BEGIN_NAMESPACE
24
25 /* prec=53, eta=0.501, dim < dim_double_max [ (delta / 100.0) + 25 ] */
26 const double dim_double_max[75] = {
27 0, 26, 29.6, 28.1, 31.1, 32.6, 34.6, 34, 37.7, 38.8, 39.6, 41.8, 40.9,
28 43.6, 44.2, 47, 46.8, 50.6, 49.1, 51.5, 52.5, 54.8, 54.6, 57.4, 57.6, 59.9,
29 61.8, 62.3, 64.5, 67.1, 68.8, 68.3, 69.9, 73.1, 74, 76.1, 76.8, 80.9, 81.8,
30 83, 85.3, 87.9, 89, 90.1, 89, 94.6, 94.8, 98.7, 99, 101.6, 104.9, 106.8,
31 108.2, 107.4, 110, 112.7, 114.6, 118.1, 119.7, 121.8, 122.9, 126.6, 128.6, 129, 133.6,
32 126.9, 135.9, 139.5, 135.2, 137.2, 139.3, 142.8, 142.4, 142.5, 145.4};
33
34 const double eta_dep[10] = {1., // 0.5
35 1., // 0.55
36 1.0521, // 0.6
37 1.1254, // 0.65
38 1.2535, // 0.7
39 1.3957, // 0.75
40 1.6231, // 0.8
41 1.8189, // 0.85
42 2.1025, // 0.9
43 2.5117}; // 0.95
44
Wrapper(ZZ_mat<mpz_t> & b,ZZ_mat<mpz_t> & u,ZZ_mat<mpz_t> & u_inv,double delta,double eta,int flags)45 Wrapper::Wrapper(ZZ_mat<mpz_t> &b, ZZ_mat<mpz_t> &u, ZZ_mat<mpz_t> &u_inv, double delta, double eta,
46 int flags)
47 : status(RED_SUCCESS), b(b), u(u), u_inv(u_inv), delta(delta), eta(eta), use_long(false),
48 last_early_red(0)
49 {
50 n = b.get_cols();
51 d = b.get_rows();
52 this->flags = flags;
53 max_exponent = b.get_max_exp() + (int)ceil(0.5 * log2((double)d * n));
54
55 // Computes the parameters required for the proved version
56 good_prec = l2_min_prec(d, delta, eta, LLL_DEF_EPSILON);
57 }
58
59 // Constructor for HLLL
Wrapper(ZZ_mat<mpz_t> & b,ZZ_mat<mpz_t> & u,ZZ_mat<mpz_t> & u_inv,double delta,double eta,double theta,double c,int flags)60 Wrapper::Wrapper(ZZ_mat<mpz_t> &b, ZZ_mat<mpz_t> &u, ZZ_mat<mpz_t> &u_inv, double delta, double eta,
61 double theta, double c, int flags)
62 : status(RED_SUCCESS), b(b), u(u), u_inv(u_inv), delta(delta), eta(eta), use_long(false),
63 last_early_red(-1), theta(theta), c(c)
64 {
65 n = b.get_cols();
66 d = b.get_rows();
67 this->flags = flags;
68
69 // Computes the parameters required for the proved version
70 good_prec = hlll_min_prec(d, n, delta, eta, theta, c);
71 }
72
little(int kappa,int precision)73 bool Wrapper::little(int kappa, int precision)
74 {
75 /*one may add here dimension arguments with respect to eta and delta */
76 int dm = (int)(delta * 100. - 25.);
77 if (dm < 0)
78 dm = 0;
79 if (dm > 74)
80 dm = 74;
81
82 int em = (int)((eta - 0.5) * 20);
83 if (em < 0)
84 em = 0;
85 if (em > 9)
86 em = 9;
87
88 double p = max(1.0, precision / 53.0);
89
90 p *= eta_dep[em]; /* eta dependance */
91 p *= dim_double_max[dm];
92 // cerr << kappa << " compared to " << p << endl;
93 return kappa < p;
94 }
95
96 /**
97 * main function. Method determines whether heuristic, fast or proved
98 */
99 template <class Z, class F>
call_lll(ZZ_mat<Z> & bz,ZZ_mat<Z> & uz,ZZ_mat<Z> & u_invZ,LLLMethod method,int precision,double delta,double eta)100 int Wrapper::call_lll(ZZ_mat<Z> &bz, ZZ_mat<Z> &uz, ZZ_mat<Z> &u_invZ, LLLMethod method,
101 int precision, double delta, double eta)
102 {
103 typedef Z_NR<Z> ZT;
104 typedef FP_NR<F> FT;
105
106 if (flags & LLL_VERBOSE)
107 {
108 cerr << "====== Wrapper: calling " << LLL_METHOD_STR[method] << "<" << num_type_str<Z>() << ","
109 << num_type_str<F>() << "> method";
110 if (precision > 0)
111 {
112 cerr << " (precision=" << precision << ")";
113 }
114 cerr << " ======" << endl;
115 }
116
117 int gso_flags = 0;
118 if (method == LM_PROVED)
119 gso_flags |= GSO_INT_GRAM;
120 if (method == LM_FAST)
121 gso_flags |= GSO_ROW_EXPO;
122 if (method != LM_PROVED && precision == 0)
123 gso_flags |= GSO_OP_FORCE_LONG;
124
125 int old_prec = FP_NR<mpfr_t>::get_prec();
126 if (precision > 0)
127 {
128 FP_NR<mpfr_t>::set_prec(precision);
129 }
130 MatGSO<ZT, FT> m_gso(bz, uz, u_invZ, gso_flags);
131 LLLReduction<ZT, FT> lll_obj(m_gso, delta, eta, flags);
132 lll_obj.last_early_red = last_early_red;
133 lll_obj.lll();
134 status = lll_obj.status;
135 last_early_red = max(last_early_red, lll_obj.last_early_red);
136 if (precision > 0)
137 {
138 FP_NR<mpfr_t>::set_prec(old_prec);
139 }
140
141 if (flags & LLL_VERBOSE)
142 {
143 cerr << "====== Wrapper: end of " << LLL_METHOD_STR[method] << " method ======\n" << endl;
144 }
145
146 if (lll_obj.status == RED_SUCCESS)
147 return 0;
148 else if (lll_obj.status == RED_GSO_FAILURE || lll_obj.status == RED_BABAI_FAILURE)
149 return lll_obj.final_kappa;
150 else
151 return -1;
152 }
153
154 /**
155 * pass the method to call_lll()
156 */
fast_lll(double delta,double eta)157 template <class F> int Wrapper::fast_lll(double delta, double eta)
158 {
159 return call_lll<mpz_t, F>(b, u, u_inv, LM_FAST, 0, delta, eta);
160 }
161
162 template <class Z, class F>
heuristic_lll(ZZ_mat<Z> & bz,ZZ_mat<Z> & uz,ZZ_mat<Z> & u_invZ,int precision,double delta,double eta)163 int Wrapper::heuristic_lll(ZZ_mat<Z> &bz, ZZ_mat<Z> &uz, ZZ_mat<Z> &u_invZ, int precision,
164 double delta, double eta)
165 {
166 return call_lll<Z, F>(bz, uz, u_invZ, LM_HEURISTIC, precision, delta, eta);
167 }
168
169 template <class Z, class F>
proved_lll(ZZ_mat<Z> & bz,ZZ_mat<Z> & uz,ZZ_mat<Z> & u_invZ,int precision,double delta,double eta)170 int Wrapper::proved_lll(ZZ_mat<Z> &bz, ZZ_mat<Z> &uz, ZZ_mat<Z> &u_invZ, int precision,
171 double delta, double eta)
172 {
173 return call_lll<Z, F>(bz, uz, u_invZ, LM_PROVED, precision, delta, eta);
174 }
175
176 /**
177 * In heuristic_loop(), we only use double or dpe_t or mpfr_t.
178 */
heuristic_loop(int precision)179 int Wrapper::heuristic_loop(int precision)
180 {
181 int kappa;
182
183 if (precision > numeric_limits<double>::digits)
184 kappa = heuristic_lll<mpz_t, mpfr_t>(b, u, u_inv, precision, delta, eta);
185 else
186 {
187 #ifdef FPLLL_WITH_DPE
188 kappa = heuristic_lll<mpz_t, dpe_t>(b, u, u_inv, 0, delta, eta);
189 #else
190 kappa = heuristic_lll<mpz_t, mpfr_t>(b, u, u_inv, precision, delta, eta);
191 #endif
192 }
193
194 if (kappa == 0)
195 return 0; // Success
196 else if (precision < good_prec && !little(kappa, precision))
197 return heuristic_loop(increase_prec(precision));
198 else
199 return proved_loop(precision);
200 }
201
proved_loop(int precision)202 int Wrapper::proved_loop(int precision)
203 {
204 int kappa;
205 #ifdef FPLLL_WITH_QD
206 if (precision > PREC_DD)
207 #else
208 if (precision > numeric_limits<double>::digits)
209 #endif
210 kappa = proved_lll<mpz_t, mpfr_t>(b, u, u_inv, precision, delta, eta);
211 else if (max_exponent * 2 > MAX_EXP_DOUBLE)
212 {
213 #ifdef FPLLL_WITH_DPE
214 kappa = proved_lll<mpz_t, dpe_t>(b, u, u_inv, 0, delta, eta);
215 #else
216 kappa = proved_lll<mpz_t, mpfr_t>(b, u, u_inv, precision, delta, eta);
217 #endif
218 }
219 #ifdef FPLLL_WITH_QD
220 else if (precision > numeric_limits<double>::digits)
221 kappa = proved_lll<mpz_t, dd_real>(b, u, u_inv, precision, delta, eta);
222 #endif
223 else
224 kappa = proved_lll<mpz_t, double>(b, u, u_inv, 0, delta, eta);
225
226 if (kappa == 0)
227 return 0; // Success
228 else if (precision < good_prec)
229 return proved_loop(increase_prec(precision));
230 else
231 return -1; // This point should never be reached
232 }
233
234 /**
235 * last call to LLL. Need to be proved_lll.
236 */
last_lll()237 int Wrapper::last_lll()
238 {
239
240 /* <long, FT> */
241 #ifdef FPLLL_WITH_ZLONG
242 if (use_long)
243 {
244 int kappa;
245 if (good_prec <= numeric_limits<double>::digits)
246 kappa = proved_lll<long, double>(b_long, u_long, u_inv_long, good_prec, delta, eta);
247 #ifdef FPLLL_WITH_QD
248 else if (good_prec <= PREC_DD)
249 kappa = proved_lll<long, dd_real>(b_long, u_long, u_inv_long, good_prec, delta, eta);
250 #endif
251 else
252 kappa = proved_lll<long, mpfr_t>(b_long, u_long, u_inv_long, good_prec, delta, eta);
253 return kappa;
254 }
255 #endif
256
257 /* <mpfr, FT> */
258 #ifdef FPLLL_WITH_DPE
259 if (good_prec <= numeric_limits<double>::digits)
260 return proved_lll<mpz_t, dpe_t>(b, u, u_inv, good_prec, delta, eta);
261 #ifdef FPLLL_WITH_QD
262 else if (good_prec <= PREC_DD)
263 {
264 max_exponent = b.get_max_exp() + (int)ceil(0.5 * log2((double)d * n));
265 if (max_exponent * 2 < MAX_EXP_DOUBLE)
266 {
267 return proved_lll<mpz_t, dd_real>(b, u, u_inv, good_prec, delta, eta);
268 }
269 }
270 #endif
271 #endif
272 return proved_lll<mpz_t, mpfr_t>(b, u, u_inv, good_prec, delta, eta);
273 }
274
275 /**
276 * Wrapper.lll() calls
277 * - heuristic_lll()
278 * - fast_lll()
279 * - proved_lll()
280 */
lll()281 bool Wrapper::lll()
282 {
283 if (b.get_rows() == 0 || b.get_cols() == 0)
284 return RED_SUCCESS;
285
286 #ifdef FPLLL_WITH_ZLONG
287 bool heuristic_with_long =
288 max_exponent < numeric_limits<long>::digits - 2 && u.empty() && u_inv.empty();
289 bool proved_with_long =
290 2 * max_exponent < numeric_limits<long>::digits - 2 && u.empty() && u_inv.empty();
291 #else
292 bool heuristic_with_long = false, proved_with_long = false;
293 #endif
294
295 int kappa;
296
297 /* small matrix */
298 if (heuristic_with_long)
299 {
300 #ifdef FPLLL_WITH_ZLONG
301 set_use_long(true);
302 /* try heuristic_lll <long, double> */
303 heuristic_lll<long, double>(b_long, u_long, u_inv_long, 0, delta, eta);
304 #endif
305 }
306 /* large matrix */
307 else
308 {
309
310 /* try fast_lll<mpz_t, double> */
311 kappa = fast_lll<double>(delta, eta);
312 bool lll_failure = (kappa != 0);
313 int last_prec;
314
315 /* try fast_lll<mpz_t, long double> */
316 #ifdef FPLLL_WITH_LONG_DOUBLE
317 if (lll_failure)
318 {
319 kappa = fast_lll<long double>(delta, eta);
320 lll_failure = kappa != 0;
321 }
322 last_prec = numeric_limits<long double>::digits;
323 #else
324 last_prec = numeric_limits<double>::digits;
325 #endif
326
327 /* try fast_lll<mpz_t, dd_real> */
328 #ifdef FPLLL_WITH_QD
329 if (lll_failure)
330 {
331 kappa = fast_lll<dd_real>(delta, eta);
332 lll_failure = kappa != 0;
333 }
334 last_prec = PREC_DD;
335 #else
336 #ifdef FPLLL_WITH_LONG_DOUBLE
337 last_prec = numeric_limits<long double>::digits;
338 #else
339 last_prec = numeric_limits<double>::digits;
340 #endif
341 #endif
342
343 /* loop */
344 if (lll_failure)
345 {
346 int prec_d = numeric_limits<double>::digits;
347 if (little(kappa, last_prec))
348 kappa = proved_loop(prec_d);
349 else
350 kappa = heuristic_loop(increase_prec(prec_d));
351 }
352 }
353
354 set_use_long(proved_with_long);
355 /* final LLL */
356 kappa = last_lll();
357 set_use_long(false);
358 return kappa == 0;
359 }
360
361 /**
362 * set blong <-- b
363 */
set_use_long(bool value)364 void Wrapper::set_use_long(bool value)
365 {
366 #ifdef FPLLL_WITH_ZLONG
367 if (!use_long && value)
368 {
369 if (b_long.empty())
370 {
371 b_long.resize(d, n);
372 }
373 for (int i = 0; i < d; i++)
374 for (int j = 0; j < n; j++)
375 b_long(i, j) = b(i, j).get_si();
376 }
377 else if (use_long && !value)
378 {
379 for (int i = 0; i < d; i++)
380 for (int j = 0; j < n; j++)
381 b(i, j) = b_long(i, j).get_si();
382 }
383 use_long = value;
384 #endif
385 }
386
increase_prec(int precision)387 int Wrapper::increase_prec(int precision) { return min(precision * 2, good_prec); }
388
389 /* Set of methods for the HLLL wrapper. */
390
391 /**
392 * main function to call hlll
393 * Return true if success, false otherwise
394 */
call_hlll(LLLMethod method,int precision)395 template <class F> bool Wrapper::call_hlll(LLLMethod method, int precision)
396 {
397 typedef FP_NR<F> FT;
398
399 if (flags & LLL_VERBOSE)
400 {
401 cerr << "====== Wrapper: calling " << HLLL_METHOD_STR[method] << "<mpz_t," << num_type_str<F>()
402 << "> method";
403 if (precision > 0)
404 {
405 cerr << " (precision=" << precision << ")";
406 }
407 cerr << " ======" << endl;
408 }
409
410 int householder_flags = 0;
411 if (method == LM_PROVED)
412 householder_flags |= HOUSEHOLDER_DEFAULT;
413 if (method == LM_FAST)
414 householder_flags |= HOUSEHOLDER_ROW_EXPO | HOUSEHOLDER_OP_FORCE_LONG;
415
416 int old_prec = FP_NR<mpfr_t>::get_prec();
417
418 if (precision > 0)
419 FP_NR<mpfr_t>::set_prec(precision);
420
421 MatHouseholder<Z_NR<mpz_t>, FT> m(b, u, u_inv, householder_flags);
422 HLLLReduction<Z_NR<mpz_t>, FT> hlll_obj(m, delta, eta, theta, c, flags);
423 hlll_obj.hlll();
424 int status = hlll_obj.get_status();
425
426 if (precision > 0)
427 FP_NR<mpfr_t>::set_prec(old_prec);
428
429 if (flags & LLL_VERBOSE)
430 {
431 cerr << "====== Wrapper: end of " << HLLL_METHOD_STR[method] << " method ======\n" << endl;
432 }
433
434 if (status == RED_SUCCESS)
435 return true;
436 else
437 return false;
438 }
439
440 /**
441 * last call to LLL. Need to be proved_lll.
442 */
last_hlll()443 bool Wrapper::last_hlll()
444 {
445 /* <mpfr, FT> */
446 #ifdef FPLLL_WITH_DPE
447 if (good_prec <= numeric_limits<double>::digits)
448 return proved_hlll<dpe_t>(good_prec);
449 #ifdef FPLLL_WITH_QD
450 else if (good_prec <= PREC_DD)
451 return proved_hlll<dd_real>(good_prec);
452 #endif // FPLLL_WITH_QD
453 #endif // FPLLL_WITH_DPE
454 return proved_hlll<mpfr_t>(good_prec);
455 }
hlll_proved_loop(int precision)456 int Wrapper::hlll_proved_loop(int precision)
457 {
458 bool status = proved_hlll<mpfr_t>(precision);
459
460 if (status)
461 return 0; // Success
462 else if (precision < good_prec)
463 return hlll_proved_loop(increase_prec(precision));
464 else
465 return -1; // This point should never be reached
466 }
467
468 /**
469 * pass the method to call_hlll()
470 */
fast_hlll()471 template <class F> bool Wrapper::fast_hlll() { return call_hlll<F>(LM_FAST, 0); }
472
proved_hlll(int precision)473 template <class F> bool Wrapper::proved_hlll(int precision)
474 {
475 return call_hlll<F>(LM_PROVED, precision);
476 }
477
hlll()478 bool Wrapper::hlll()
479 {
480 if (b.get_rows() == 0 || b.get_cols() == 0)
481 return RED_SUCCESS;
482
483 int last_prec = numeric_limits<double>::digits;
484 bool hlll_complete = false;
485
486 // TODO: since classical lll is faster than hlll for dim <~ 160, maybe we can
487 // use fast_lll<double>() at the beginning of hlll, before calling
488 // fast_hlll<double>()
489 // Something like the one used in #if 0 should work
490 #if 0
491 /* try fast_lll<mpz_t, double> */
492 int kappa = fast_lll<double>(delta, eta);
493 bool lll_failure = (kappa != 0);
494
495 /* try fast_lll<mpz_t, double> */
496 if (lll_failure)
497 hlll_complete = fast_hlll<double>();
498 else
499 hlll_complete = true;
500 #else // 0
501 hlll_complete = fast_hlll<double>();
502 #endif // 0
503
504 /* try fast_hlll<mpz_t, long double> */
505 #ifdef FPLLL_WITH_LONG_DOUBLE
506 if (!hlll_complete)
507 {
508 hlll_complete = fast_hlll<long double>();
509 last_prec = numeric_limits<long double>::digits;
510 }
511 #endif // FPLLL_WITH_LONG_DOUBLE
512
513 /* try fast_hlll<mpz_t, dd_real> */
514 #ifdef FPLLL_WITH_QD
515 if (!hlll_complete)
516 {
517 hlll_complete = fast_hlll<dd_real>();
518 last_prec = PREC_DD;
519 }
520 #endif // FPLLL_WITH_QD
521
522 /* loop */
523 if (!hlll_complete)
524 hlll_complete = hlll_proved_loop(last_prec);
525
526 hlll_complete = last_hlll();
527
528 return hlll_complete == RED_SUCCESS;
529 }
530
531 /**
532 * LLL with a typical method "proved or heuristic or fast".
533 * @proved: exact gram + exact rowexp + exact rowaddmul
534 * @heuristic: approx. gram + exact rowexp + exact rowaddmul
535 * @fast: approx. gram + approx. rowexp + approx. rowaddmul
536 * (double, long double, dd_real, qd_real)
537 */
538 template <class ZT, class FT>
lll_reduction_zf(ZZ_mat<ZT> & b,ZZ_mat<ZT> & u,ZZ_mat<ZT> & u_inv,double delta,double eta,LLLMethod method,int flags)539 int lll_reduction_zf(ZZ_mat<ZT> &b, ZZ_mat<ZT> &u, ZZ_mat<ZT> &u_inv, double delta, double eta,
540 LLLMethod method, int flags)
541 {
542 int gso_flags = 0;
543 if (b.get_rows() == 0 || b.get_cols() == 0)
544 return RED_SUCCESS;
545 if (method == LM_PROVED)
546 gso_flags |= GSO_INT_GRAM;
547 if (method == LM_FAST)
548 gso_flags |= GSO_ROW_EXPO | GSO_OP_FORCE_LONG;
549 MatGSO<Z_NR<ZT>, FP_NR<FT>> m_gso(b, u, u_inv, gso_flags);
550 LLLReduction<Z_NR<ZT>, FP_NR<FT>> lll_obj(m_gso, delta, eta, flags);
551 lll_obj.lll();
552 return lll_obj.status;
553 }
554
555 template <class ZT>
lll_reduction_wrapper(ZZ_mat<ZT> &,ZZ_mat<ZT> &,ZZ_mat<ZT> &,double,double,FloatType,int,int)556 int lll_reduction_wrapper(ZZ_mat<ZT> &, ZZ_mat<ZT> &, ZZ_mat<ZT> &, double, double, FloatType, int,
557 int)
558 {
559 FPLLL_ABORT("The wrapper method works only with integer type mpz");
560 return RED_LLL_FAILURE;
561 }
562
563 template <>
lll_reduction_wrapper(ZZ_mat<mpz_t> & b,ZZ_mat<mpz_t> & u,ZZ_mat<mpz_t> & u_inv,double delta,double eta,FloatType float_type,int precision,int flags)564 int lll_reduction_wrapper(ZZ_mat<mpz_t> &b, ZZ_mat<mpz_t> &u, ZZ_mat<mpz_t> &u_inv, double delta,
565 double eta, FloatType float_type, int precision, int flags)
566 {
567 FPLLL_CHECK(float_type == FT_DEFAULT,
568 "The floating point type cannot be specified with the wrapper method");
569 FPLLL_CHECK(precision == 0, "The precision cannot be specified with the wrapper method");
570 Wrapper wrapper(b, u, u_inv, delta, eta, flags);
571 wrapper.lll();
572 zeros_first(b, u, u_inv);
573 return wrapper.status;
574 }
575
576 /**
577 * Main function called from call_lll().
578 */
579 template <class ZT>
lll_reduction_z(ZZ_mat<ZT> & b,ZZ_mat<ZT> & u,ZZ_mat<ZT> & u_inv,double delta,double eta,LLLMethod method,IntType int_type,FloatType float_type,int precision,int flags)580 int lll_reduction_z(ZZ_mat<ZT> &b, ZZ_mat<ZT> &u, ZZ_mat<ZT> &u_inv, double delta, double eta,
581 LLLMethod method, IntType int_type, FloatType float_type, int precision,
582 int flags)
583 {
584
585 /* switch to wrapper */
586 if (method == LM_WRAPPER)
587 return lll_reduction_wrapper(b, u, u_inv, delta, eta, float_type, precision, flags);
588
589 FPLLL_CHECK(!(method == LM_PROVED && (flags & LLL_EARLY_RED)),
590 "LLL method 'proved' with early reduction is not implemented");
591
592 /* computes the parameters required for the proved version */
593 int good_prec = l2_min_prec(b.get_rows(), delta, eta, LLL_DEF_EPSILON);
594
595 /* sets the parameters and checks the consistency */
596 int sel_prec = 0;
597 if (method == LM_PROVED)
598 {
599 sel_prec = (precision != 0) ? precision : good_prec;
600 }
601 else
602 {
603 sel_prec = (precision != 0) ? precision : PREC_DOUBLE;
604 }
605
606 FloatType sel_ft = float_type;
607
608 /* if manually input precision */
609 if (precision != 0)
610 {
611 if (sel_ft == FT_DEFAULT)
612 {
613 sel_ft = FT_MPFR;
614 }
615 FPLLL_CHECK(sel_ft == FT_MPFR,
616 "The floating type must be mpfr when the precision is specified");
617 }
618
619 if (sel_ft == FT_DEFAULT)
620 {
621 if (method == LM_FAST)
622 sel_ft = FT_DOUBLE;
623 #ifdef FPLLL_WITH_DPE
624 else if (sel_prec <= static_cast<int>(FP_NR<dpe_t>::get_prec()))
625 sel_ft = FT_DPE;
626 #endif
627 #ifdef FPLLL_WITH_QD
628 else if (sel_prec <= static_cast<int>(FP_NR<dd_real>::get_prec()))
629 sel_ft = FT_DD;
630 else if (sel_prec <= static_cast<int>(FP_NR<qd_real>::get_prec()))
631 sel_ft = FT_QD;
632 #endif
633 else
634 sel_ft = FT_MPFR;
635 }
636 else if (method == LM_FAST &&
637 (sel_ft != FT_DOUBLE && sel_ft != FT_LONG_DOUBLE && sel_ft != FT_DD && sel_ft != FT_QD))
638 {
639 FPLLL_ABORT("'double' or 'long double' or 'dd' or 'qd' required for "
640 << LLL_METHOD_STR[method]);
641 }
642
643 if (sel_ft == FT_DOUBLE)
644 sel_prec = FP_NR<double>::get_prec();
645 #ifdef FPLLL_WITH_LONG_DOUBLE
646 else if (sel_ft == FT_LONG_DOUBLE)
647 sel_prec = FP_NR<long double>::get_prec();
648 #endif
649 #ifdef FPLLL_WITH_DPE
650 else if (sel_ft == FT_DPE)
651 sel_prec = FP_NR<dpe_t>::get_prec();
652 #endif
653 #ifdef FPLLL_WITH_QD
654 else if (sel_ft == FT_DD)
655 sel_prec = FP_NR<dd_real>::get_prec();
656 else if (sel_ft == FT_QD)
657 sel_prec = FP_NR<qd_real>::get_prec();
658 #endif
659
660 if (flags & LLL_VERBOSE)
661 {
662 cerr << "Starting LLL method '" << LLL_METHOD_STR[method] << "'" << endl
663 << " integer type '" << INT_TYPE_STR[int_type] << "'" << endl
664 << " floating point type '" << FLOAT_TYPE_STR[sel_ft] << "'" << endl;
665 if (method != LM_PROVED || int_type != ZT_MPZ || sel_ft == FT_DOUBLE)
666 {
667 cerr << " The reduction is not guaranteed";
668 }
669 else if (sel_prec < good_prec)
670 {
671 cerr << " prec < " << good_prec << ", the reduction is not guaranteed";
672 }
673 else
674 {
675 cerr << " prec >= " << good_prec << ", the reduction is guaranteed";
676 }
677 cerr << endl;
678 }
679
680 // Applies the selected method
681 int status;
682 if (sel_ft == FT_DOUBLE)
683 {
684 status = lll_reduction_zf<ZT, double>(b, u, u_inv, delta, eta, method, flags);
685 }
686 #ifdef FPLLL_WITH_LONG_DOUBLE
687 else if (sel_ft == FT_LONG_DOUBLE)
688 {
689 status = lll_reduction_zf<ZT, long double>(b, u, u_inv, delta, eta, method, flags);
690 }
691 #endif
692 #ifdef FPLLL_WITH_DPE
693 else if (sel_ft == FT_DPE)
694 {
695 status = lll_reduction_zf<ZT, dpe_t>(b, u, u_inv, delta, eta, method, flags);
696 }
697 #endif
698 #ifdef FPLLL_WITH_QD
699 else if (sel_ft == FT_DD)
700 {
701 unsigned int old_cw;
702 fpu_fix_start(&old_cw);
703 status = lll_reduction_zf<ZT, dd_real>(b, u, u_inv, delta, eta, method, flags);
704 fpu_fix_end(&old_cw);
705 }
706 else if (sel_ft == FT_QD)
707 {
708 unsigned int old_cw;
709 fpu_fix_start(&old_cw);
710 status = lll_reduction_zf<ZT, qd_real>(b, u, u_inv, delta, eta, method, flags);
711 fpu_fix_end(&old_cw);
712 }
713 #endif
714 else if (sel_ft == FT_MPFR)
715 {
716 int old_prec = FP_NR<mpfr_t>::set_prec(sel_prec);
717 status = lll_reduction_zf<ZT, mpfr_t>(b, u, u_inv, delta, eta, method, flags);
718 FP_NR<mpfr_t>::set_prec(old_prec);
719 }
720 else
721 {
722 if (0 <= sel_ft && sel_ft <= FT_MPFR)
723 {
724 // it's a valid choice but we don't have support for it
725 FPLLL_ABORT("Compiled without support for LLL reduction with " << FLOAT_TYPE_STR[sel_ft]);
726 }
727 else
728 {
729 FPLLL_ABORT("Floating point type " << sel_ft << "not supported in LLL");
730 }
731 }
732 zeros_first(b, u, u_inv);
733 return status;
734 }
735
736 // Verify if b is hlll reduced according to delta and eta
737 // For FT != dpe and FT != mpfr
738 // This function is not used, but can be used during a testing step.
739 template <class ZT, class FT>
is_hlll_reduced_zf(ZZ_mat<ZT> & b,ZZ_mat<ZT> & u,ZZ_mat<ZT> & u_inv,double delta,double eta,double theta)740 int is_hlll_reduced_zf(ZZ_mat<ZT> &b, ZZ_mat<ZT> &u, ZZ_mat<ZT> &u_inv, double delta, double eta,
741 double theta)
742 {
743 if (b.get_rows() == 0 || b.get_cols() == 0)
744 return RED_SUCCESS;
745
746 int householder_flags = HOUSEHOLDER_DEFAULT | HOUSEHOLDER_ROW_EXPO;
747 MatHouseholder<Z_NR<ZT>, FP_NR<FT>> m(b, u, u_inv, householder_flags);
748
749 return is_hlll_reduced<Z_NR<ZT>, FP_NR<FT>>(m, delta, eta, theta);
750 }
751
752 // Verify if b is hlll reduced according to delta and eta
753 // For FT == dpe or FT == mpfr
754 template <class ZT, class FT>
is_hlll_reduced_pr(ZZ_mat<ZT> & b,ZZ_mat<ZT> & u,ZZ_mat<ZT> & u_inv,double delta,double eta,double theta)755 int is_hlll_reduced_pr(ZZ_mat<ZT> &b, ZZ_mat<ZT> &u, ZZ_mat<ZT> &u_inv, double delta, double eta,
756 double theta)
757 {
758 if (b.get_rows() == 0 || b.get_cols() == 0)
759 return RED_SUCCESS;
760
761 int householder_flags = HOUSEHOLDER_DEFAULT;
762 MatHouseholder<Z_NR<ZT>, FP_NR<FT>> m(b, u, u_inv, householder_flags);
763
764 return is_hlll_reduced<Z_NR<ZT>, FP_NR<FT>>(m, delta, eta, theta);
765 }
766
767 template <class ZT>
hlll_reduction_wrapper(ZZ_mat<ZT> &,ZZ_mat<ZT> &,ZZ_mat<ZT> &,double,double,double,double,FloatType,int,int)768 int hlll_reduction_wrapper(ZZ_mat<ZT> &, ZZ_mat<ZT> &, ZZ_mat<ZT> &, double, double, double, double,
769 FloatType, int, int)
770 {
771 FPLLL_ABORT("The wrapper method works only with integer type mpz");
772 return RED_LLL_FAILURE;
773 }
774
775 template <>
hlll_reduction_wrapper(ZZ_mat<mpz_t> & b,ZZ_mat<mpz_t> & u,ZZ_mat<mpz_t> & u_inv,double delta,double eta,double theta,double c,FloatType float_type,int precision,int flags)776 int hlll_reduction_wrapper(ZZ_mat<mpz_t> &b, ZZ_mat<mpz_t> &u, ZZ_mat<mpz_t> &u_inv, double delta,
777 double eta, double theta, double c, FloatType float_type, int precision,
778 int flags)
779 {
780 FPLLL_CHECK(float_type == FT_DEFAULT,
781 "The floating point type cannot be specified with the wrapper method");
782 FPLLL_CHECK(precision == 0, "The precision cannot be specified with the wrapper method");
783 Wrapper wrapper(b, u, u_inv, delta, eta, theta, c, flags);
784 wrapper.hlll();
785 zeros_first(b, u, u_inv);
786 return wrapper.status;
787 }
788
789 template <class ZT, class FT>
hlll_reduction_zf(ZZ_mat<ZT> & b,ZZ_mat<ZT> & u,ZZ_mat<ZT> & u_inv,double delta,double eta,double theta,double c,LLLMethod method,int flags)790 int hlll_reduction_zf(ZZ_mat<ZT> &b, ZZ_mat<ZT> &u, ZZ_mat<ZT> &u_inv, double delta, double eta,
791 double theta, double c, LLLMethod method, int flags)
792 {
793 if (b.get_rows() == 0 || b.get_cols() == 0)
794 return RED_SUCCESS;
795 int householder_flags = HOUSEHOLDER_DEFAULT;
796 if (method == LM_FAST)
797 {
798 householder_flags |= HOUSEHOLDER_ROW_EXPO | HOUSEHOLDER_OP_FORCE_LONG;
799 // householder_flags |= HOUSEHOLDER_ROW_EXPO;
800 }
801 MatHouseholder<Z_NR<ZT>, FP_NR<FT>> m(b, u, u_inv, householder_flags);
802 HLLLReduction<Z_NR<ZT>, FP_NR<FT>> hlll_obj(m, delta, eta, theta, c, flags);
803 hlll_obj.hlll();
804
805 return hlll_obj.get_status();
806 }
807
808 template <class ZT>
hlll_reduction_z(ZZ_mat<ZT> & b,ZZ_mat<ZT> & u,ZZ_mat<ZT> & u_inv,double delta,double eta,double theta,double c,LLLMethod method,IntType int_type,FloatType float_type,int precision,int flags,bool nolll)809 int hlll_reduction_z(ZZ_mat<ZT> &b, ZZ_mat<ZT> &u, ZZ_mat<ZT> &u_inv, double delta, double eta,
810 double theta, double c, LLLMethod method, IntType int_type,
811 FloatType float_type, int precision, int flags, bool nolll)
812 {
813 FPLLL_CHECK(method != LM_HEURISTIC, "HLLL heuristic is not implemented.");
814
815 int sel_prec = 0;
816 int status = -1;
817 /* computes the parameters required for the proved version */
818 int good_prec = hlll_min_prec(b.get_rows(), b.get_cols(), delta, eta, theta, c);
819
820 // If nolll, just verify if the basis is reduced or not
821 /*
822 * FIXME: for an unknow reason, this test can use a lot of RAM. Example:
823 * latticegen n 613 2048 q | fplll -a hlll | fplll -a hlll -nolll
824 * uses more than 16 GB of RAM. It is advised to use for now the binary
825 * isreduced provided inside hplll
826 * latticegen n 613 2048 q | fplll -a hlll | isreduced
827 */
828 if (nolll)
829 {
830 sel_prec = (precision != 0) ? precision : good_prec;
831
832 if (flags & LLL_VERBOSE)
833 {
834 cerr << "Starting HLLL method 'verification'" << endl
835 << " integer type '" << INT_TYPE_STR[int_type] << "'" << endl
836 << " floating point type 'mpfr_t'" << endl;
837
838 if (sel_prec < good_prec)
839 cerr << " prec < " << good_prec << ", the verification is not guaranteed";
840 else
841 cerr << " prec >= " << good_prec << ", the verification is guaranteed";
842
843 cerr << endl;
844 }
845
846 int old_prec = FP_NR<mpfr_t>::set_prec(sel_prec);
847
848 status = is_hlll_reduced_pr<ZT, mpfr_t>(b, u, u_inv, delta, eta, theta);
849
850 if (flags & LLL_VERBOSE)
851 {
852 if (status == RED_SUCCESS)
853 cerr << "Basis is reduced";
854 else
855 cerr << "Basis is not reduced";
856 cerr << endl;
857 }
858
859 FP_NR<mpfr_t>::set_prec(old_prec);
860
861 return status;
862 }
863
864 /* switch to wrapper */
865 if (method == LM_WRAPPER)
866 return hlll_reduction_wrapper(b, u, u_inv, delta, eta, theta, c, float_type, precision, flags);
867
868 /* sets the parameters and checks the consistency */
869 if (method == LM_PROVED)
870 {
871 sel_prec = (precision != 0) ? precision : good_prec;
872 }
873 else
874 {
875 sel_prec = (precision != 0) ? precision : PREC_DOUBLE;
876 }
877
878 FloatType sel_ft = float_type;
879
880 /* if manually input precision */
881 if (precision != 0)
882 {
883 if (sel_ft == FT_DEFAULT)
884 {
885 sel_ft = FT_MPFR;
886 }
887 FPLLL_CHECK(sel_ft == FT_MPFR,
888 "The floating type must be mpfr when the precision is specified");
889 }
890
891 if (sel_ft == FT_DEFAULT)
892 {
893 if (method == LM_FAST)
894 sel_ft = FT_DOUBLE;
895 #ifdef FPLLL_WITH_DPE
896 else if (sel_prec <= static_cast<int>(FP_NR<dpe_t>::get_prec()))
897 sel_ft = FT_DPE;
898 #endif
899 #ifdef FPLLL_WITH_QD
900 else if (sel_prec <= static_cast<int>(FP_NR<dd_real>::get_prec()))
901 sel_ft = FT_DD;
902 else if (sel_prec <= static_cast<int>(FP_NR<qd_real>::get_prec()))
903 sel_ft = FT_QD;
904 #endif
905 else
906 sel_ft = FT_MPFR;
907 }
908 else if (method == LM_FAST &&
909 (sel_ft != FT_DOUBLE && sel_ft != FT_LONG_DOUBLE && sel_ft != FT_DD && sel_ft != FT_QD))
910 {
911 FPLLL_ABORT("'double' or 'long double' or 'dd' or 'qd' required for "
912 << LLL_METHOD_STR[method]);
913 }
914
915 if (sel_ft == FT_DOUBLE)
916 sel_prec = FP_NR<double>::get_prec();
917 #ifdef FPLLL_WITH_LONG_DOUBLE
918 else if (sel_ft == FT_LONG_DOUBLE)
919 sel_prec = FP_NR<long double>::get_prec();
920 #endif
921 #ifdef FPLLL_WITH_DPE
922 else if (sel_ft == FT_DPE)
923 sel_prec = FP_NR<dpe_t>::get_prec();
924 #endif
925 #ifdef FPLLL_WITH_QD
926 else if (sel_ft == FT_DD)
927 sel_prec = FP_NR<dd_real>::get_prec();
928 else if (sel_ft == FT_QD)
929 sel_prec = FP_NR<qd_real>::get_prec();
930 #endif
931
932 if (flags & LLL_VERBOSE)
933 {
934 cerr << "Starting HLLL method '" << LLL_METHOD_STR[method] << "'" << endl
935 << " integer type '" << INT_TYPE_STR[int_type] << "'" << endl
936 << " floating point type '" << FLOAT_TYPE_STR[sel_ft] << "'" << endl;
937 if (method != LM_PROVED || int_type != ZT_MPZ || sel_ft == FT_DOUBLE)
938 {
939 cerr << " The reduction is not guaranteed";
940 }
941 else if (sel_prec < good_prec)
942 {
943 cerr << " prec < " << good_prec << ", the reduction is not guaranteed";
944 }
945 else
946 {
947 cerr << " prec >= " << good_prec << ", the reduction is guaranteed";
948 }
949 cerr << endl;
950 }
951
952 // Applies the selected method
953 if (sel_ft == FT_DOUBLE)
954 status = hlll_reduction_zf<ZT, double>(b, u, u_inv, delta, eta, theta, c, method, flags);
955 #ifdef FPLLL_WITH_LONG_DOUBLE
956 else if (sel_ft == FT_LONG_DOUBLE)
957 status = hlll_reduction_zf<ZT, long double>(b, u, u_inv, delta, eta, theta, c, method, flags);
958 #endif
959 #ifdef FPLLL_WITH_DPE
960 else if (sel_ft == FT_DPE)
961 status = hlll_reduction_zf<ZT, dpe_t>(b, u, u_inv, delta, eta, theta, c, method, flags);
962 #endif
963 #ifdef FPLLL_WITH_QD
964 else if (sel_ft == FT_DD)
965 {
966 unsigned int old_cw;
967 fpu_fix_start(&old_cw);
968 status = hlll_reduction_zf<ZT, dd_real>(b, u, u_inv, delta, eta, theta, c, method, flags);
969 fpu_fix_end(&old_cw);
970 }
971 else if (sel_ft == FT_QD)
972 {
973 unsigned int old_cw;
974 fpu_fix_start(&old_cw);
975 status = hlll_reduction_zf<ZT, qd_real>(b, u, u_inv, delta, eta, theta, c, method, flags);
976 fpu_fix_end(&old_cw);
977 }
978 #endif
979 else if (sel_ft == FT_MPFR)
980 {
981 int old_prec = FP_NR<mpfr_t>::set_prec(sel_prec);
982 status = hlll_reduction_zf<ZT, mpfr_t>(b, u, u_inv, delta, eta, theta, c, method, flags);
983 FP_NR<mpfr_t>::set_prec(old_prec);
984 }
985 else
986 {
987 if (0 <= sel_ft && sel_ft <= FT_MPFR)
988 {
989 // it's a valid choice but we don't have support for it
990 FPLLL_ABORT("Compiled without support for LLL reduction with " << FLOAT_TYPE_STR[sel_ft]);
991 }
992 else
993 {
994 FPLLL_ABORT("Floating point type " << sel_ft << "not supported in LLL");
995 }
996 }
997 zeros_first(b, u, u_inv);
998
999 return status;
1000 }
1001
1002 /**
1003 * We define LLL for each input type instead of using a template,
1004 * in order to force the compiler to instantiate the functions.
1005 */
1006 #define FPLLL_DEFINE_LLL(T, id_t) \
1007 int lll_reduction(ZZ_mat<T> &b, double delta, double eta, LLLMethod method, \
1008 FloatType float_type, int precision, int flags) \
1009 { \
1010 ZZ_mat<T> empty_mat; /* Empty u -> transform disabled */ \
1011 return lll_reduction_z<T>(b, empty_mat, empty_mat, delta, eta, method, id_t, float_type, \
1012 precision, flags); \
1013 } \
1014 \
1015 int lll_reduction(ZZ_mat<T> &b, ZZ_mat<T> &u, double delta, double eta, LLLMethod method, \
1016 FloatType float_type, int precision, int flags) \
1017 { \
1018 ZZ_mat<T> empty_mat; \
1019 if (!u.empty()) \
1020 u.gen_identity(b.get_rows()); \
1021 return lll_reduction_z<T>(b, u, empty_mat, delta, eta, method, id_t, float_type, precision, \
1022 flags); \
1023 } \
1024 \
1025 int lll_reduction(ZZ_mat<T> &b, ZZ_mat<T> &u, ZZ_mat<T> &u_inv, double delta, double eta, \
1026 LLLMethod method, FloatType float_type, int precision, int flags) \
1027 { \
1028 if (!u.empty()) \
1029 u.gen_identity(b.get_rows()); \
1030 if (!u_inv.empty()) \
1031 u_inv.gen_identity(b.get_rows()); \
1032 u_inv.transpose(); \
1033 int status = \
1034 lll_reduction_z<T>(b, u, u_inv, delta, eta, method, id_t, float_type, precision, flags); \
1035 u_inv.transpose(); \
1036 return status; \
1037 }
1038
1039 FPLLL_DEFINE_LLL(mpz_t, ZT_MPZ)
1040
1041 #ifdef FPLLL_WITH_ZLONG
1042 FPLLL_DEFINE_LLL(long, ZT_LONG)
1043 #endif
1044
1045 #ifdef FPLLL_WITH_ZDOUBLE
1046 FPLLL_DEFINE_LLL(double, ZT_DOUBLE)
1047 #endif
1048
1049 // HLLL
1050
1051 /**
1052 * We define HLLL for each input type instead of using a template,
1053 * in order to force the compiler to instantiate the functions.
1054 */
1055 #define FPLLL_DEFINE_HLLL(T, id_t) \
1056 int hlll_reduction(ZZ_mat<T> &b, double delta, double eta, double theta, double c, \
1057 LLLMethod method, FloatType float_type, int precision, int flags, bool nolll) \
1058 { \
1059 ZZ_mat<T> empty_mat; /* Empty u -> transform disabled */ \
1060 return hlll_reduction_z<T>(b, empty_mat, empty_mat, delta, eta, theta, c, method, id_t, \
1061 float_type, precision, flags, nolll); \
1062 } \
1063 \
1064 int hlll_reduction(ZZ_mat<T> &b, ZZ_mat<T> &u, double delta, double eta, double theta, double c, \
1065 LLLMethod method, FloatType float_type, int precision, int flags, bool nolll) \
1066 { \
1067 ZZ_mat<T> empty_mat; \
1068 if (!u.empty()) \
1069 u.gen_identity(b.get_rows()); \
1070 return hlll_reduction_z<T>(b, u, empty_mat, delta, eta, theta, c, method, id_t, float_type, \
1071 precision, flags, nolll); \
1072 } \
1073 \
1074 int hlll_reduction(ZZ_mat<T> &b, ZZ_mat<T> &u, ZZ_mat<T> &u_inv, double delta, double eta, \
1075 double theta, double c, LLLMethod method, FloatType float_type, \
1076 int precision, int flags, bool nolll) \
1077 { \
1078 if (!u.empty()) \
1079 u.gen_identity(b.get_rows()); \
1080 if (!u_inv.empty()) \
1081 u_inv.gen_identity(b.get_rows()); \
1082 u_inv.transpose(); \
1083 int status = hlll_reduction_z<T>(b, u, u_inv, delta, eta, theta, c, method, id_t, float_type, \
1084 precision, flags, nolll); \
1085 u_inv.transpose(); \
1086 return status; \
1087 }
1088
1089 FPLLL_DEFINE_HLLL(mpz_t, ZT_MPZ)
1090
1091 #ifdef FPLLL_WITH_ZLONG
1092 FPLLL_DEFINE_HLLL(long, ZT_LONG)
1093 #endif
1094
1095 #ifdef FPLLL_WITH_ZDOUBLE
1096 FPLLL_DEFINE_HLLL(double, ZT_DOUBLE)
1097 #endif
1098
1099 FPLLL_END_NAMESPACE
1100