bkz.h

Go to the documentation of this file.

/* Copyright (C) 2011 Xavier Pujol
   (C) 2014-2016 Martin R. Albrecht
   (C) 2016 Michael Walter
 
   This file is part of fplll. fplll is free software: you
   can redistribute it and/or modify it under the terms of the GNU Lesser
   General Public License as published by the Free Software Foundation,
   either version 2.1 of the License, or (at your option) any later version.
 
   fplll is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
   GNU Lesser General Public License for more details.
 
   You should have received a copy of the GNU Lesser General Public License
   along with fplll. If not, see <http://www.gnu.org/licenses/>. */
 
#ifndef FPLLL_BKZ_H
#define FPLLL_BKZ_H
 
#include "bkz_param.h"
#include "enum/enumerate.h"
#include "enum/evaluator.h"
#include "lll.h"
 
FPLLL_BEGIN_NAMESPACE
 
template <class ZT, class FT> class BKZAutoAbort
{
public:
  BKZAutoAbort(MatGSOInterface<ZT, FT> &m, int num_rows, int start_row = 0)
      : m(m), old_slope(numeric_limits<double>::max()), no_dec(-1), num_rows(num_rows),
        start_row(start_row)
  {
  }
 
  bool test_abort(double scale = 1.0, int maxNoDec = 5);
 
private:
  MatGSOInterface<ZT, FT> &m;
  double old_slope;
  int no_dec;
  int num_rows;
  int start_row;
};
 
template <class ZT, class FT> class BKZReduction
{
public:
  BKZReduction(MatGSOInterface<ZT, FT> &m, LLLReduction<ZT, FT> &lll_obj, const BKZParam &param);
  ~BKZReduction();
 
  bool svp_preprocessing(int kappa, unsigned int block_size, const BKZParam &param);
 
  bool svp_postprocessing(int kappa, int block_size, const vector<FT> &solution, bool dual = false);
 
  bool svp_reduction(int kappa, int block_size, const BKZParam &param, bool dual = false);
 
  bool tour(const int loop, int &kappa_max, const BKZParam &param, int min_row, int max_row);
 
  bool sd_tour(const int loop, const BKZParam &param, int min_row, int max_row);
 
  bool hkz(int &kappa_max, const BKZParam &param, int min_row, int max_row);
 
  bool slide_tour(const int loop, const BKZParam &param, int min_row, int max_row);
 
  bool bkz();
 
  void rerandomize_block(int min_row, int max_row, int density);
 
  void dump_gso(const std::string &filename, bool append, const std::string &step, const int loop,
                const double time);
 
  int status;
 
  long nodes;
 
private:
  void print_tour(const int loop, int min_row, int max_row);
  void print_params(const BKZParam &param, ostream &out);
 
  bool set_status(int new_status);
 
  const PruningParams &get_pruning(int kappa, unsigned int block_size, const BKZParam &par) const;
 
  // handles the general case of inserting a vector into the (dual) basis, i.e.
  // when none of the coefficients are \pm 1
  bool svp_postprocessing_generic(int kappa, int block_size, const vector<FT> &solution,
                                  bool dual = false);
  // a truncated tour: svp reducing from min_row to max_row without decreasing the window
  // size (simply returns when the last block is reduced)
  bool trunc_tour(int &kappa_max, const BKZParam &param, int min_row, int max_row);
  // a truncated dual tour: dual svp reducing from max_row to min_row without decreasing
  // the window size (simply returns when the first block is reduced)
  bool trunc_dtour(const BKZParam &param, int min_row, int max_row);
 
  const BKZParam &param;
  int num_rows;
  MatGSOInterface<ZT, FT> &m;
  LLLReduction<ZT, FT> &lll_obj;
  // evaluator passed to the enumeration object to handle solutions found
  FastEvaluator<FT> evaluator;
  // slack variable for svp reductions
  FT delta;
 
  // an acronym for the type of block reduction used, for reporting purposes
  const char *algorithm;
  // current value of the potential function as defined in the slide reduction paper
  // used to reliably determine terminating condition during slide reduction
  FT sld_potential;
 
  // Temporary data
  const vector<FT> empty_target, empty_sub_tree;
  FT max_dist, delta_max_dist;
  double cputime_start;
};
 
int bkz_reduction(ZZ_mat<mpz_t> *B, ZZ_mat<mpz_t> *U, const BKZParam &param,
                  FloatType float_type = FT_DEFAULT, int precision = 0);
 
int bkz_reduction(ZZ_mat<mpz_t> &b, int block_size, int flags = BKZ_DEFAULT,
                  FloatType float_type = FT_DEFAULT, int precision = 0);
 
int bkz_reduction(ZZ_mat<mpz_t> &b, ZZ_mat<mpz_t> &u, int block_size, int flags = BKZ_DEFAULT,
                  FloatType float_type = FT_DEFAULT, int precision = 0);
 
int hkz_reduction(ZZ_mat<mpz_t> &b, int flags = HKZ_DEFAULT, FloatType float_type = FT_DEFAULT,
                  int precision = 0);
 
FPLLL_END_NAMESPACE
 
#endif