plll.hpp

Go to the documentation of this file.

/*
    Copyright (c) 2011-2014 University of Zurich
    
    Permission is hereby granted, free of charge, to any person obtaining a copy
    of this software and associated documentation files (the "Software"), to deal
    in the Software without restriction, including without limitation the rights
    to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
    copies of the Software, and to permit persons to whom the Software is
    furnished to do so, subject to the following conditions:
    
    The above copyright notice and this permission notice shall be included in
    all copies or substantial portions of the Software.
    
    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
    IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
    FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
    AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
    LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
    OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
    THE SOFTWARE.
*/

#ifndef PLLL_INCLUDE_GUARD__PLLL2_LLL_HPP
#define PLLL_INCLUDE_GUARD__PLLL2_LLL_HPP

#include <plll/config.hpp>
#include <plll/arithmetic.hpp>
#include <plll/arithmetic-nint.hpp>
#include <plll/matrix.hpp>
#include <exception>
#include <iostream>
#include <limits>
#include <boost/function.hpp>

namespace plll
{
    class LatticeReductionImpl;
    
    class LatticeReduction
    {
    private:
        std::auto_ptr<LatticeReductionImpl> d_impl; 
        
        // Disable copy constructor and operator
        LatticeReduction(const LatticeReduction &);
        LatticeReduction & operator = (const LatticeReduction &);
        
    public:
        class stop_reduction : public std::exception
        {
        public:
            virtual ~stop_reduction() PLLL_INTERNAL_NOTHROW_POSTFIX_ENFORCE
            {
            }
            
            virtual const char * what() const PLLL_INTERNAL_NOTHROW_POSTFIX_ENFORCE;
        };
        
        class stop_enumeration : public std::exception
        {
        public:
            virtual ~stop_enumeration() PLLL_INTERNAL_NOTHROW_POSTFIX_ENFORCE
            {
            }
            
            virtual const char * what() const PLLL_INTERNAL_NOTHROW_POSTFIX_ENFORCE;
        };
        
        enum Arithmetic
        {
            A_Rational,
            A_Real,
            A_LongDouble,
            A_Double,
            A_DoubleDouble,
            A_QuadDouble,
            A_Default = A_LongDouble
        };
        
        enum Integers
        {
            I_Auto,
            I_ArbitraryPrecision,
            I_LongInt,
            I_Default = I_Auto
        };
        
        enum GramSchmidt
        {
            G_Classic,
            G_ClassicInteger,
            G_Givens,
            G_NumStable,
            G_Default = G_NumStable
        };
        
        enum Transform
        {
            T_Normal,
            T_Inverse
        };
        
        enum LLLMode
        {
            LLL_Classic,
            LLL_Unprojected,
            LLL_Siegel,
            LLL_Default = LLL_Classic
        };
        
        enum BKZMode
        {
            BKZ_SchnorrEuchner,
            BKZ_Simplified,
            BKZ_HanrotPujolStehleHKZ,
            BKZ_HanrotPujolStehleSVP,
            BKZ_PrimalDual,
            BKZ_SlideReduction,
            BKZ_ImprovedSlideReduction,
            BKZ_ImprovedSlideReduction2,
            BKZ_ImprovedSlideReduction3,
            BKZ_SemiBlock2k,
            BKZ_SamplingReduction,
            BKZ_Experimental, // An experimental variant which should *not* be used.
            BKZ_Default = BKZ_SchnorrEuchner
        };
        
        enum SVPMode
        {
            SVP_KannanSchnorrEuchner,
            SVP_ParallelKannanSchnorrEuchner,
            SVP_SchnorrFast,
            SVP_VoronoiCellSVP,
            SVP_ListSieve,
            SVP_ListSieveBirthday,
            SVP_GaussSieve,
            SVP_Default = SVP_ParallelKannanSchnorrEuchner
        };
        
        enum DIMethod
        {
            DI_None,
            DI_Classic,
            DI_MinimizePotential1,
            DI_MinimizePotential2,
            DI_Default = DI_None
        };
        
        enum DIChoice
        {
            DIC_First,
            DIC_Block,
            DIC_FirstBlock,
            DIC_All,
            DIC_Default = DIC_All
        };
        
        enum DIMode
        {
            DIM_BeforeSR,
            DIM_AfterSR,
            DIM_Both,
            DIM_Default = DIM_Both
        };
        
        enum VerboseOutputLevel
        {
            VOL_None,
            VOL_Warnings,
            VOL_Informative,
            VOL_Full
        };
        
        enum VerboseLevel
        {
            VL_Error,
            VL_Warning,
            VL_Information,
            VL_Chatter
        };
        
        struct Statistics
        {
            unsigned long swaps;
            unsigned long adds;
            unsigned long adds_pm1;
            unsigned long adds_pm2;
            unsigned long flips;
            unsigned long trans;
            unsigned long sizereductions;
            unsigned long deepinsertions;
            unsigned long enumcalls;
            unsigned long enumfails;
            unsigned long vectorinsertions;
            unsigned long vectorinsertions_rearrange;
            void reset(); 
            Statistics(); 
        };
        
        class GramSchmidtInformer
        {
        protected:
            GramSchmidtInformer() { }
            virtual ~GramSchmidtInformer() { }
            
        public:
            virtual double getGSCoefficientD(unsigned, unsigned) const = 0;
            virtual long double getGSCoefficientLD(unsigned, unsigned) const = 0;
            virtual arithmetic::Real getGSCoefficientR(unsigned, unsigned, const arithmetic::RealContext &) const = 0;
            virtual double getGSSqNormD(unsigned) const = 0;
            virtual long double getGSSqNormLD(unsigned) const = 0;
            virtual arithmetic::Real getGSSqNormR(unsigned, const arithmetic::RealContext &) const = 0;
            virtual double computeProjectionLengthD(unsigned k, unsigned b,
                                                    const linalg::math_rowvector<arithmetic::Integer> & vec) const = 0;
            virtual long double computeProjectionLengthLD(unsigned k, unsigned b,
                                                          const linalg::math_rowvector<arithmetic::Integer> & vec) const = 0;
            virtual arithmetic::Real computeProjectionLengthR(unsigned k, unsigned b,
                                                              const linalg::math_rowvector<arithmetic::Integer> & vec,
                                                              const arithmetic::RealContext &) const = 0;
            inline arithmetic::Real getGSCoefficientR(unsigned i, unsigned j) const
            {
                return getGSCoefficientR(i, j, arithmetic::getThreadRealContext());
            }
            
            inline arithmetic::Real getGSSqNormR(unsigned i) const
            {
                return getGSSqNormR(i, arithmetic::getThreadRealContext());
            }
            
            inline arithmetic::Real computeProjectionLengthR(unsigned k, unsigned b,
                                                             const linalg::math_rowvector<arithmetic::Integer> & vec) const
            {
                return computeProjectionLengthR(k, b, vec, arithmetic::getThreadRealContext());
            }
        };
        
        typedef boost::function<void(const linalg::math_matrix<arithmetic::Integer> &)> CallbackFunction;
        typedef boost::function<void(const linalg::math_matrix<arithmetic::NInt<long int> > &)> CallbackFunction_LI;
        typedef boost::function<void(const linalg::math_matrix<arithmetic::Integer> &, unsigned,
                                     const arithmetic::Integer &)> MinCallbackFunction;
        typedef boost::function<void(const linalg::math_matrix<arithmetic::NInt<long int> > &, unsigned,
                                     const arithmetic::NInt<long int> &)> MinCallbackFunction_LI;
        typedef boost::function<void(const linalg::math_matrix<arithmetic::Integer> & basis,
                                     int p,
                                     const linalg::math_rowvector<arithmetic::Integer> & vec)> EnumCallbackFunction;
        typedef boost::function<void(const linalg::math_matrix<arithmetic::NInt<long int> > & basis,
                                     int p,
                                     const linalg::math_rowvector<arithmetic::NInt<long int> > & vec)> EnumCallbackFunction_LI;
        typedef boost::function<bool(const linalg::math_matrix<arithmetic::Integer> &,
                                     arithmetic::RealContext &,
                                     arithmetic::Real & T)> AnnealCallbackFunction;
        typedef boost::function<bool(const linalg::math_matrix<arithmetic::Integer> &,
                                     int k,
                                     arithmetic::RealContext &,
                                     arithmetic::RandomNumberGenerator &,
                                     arithmetic::Real & T,
                                     GramSchmidtInformer *)> LLL_AnnealFunction;
        typedef boost::function<bool (const linalg::math_matrix<arithmetic::Integer> &,
                                      int k, int windowsize,
                                      linalg::math_rowvector<arithmetic::Integer> & lincomb,
                                      arithmetic::RealContext &,
                                      arithmetic::RandomNumberGenerator &,
                                      arithmetic::Real & T,
                                      GramSchmidtInformer *)> BKZ_AnnealFunction;
        typedef boost::function<void(VerboseLevel, const std::string &)> VerboseFunction;
        
        LatticeReduction();
        LatticeReduction(const linalg::math_matrix<arithmetic::Integer> & lattice);
        template<typename IType>
        LatticeReduction(const linalg::math_matrix<arithmetic::NInt<IType> > & lattice);
#if __cplusplus >= 201103L
        LatticeReduction(linalg::math_matrix<arithmetic::Integer> && lattice);
        LatticeReduction(LatticeReduction &&);
        LatticeReduction & operator = (LatticeReduction &&);
#endif
        ~LatticeReduction();
        void setLattice(const linalg::math_matrix<arithmetic::Integer> & lattice);
        template<typename IType>
        void setLattice(const linalg::math_matrix<arithmetic::NInt<IType> > & lattice);
#if __cplusplus >= 201103L
        void setLattice(linalg::math_matrix<arithmetic::Integer> && lattice);
#endif
        const linalg::math_matrix<arithmetic::Integer> & getLattice() const;
        
        unsigned rank() const;
        unsigned dimension() const;
        
        void setArithmetic(Arithmetic);
        Arithmetic getArithmetic() const;
        bool ensurePrecision(unsigned long);
        void setIntegers(Integers);
        Integers getIntegers() const;
        
        void setGramSchmidt(GramSchmidt);
        void setGramSchmidtRestart(bool);
        GramSchmidt getGramSchmidt() const;
        bool getGramSchmidtRestart() const;
        
        void forceGSRebuild(bool makeSureAllComputed = false);
        double getGSCoefficientD(unsigned, unsigned) const;
        long double getGSCoefficientLD(unsigned, unsigned) const;
        arithmetic::Real getGSCoefficientR(unsigned, unsigned) const;
        arithmetic::Real getGSCoefficientR(unsigned, unsigned, const arithmetic::RealContext &) const;
        double getGSSqNormD(unsigned) const;
        long double getGSSqNormLD(unsigned) const;
        arithmetic::Real getGSSqNormR(unsigned) const;
        arithmetic::Real getGSSqNormR(unsigned, const arithmetic::RealContext &) const;
        
        void modFlip(unsigned);
        void modSwap(unsigned, unsigned);
        void modAdd(unsigned i, unsigned j, const arithmetic::Integer & m);
        
        void enableTransform(Transform = T_Normal);
        void disableTransform();
        bool isTransformationRecorded() const;
        Transform getTransformationMode() const;
        const linalg::math_matrix<arithmetic::Integer> * getTransformation() const;
        
        void setSVPMode(SVPMode);
        SVPMode getSVPMode() const;
        
        void setMaximalCoreUsage(unsigned);
        unsigned getMaximalCoreUsage();
        
        void setCallbackFunction(const CallbackFunction &, const CallbackFunction_LI & = CallbackFunction_LI());
        void setCallbackFunction(const CallbackFunction_LI &);
        void setCallbackInterval(double = 60.0*5.0);
        std::pair<CallbackFunction, CallbackFunction_LI> getCallbackFunction() const;
        double getCallbackInterval() const;
        void setMinCallbackFunction(const MinCallbackFunction &, const MinCallbackFunction_LI & = MinCallbackFunction_LI());
        void setMinCallbackFunction(const MinCallbackFunction_LI &);
        std::pair<MinCallbackFunction, MinCallbackFunction_LI> getMinCallbackFunction() const;
        void setEnumCallbackFunction(const EnumCallbackFunction &, const EnumCallbackFunction_LI & = EnumCallbackFunction_LI());
        void setEnumCallbackFunction(const EnumCallbackFunction_LI &);
        std::pair<EnumCallbackFunction, EnumCallbackFunction_LI> getEnumCallbackFunction();
        
        void setDefaultAnnealing();
        void setDefaultAnnealingLLL();
        void setDefaultAnnealingBKZ();
        void setAnnealing(const AnnealCallbackFunction &, const LLL_AnnealFunction &, const BKZ_AnnealFunction &);
        void setAnnealingLLL(const AnnealCallbackFunction &, const LLL_AnnealFunction &);
        void setAnnealingBKZ(const AnnealCallbackFunction &, const BKZ_AnnealFunction &);
        void disableAnnealing();
        void disableAnnealingLLL();
        void disableAnnealingBKZ();
        bool isAnnealingLLLEnabled() const;
        bool isAnnealingBKZEnabled() const;
        
        void setDeepInsertionMethod(DIMethod, DIMode = DIM_Default);
        void setDeepInsertionMode(DIMode);
        void setDeepInsertionChoice(DIChoice, unsigned = 1);
        DIMethod getDeepInsertionMethod() const;
        DIMode getDeepInsertionMode() const;
        DIChoice getDeepInsertionChoice() const;
        unsigned getDeepInsertionBlocksize() const;
        
        void setRange(unsigned begin, unsigned end = std::numeric_limits<unsigned>::max());
        std::pair<unsigned, unsigned> getRange() const;
        
        void sort(bool projected = false);
        void sizereduction();
        void lll(double alpha = 0.99, LLLMode mode = LLL_Classic);
        void bkz(double alpha = 0.99, unsigned blocksize = 20, BKZMode mode = BKZ_SchnorrEuchner);
        void hkz(bool dual = false);
        void svp(bool make_basis = true, bool extreme = false, bool dual = false);
        
        bool isSizeReduced() const;
        bool isLLLBasis(double alpha = 0.99, LLLMode mode = LLL_Classic) const;
        bool isBKZBasis(double alpha = 0.99, unsigned blocksize = 20, BKZMode mode = BKZ_SchnorrEuchner) const;
        bool isHKZBasis(bool dual = false) const;
        bool isSVPBasis(bool dual = false) const;
        
        const Statistics & getStatistics() const;
        void resetStatistics();
        
        void setVerbose(VerboseOutputLevel level, const VerboseFunction & = 0);
        VerboseOutputLevel getVerboseOutputLevel();
        const VerboseFunction & getVerboseFunction();
    };
}

#endif