1# -*- coding: utf-8 -*-
2
3#
4# General Includes
5
6from fpylll.gmp.mpz cimport mpz_t
7from fpylll.mpfr.mpfr cimport mpfr_t
8from fpylll.gmp.random cimport gmp_randstate_t
9from libcpp.vector cimport vector
10from libcpp.string cimport string
11from libcpp.pair cimport pair
12from libcpp cimport bool
13from libcpp.functional cimport function
14
15
16cdef extern from "<map>" namespace "std":
17    cdef cppclass multimap[T, U]:
18        cppclass iterator:
19            pair[T,U]& operator*()
20            iterator operator++()
21            iterator operator--()
22            bint operator==(iterator)
23            bint operator!=(iterator)
24            iterator operator=()
25
26        cppclass reverse_iterator:
27            pair[T,U]& operator*()
28            iterator operator++()
29            iterator operator--()
30            bint operator==(reverse_iterator)
31            bint operator!=(reverse_iterator)
32            iterator operator=()
33
34        map()
35        U& operator[](T&)
36        U& at(T&)
37        iterator begin()
38        reverse_iterator rbegin()
39        iterator end()
40        reverse_iterator rend()
41        size_t count(T&)
42        bint empty()
43        void erase(iterator)
44        void erase(iterator, iterator)
45        size_t erase(T&)
46        iterator find(T&)
47        pair[iterator, bint] insert(pair[T,U])
48        size_t size()
49
50
51cdef extern from "fplll/fplll_config.h":
52    """
53    #ifdef FPLLL_WITH_RECURSIVE_ENUM
54    #define FPLLL_HAVE_RECURSIVE_ENUM 1
55    #else
56    #define FPLLL_HAVE_RECURSIVE_ENUM 0
57    #endif
58    """
59    int FPLLL_MAJOR_VERSION
60    int FPLLL_MINOR_VERSION
61    int FPLLL_MICRO_VERSION
62
63    int FPLLL_MAX_ENUM_DIM
64    bool FPLLL_HAVE_RECURSIVE_ENUM
65    int FPLLL_MAX_PARALLEL_ENUM_DIM
66
67#
68# Numbers
69
70cdef extern from "fplll/nr/nr.h" namespace "fplll":
71
72    ctypedef double enumf
73
74    cdef cppclass Z_NR[T]:
75        T& get_data() nogil
76        void set "operator=" (T d) nogil
77        double get_d() nogil
78        long exponent() nogil
79        void set_str(const char* s) nogil
80        int cmp(const Z_NR[T]& m) nogil
81        int sgn() nogil
82
83        void operator=(const Z_NR[T]& z) nogil
84        void operator=(const mpz_t& z) nogil
85        void operator=(long i) nogil
86        int operator<(const Z_NR[T]& a) nogil
87        int operator<(long a) nogil
88        int operator>(const Z_NR[T]& a) nogil
89        int operator>(long a) nogil
90        int operator<=(const Z_NR[T]& a) nogil
91        int operator<=(long a) nogil
92        int operator>=(const Z_NR[T]& a) nogil
93        int operator>=(long a) nogil
94        int operator==(const Z_NR[T]& a) nogil
95        int operator==(long a) nogil
96        int operator!=(const Z_NR[T]& a) nogil
97        int operator!=(long a) nogil
98
99        void add(const Z_NR[T]& a, const Z_NR[T]& b) nogil
100        void add_ui(const Z_NR[T]& a, unsigned int b) nogil
101        void sub(const Z_NR[T]& a, const Z_NR[T]& b) nogil
102        void sub_ui(const Z_NR[T]& a, unsigned int b) nogil
103        void neg(const Z_NR[T]& a) nogil
104        void mul(const Z_NR[T]& a, const Z_NR[T]& b) nogil
105        void mul_si(const Z_NR[T]& a, long b) nogil
106        void mul_ui(const Z_NR[T]& a, unsigned long b) nogil
107        void mul_2si(const Z_NR[T]& a, long b) nogil
108        void div_2si(const Z_NR[T]& a, long b) nogil
109        void addmul(const Z_NR[T]& a, const Z_NR[T]& b) nogil
110        void addmul_ui(const Z_NR[T]& a, unsigned long b) nogil
111        void addmul_si(const Z_NR[T]& a, long b) nogil
112        void submul(const Z_NR[T]& a, const Z_NR[T]& b) nogil
113        void submul_ui(const Z_NR[T]& a, unsigned long b) nogil
114        void abs(const Z_NR[T]& a) nogil
115        void swap(Z_NR[T]& a) nogil
116        void randb(int bits) nogil
117        void randb_si(int bits) nogil
118        void randm(const Z_NR[T]& max) nogil
119        void randm_si(const Z_NR[T]& max) nogil
120
121
122    cdef cppclass FP_NR[T]:
123        T& get_data() nogil
124        double get_d() nogil
125        inline void operator=(const FP_NR[T]& a) nogil
126        inline void operator=(double a) nogil
127
128        @staticmethod
129        unsigned int get_prec() nogil
130
131        @staticmethod
132        unsigned int set_prec(unsigned int) nogil
133
134cdef extern from "fplll/nr/nr.h":
135    cdef struct dpe_struct:
136        pass
137    ctypedef dpe_struct *dpe_t
138
139
140# Random Numbers
141
142
143cdef extern from "fplll/nr/nr.h" namespace "fplll":
144
145    cdef cppclass RandGen:
146        @staticmethod
147        void init()
148
149        @staticmethod
150        void init_with_seed(unsigned long seed)
151
152        @staticmethod
153        void init_with_time()
154
155        @staticmethod
156        void init_with_time2()
157
158        @staticmethod
159        int get_initialized()
160
161        @staticmethod
162        gmp_randstate_t& get_gmp_state()
163
164
165# Definitions & Enums
166
167cdef extern from "fplll/defs.h" namespace "fplll":
168
169    cdef enum RedStatus:
170        RED_SUCCESS
171        RED_GSO_FAILURE
172        RED_BABAI_FAILURE
173        RED_LLL_FAILURE
174        RED_ENUM_FAILURE
175        RED_BKZ_FAILURE
176        RED_BKZ_TIME_LIMIT
177        RED_BKZ_LOOPS_LIMIT
178        RED_STATUS_MAX
179
180    cdef enum LLLFlags:
181        LLL_VERBOSE
182        LLL_EARLY_RED
183        LLL_SIEGEL
184        LLL_DEFAULT
185
186    cdef enum BKZFlags:
187        BKZ_DEFAULT
188        BKZ_VERBOSE
189        BKZ_NO_LLL
190        BKZ_MAX_LOOPS
191        BKZ_MAX_TIME
192        BKZ_BOUNDED_LLL
193        BKZ_AUTO_ABORT
194        BKZ_DUMP_GSO
195        BKZ_GH_BND
196        BKZ_SD_VARIANT
197        BKZ_SLD_RED
198
199    cdef enum LLLMethod:
200        LM_WRAPPER
201        LM_PROVED
202        LM_HEURISTIC
203        LM_FAST
204
205    cdef enum SVPMethod:
206        SVPM_FAST
207        SVPM_PROVED
208
209    cdef enum SVPFlags:
210        SVP_DEFAULT
211        SVP_VERBOSE
212        SVP_OVERRIDE_BND
213
214    cdef enum CVPMethod:
215        CVPM_FAST
216        CVPM_PROVED
217
218    cdef enum CVPFlags:
219        CVP_DEFAULT
220        CVP_VERBOSE
221
222    cdef enum IntType:
223        ZT_MPZ
224        ZT_LONG
225        ZT_DOUBLE
226
227    cdef enum FloatType:
228        FT_DEFAULT
229        FT_DOUBLE
230        FT_LONG_DOUBLE
231        FT_DD
232        FT_QD
233        FT_DPE
234        FT_MPFR
235
236    cdef enum EvaluatorMode:
237        EVALMODE_SV
238        EVALMODE_CV
239        EVALMODE_COUNT
240        EVALMODE_PRINT
241
242    cdef double LLL_DEF_DELTA
243    cdef double LLL_DEF_ETA
244
245
246    const double BKZ_DEF_AUTO_ABORT_SCALE
247    const int BKZ_DEF_AUTO_ABORT_MAX_NO_DEC
248    const double BKZ_DEF_GH_FACTOR
249    const double BKZ_DEF_MIN_SUCCESS_PROBABILITY
250    const int BKZ_DEF_RERANDOMIZATION_DENSITY
251
252# Vectors (only used in some places)
253
254cdef extern from "fplll/nr/numvect.h" namespace "fplll":
255
256    cdef cppclass NumVect[T]:
257
258        cppclass iterator:
259            iterator operator++()
260            iterator operator--()
261            bint operator==(iterator)
262            bint operator!=(iterator)
263            iterator operator=()
264
265        NumVect()
266        NumVect(const NumVect[T]& v)
267        NumVect(int size)
268        NumVect(int size, T &t)
269
270        void operator=(NumVect &v)
271        void swap(NumVect &v)
272
273        const iterator begin()
274        iterator end()
275        int size()
276        bool empty()
277        void resize(int size)
278        void resize(int size, const T &t)
279        void gen_zero(int size)
280
281        void push_back(const T &t)
282        void pop_back()
283        T &front()
284        T &back()
285        void extend(int maxSize)
286        void clear()
287        T &operator[](int i)
288
289        void add(const NumVect[T] &v, int n)
290        void add(const NumVect[T] &v)
291        void sub(const NumVect[T] &v, int n)
292        void sub(const NumVect[T] &v)
293        void mul(const NumVect[T] &v, int n, T c)
294        void mul(const NumVect[T] &v, T c)
295        void addmul(const NumVect[T] &v, T x, int n)
296        void addmul(const NumVect[T] &v, T x)
297        void addmul_2exp(const NumVect[T] &v, const T &x, long expo, T &tmp)
298        void addmul_2exp(const NumVect[T] &v, const T &x, long expo, int n, T &tmp)
299        void addmul_si(const NumVect[T] &v, long x)
300        void addmul_si(const NumVect[T] &v, long x, int n)
301        void addmul_si_2exp(const NumVect[T] &v, long x, long expo, T &tmp)
302        void addmul_si_2exp(const NumVect[T] &v, long x, long expo, int n, T &tmp)
303
304        # (v[first],...,v[last]) becomes (v[first+1],...,v[last],v[first]) */
305        void rotate_left(int first, int last)
306
307        # (v[first],...,v[last]) becomes (v[last],v[first],...,v[last-1]) */
308        void rotate_right(int first, int last)
309
310        # Returns expo >= 0 such that all elements are < 2^expo.
311        long get_max_exponent()
312
313        void fill(long value)
314
315        bool is_zero(int fromCol = 0) const
316
317        int size_nz() const
318
319
320# Matrices over the Integers
321
322cdef extern from "fplll/nr/matrix.h" namespace "fplll":
323    cdef cppclass MatrixRow[T]:
324        T& operator[](int i) nogil
325        int size() nogil
326        int is_zero() nogil
327        int is_zero(int frm) nogil
328        int size_nz() nogil
329        void fill(long value) nogil
330        void add(const MatrixRow[T] v) nogil
331        void add(const MatrixRow[T] v, int n) nogil
332        void sub(const MatrixRow[T] v) nogil
333        void sub(const MatrixRow[T] v, int n) nogil
334        void addmul_2exp(const MatrixRow[T]& v, const T& x, long expo, T& tmp) nogil
335        void addmul_2exp(const MatrixRow[T]& v, const T& x, long expo, int n, T& tmp) nogil
336        void addmul_si(const MatrixRow[T]& v, long x) nogil
337        void addmul_si(const MatrixRow[T]& v, long x, int n) nogil
338        void addmul_si_2exp(const MatrixRow[T]& v, long x, long expo, T& tmp) nogil
339        void addmul_si_2exp(const MatrixRow[T]& v, long x, long expo, int n, T& tmp) nogil
340
341        void dot_product(T &result, const MatrixRow[T] &v0) nogil
342        void dot_product(T &result, const MatrixRow[T] &v0, int n) nogil
343
344    void dot_product[T](T& result, const MatrixRow[T]& v1, const MatrixRow[T]& v2, int n) nogil
345    void dot_product[T](T& result, const MatrixRow[T]& v1, const MatrixRow[T]& v2) nogil
346
347    cdef cppclass Matrix[T]:
348        Matrix()
349        Matrix(int r, int c)
350
351        int get_rows()
352        int get_cols()
353
354        T& operator()(int i, int j)
355        MatrixRow[T] operator[](int i)
356
357        void clear()
358        int empty()
359        void resize(int rows, int cols) nogil
360        void set_rows(int rows) nogil
361        void set_cols(int cols) nogil
362        void swap(Matrix[T]& m) nogil
363
364        void swap_rows(int r1, int r2) nogil
365        void rotate_left(int first, int last) nogil
366        void rotate_right(int first, int last) nogil
367        void rotate(int first, int middle, int last) nogil
368        void rotate_gram_left(int first, int last, int nValidRows) nogil
369        void rotate_gram_right(int first, int last, int nValidRows) nogil
370        void transpose() nogil
371        long get_max_exp() nogil
372
373    cdef cppclass ZZ_mat[T]:
374
375        ZZ_mat()
376        ZZ_mat(int r, int c)
377
378        int get_rows() nogil
379        int get_cols() nogil
380        void set_rows(int rows) nogil
381        void set_cols(int cols) nogil
382
383        Z_NR[T]& operator()(int i, int j) nogil
384        MatrixRow[Z_NR[T]] operator[](int i) nogil
385
386        void gen_identity(int nrows) nogil
387        void gen_intrel(int bits) nogil
388        void gen_simdioph(int bits, int bits2) nogil
389        void gen_uniform(int bits) nogil
390        void gen_ntrulike(int bits) nogil
391        void gen_ntrulike_withq(int q) nogil
392        void gen_ntrulike2(int bits) nogil
393        void gen_ntrulike2_withq(int q) nogil
394        void gen_qary_withq(int k, int q) nogil
395        void gen_qary_prime(int k, int bits) nogil
396        void gen_trg(double alpha) nogil
397
398
399
400# Gram Schmidt Orthogonalization
401
402cdef extern from "fplll/gso.h" namespace "fplll":
403
404    cdef enum MatGSOInterfaceFlags:
405        GSO_DEFAULT
406        GSO_INT_GRAM
407        GSO_ROW_EXPO
408        GSO_OP_FORCE_LONG
409
410    cdef cppclass MatGSO[ZT, FT]:
411        MatGSO(Matrix[ZT] B, Matrix[ZT] U, Matrix[ZT] UinvT, int flags)
412
413        int d
414        Matrix[ZT]& b
415        vector[long] row_expo
416        void row_op_begin(int first, int last)
417        void row_op_end(int first, int last)
418        FT& get_gram(FT& f, int i, int j)
419
420        const Matrix[FT]& get_mu_matrix() nogil
421        const FT& get_mu_exp(int i, int j, long& expo) nogil
422        const FT& get_mu_exp(int i, int j) nogil
423        FT& get_mu(FT& f, int i, int j) nogil
424
425        const Matrix[FT]& get_r_matrix() nogil
426        const FT& get_r_exp(int i, int j, long& expo) nogil
427        const FT& get_r_exp(int i, int j) nogil
428        FT& get_r(FT& f, int i, int j) nogil
429
430        long get_max_mu_exp(int i, int nColumns) nogil
431
432        int update_gso_row(int i, int lastJ) nogil
433        int update_gso_row(int i) nogil
434        int update_gso() nogil
435
436        void discover_all_rows() nogil
437        void set_r(int i, int j, FT& f) nogil
438        void move_row(int oldR, int newR) nogil
439        void row_swap(int row1, int row2) nogil
440
441        void row_addmul(int i, int j, const FT& x) nogil
442        void row_addmul_we(int i, int j, const FT& x, long expoAdd) nogil
443
444        void lock_cols() nogil
445        void unlock_cols() nogil
446
447        void create_row() nogil
448        void create_rows(int nNewRows) nogil
449
450        void remove_last_row() nogil
451        void remove_last_rows(int nRemovedRows) nogil
452
453        void apply_transform(const Matrix[FT]& transform, int srcBase, int targetBase) nogil
454        void apply_transform(const Matrix[FT]& transform, int srcBase) nogil
455
456        void dump_mu_d(double* mu, int offset, int block_size) nogil
457        void dump_mu_d(vector[double] mu, int offset, int block_size) nogil
458
459        void dump_r_d(double* r, int offset, int block_size) nogil
460        void dump_r_d(vector[double] r, int offset, int block_size) nogil
461
462        double get_current_slope(int start_row, int stop_row) nogil
463        FT get_root_det(int start_row, int stop_row) nogil
464        FT get_log_det(int start_row, int stop_row) nogil
465        FT get_slide_potential(int start_row, int stop_row, int block_size) nogil
466
467        const int enable_int_gram
468        const int enable_row_expo
469        const int enable_transform
470
471        const int enable_inverse_transform
472        const int row_op_force_long
473
474cdef extern from "fplll/gso_gram.h" namespace "fplll":
475
476    cdef cppclass MatGSOGram[ZT, FT]:
477        MatGSOGram(Matrix[ZT] B, Matrix[ZT] U, Matrix[ZT] UinvT, int flags)
478
479        long get_max_exp_of_b() nogil
480        bool b_row_is_zero(int i) nogil
481        int get_cols_of_b() nogil
482        int get_rows_of_b() nogil
483        void negate_row_of_b(int i) nogil
484
485        void set_g(Matrix[ZT] arg_g)
486        void create_rows(int n_new_rows) nogil
487        void remove_last_rows(int n_removed_rows) nogil
488
489        void move_row(int old_r, int new_r) nogil
490
491        void row_addmul_we(int i, int j, const FT &x, long expo_add) nogil
492
493        void row_add(int i, int j) nogil
494        void row_sub(int i, int j) nogil
495
496        FT &get_gram(FT &f, int i, int j) nogil
497
498
499cdef extern from "fplll/gso_interface.h" namespace "fplll":
500
501    cdef cppclass MatGSOInterface[ZT, FT]:
502        MatGSOInterface(Matrix[ZT] B, Matrix[ZT] U, Matrix[ZT] UinvT, int flags)
503
504        int d
505
506        long get_max_exp_of_b() nogil
507        bool b_row_is_zero(int i) nogil
508
509        int get_cols_of_b() nogil
510        int get_rows_of_b() nogil
511
512        void negate_row_of_b(int i) nogil
513        vector[long] row_expo
514
515        inline void row_op_begin(int first, int last) nogil
516        void row_op_end(int first, int last) nogil
517        FT &get_gram(FT &f, int i, int j) nogil
518        ZT &get_int_gram(ZT &f, int i, int j) nogil
519        const Matrix[FT] &get_mu_matrix() nogil
520        const Matrix[FT] &get_r_matrix() nogil
521        const Matrix[ZT] &get_g_matrix() nogil
522        inline const FT &get_mu_exp(int i, int j, long &expo) nogil
523        inline const FT &get_mu_exp(int i, int j) nogil
524        inline FT &get_mu(FT &f, int i, int j) nogil
525        ZT get_max_gram() nogil
526        FT get_max_bstar() nogil
527        inline const FT &get_r_exp(int i, int j, long &expo) nogil
528        inline const FT &get_r_exp(int i, int j) nogil
529        inline FT &get_r(FT &f, int i, int j) nogil
530        long get_max_mu_exp(int i, int n_columns) nogil
531        bool update_gso_row(int i, int last_j) nogil
532
533        inline bool update_gso_row(int i) nogil
534        inline bool update_gso() nogil
535
536        inline void discover_all_rows() nogil
537        void set_r(int i, int j, FT &f) nogil
538
539        void move_row(int old_r, int new_r) nogil
540        void row_swap(int row1, int row2) nogil
541
542
543        inline void row_addmul(int i, int j, const FT &x) nogil
544        void row_addmul_we(int i, int j, const FT &x, long expo_add) nogil
545        void row_add(int i, int j) nogil
546        void row_sub(int i, int j) nogil
547        void lock_cols() nogil
548        void unlock_cols() nogil
549        inline void create_row() nogil
550        void create_rows(int n_new_rows) nogil
551        inline void remove_last_row() nogil
552        void remove_last_rows(int n_removed_rows) nogil
553
554        void apply_transform(const Matrix[FT] &transform, int src_base, int target_base) nogil
555        void apply_transform(const Matrix[FT] &transform, int src_base) nogil
556
557        void dump_mu_d(double* mu, int offset, int block_size) nogil
558        void dump_mu_d(vector[double] mu, int offset, int block_size) nogil
559
560        void dump_r_d(double* r, int offset, int block_size) nogil
561        void dump_r_d(vector[double] r, int offset, int block_size) nogil
562
563        double get_current_slope(int start_row, int stop_row) nogil
564        FT get_root_det(int start_row, int end_row) nogil
565        FT get_log_det(int start_row, int end_row) nogil
566        FT get_slide_potential(int start_row, int end_row, int block_size) nogil
567
568        const bool enable_int_gram
569        const bool enable_row_expo
570        const bool enable_transform
571        const bool enable_inverse_transform
572        const bool row_op_force_long
573
574
575
576# LLL
577
578cdef extern from "fplll/lll.h" namespace "fplll":
579
580    cdef cppclass LLLReduction[ZT,FT]:
581        LLLReduction(MatGSOInterface[ZT, FT]& m, double delta, double eta, int flags)
582
583        int lll() nogil
584        int lll(int kappa_min) nogil
585        int lll(int kappa_min, int kappa_start) nogil
586        int lll(int kappa_min, int kappa_start, int kappa_end) nogil
587        int lll(int kappa_min, int kappa_start, int kappa_end, int size_reduction_start) nogil
588        int size_reduction() nogil
589        int size_reduction(int kappa_min) nogil
590        int size_reduction(int kappa_min, int kappa_end) nogil
591        int size_reduction(int kappa_min, int kappa_end, int size_reduction_start) nogil
592
593        int status
594        int final_kappa
595        int last_early_red
596        int zeros
597        int n_swaps
598
599    int is_lll_reduced[ZT, FT](MatGSOInterface[ZT, FT]& m, double delta, double eta) nogil
600
601
602# LLL Wrapper
603
604cdef extern from "fplll/wrapper.h" namespace "fplll":
605
606    cdef cppclass Wrapper:
607        Wrapper(ZZ_mat[mpz_t]& b, ZZ_mat[mpz_t]& u, ZZ_mat[mpz_t]& uInv,
608                double delta, double eta, int flags)
609        int lll() nogil
610        int status
611
612
613
614# Evaluator
615
616cdef extern from "enumeration_callback_helper.h":
617    cdef cppclass PyCallbackEvaluatorWrapper:
618        PyCallbackEvaluatorWrapper()
619        PyCallbackEvaluatorWrapper(object)
620
621
622cdef extern from "fplll/enum/evaluator.h" namespace "fplll":
623
624    cdef enum EvaluatorStrategy:
625        EVALSTRATEGY_BEST_N_SOLUTIONS
626        EVALSTRATEGY_OPPORTUNISTIC_N_SOLUTIONS
627        EVALSTRATEGY_FIRST_N_SOLUTIONS
628
629
630    cdef cppclass Evaluator[FT]:
631        Evaluator()
632
633        void eval_sol(const vector[FT]& newSolCoord,
634                      const enumf& newPartialDist, enumf& maxDist, long normExp)
635
636
637        int max_sols
638        EvaluatorStrategy strategy
639        multimap[FT, vector[FT]] solutions
640        size_t sol_count
641        vector[pair[FT, vector[FT]]] sub_solutions
642
643        multimap[FP_NR[FT], vector[FP_NR[FT]]].reverse_iterator begin()
644        multimap[FP_NR[FT], vector[FP_NR[FT]]].reverse_iterator end()
645
646        int size()
647        bool empty()
648
649    cdef cppclass FastEvaluator[FT]:
650        FastEvaluator()
651        FastEvaluator(size_t nr_solutions, EvaluatorStrategy strategy, bool find_subsolutions)
652
653        void eval_sol(const vector[FT]& newSolCoord,
654                      const enumf& newPartialDist, enumf& maxDist, long normExp)
655
656        int max_sols
657        EvaluatorStrategy strategy
658        multimap[FT, vector[FT]] solutions
659        size_t sol_count
660        vector[pair[FT, vector[FT]]] sub_solutions
661
662        multimap[FP_NR[FT], vector[FP_NR[FT]]].reverse_iterator begin()
663        multimap[FP_NR[FT], vector[FP_NR[FT]]].reverse_iterator end()
664
665        int size()
666        bool empty()
667
668    cdef cppclass CallbackEvaluator[FT]:
669        CallbackEvaluator()
670        CallbackEvaluator(PyCallbackEvaluatorWrapper, void *ctx,
671                          size_t nr_solutions, EvaluatorStrategy strategy, bool find_subsolutions)
672
673        void eval_sol(const vector[FT]& newSolCoord,
674                      const enumf& newPartialDist, enumf& maxDist, long normExp)
675
676        int max_sols
677        EvaluatorStrategy strategy
678        multimap[FT, vector[FT]] solutions
679        size_t sol_count
680        vector[pair[FT, vector[FT]]] sub_solutions
681
682        multimap[FP_NR[FT], vector[FP_NR[FT]]].reverse_iterator begin()
683        multimap[FP_NR[FT], vector[FP_NR[FT]]].reverse_iterator end()
684
685        int size()
686        bool empty()
687
688    cdef cppclass FastErrorBoundedEvaluator:
689        FastErrorBoundedEvaluator()
690        FastErrorBoundedEvaluator(int d, Matrix[FP_NR[mpfr_t]] mu, Matrix[FP_NR[mpfr_t]] r, EvaluatorMode eval_mode, size_t nr_solutions, EvaluatorStrategy strategy, bool find_subsolutions)
691
692        void eval_sol(const vector[FP_NR[mpfr_t]]& newSolCoord,
693                      const enumf& newPartialDist, enumf& maxDist, long normExp)
694        int size()
695
696        int max_sols
697        EvaluatorStrategy strategy
698        multimap[FP_NR[mpfr_t], vector[FP_NR[mpfr_t]]] solutions
699        multimap[FP_NR[mpfr_t], vector[FP_NR[mpfr_t]]].reverse_iterator begin()
700        multimap[FP_NR[mpfr_t], vector[FP_NR[mpfr_t]]].reverse_iterator end()
701
702
703    cdef cppclass ErrorBoundedEvaluator:
704        ErrorBoundedEvaluator()
705        ErrorBoundedEvaluator(int d, Matrix[FP_NR[mpfr_t]] mu, Matrix[FP_NR[mpfr_t]] r, EvaluatorMode eval_mode, size_t nr_solutions, EvaluatorStrategy strategy, bool find_subsolutions)
706
707        void eval_sol(const vector[FP_NR[mpfr_t]]& newSolCoord,
708                      const enumf& newPartialDist, enumf& maxDist, long normExp)
709        int size()
710
711        int max_sols
712        EvaluatorStrategy strategy
713        multimap[FP_NR[mpfr_t], vector[FP_NR[mpfr_t]]] solutions
714        multimap[FP_NR[mpfr_t], vector[FP_NR[mpfr_t]]].reverse_iterator begin()
715        multimap[FP_NR[mpfr_t], vector[FP_NR[mpfr_t]]].reverse_iterator end()
716
717
718
719# Enumeration
720
721cdef extern from "fplll/enum/enumerate.h" namespace "fplll":
722    cdef cppclass Enumeration[ZT, FT]:
723        Enumeration(MatGSOInterface[ZT, FT]& gso, Evaluator[FT]& evaluator)
724        Enumeration(MatGSOInterface[ZT, FT]& gso, FastEvaluator[FT]& evaluator)
725        Enumeration(MatGSOInterface[ZT, FP_NR[mpfr_t]]& gso, ErrorBoundedEvaluator& evaluator)
726        Enumeration(MatGSOInterface[ZT, FP_NR[mpfr_t]]& gso, FastErrorBoundedEvaluator& evaluator)
727
728        void enumerate(int first, int last, FT& fMaxDist, long maxDistExpo,
729                       const vector[FT]& targetCoord,
730                       const vector[double]& subTree,
731                       const vector[double]& pruning)
732
733        void enumerate(int first, int last, FT& fMaxDist, long maxDistExpo,
734                       const vector[FT]& targetCoord,
735                       const vector[double]& subTree,
736                       const vector[double]& pruning,
737                       int dual)
738
739        void enumerate(int first, int last, FT& fMaxDist, long maxDistExpo,
740                       const vector[FT]& targetCoord,
741                       const vector[double]& subTree,
742                       const vector[double]& pruning,
743                       int dual,
744                       int subtree_reset)
745
746        unsigned long get_nodes(int level)
747
748cdef extern from "fplll/enum/enumerate_ext.h" namespace "fplll":
749
750    ctypedef void extenum_cb_set_config (double *mu, size_t mudim, bool mutranspose, double *rdiag,
751                                         double *pruning)
752
753    ctypedef double extenum_cb_process_sol(double dist, double *sol);
754
755    ctypedef void extenum_cb_process_subsol(double dist, double *subsol, int offset);
756
757    ctypedef unsigned long extenum_fc_enumerate(int dim, enumf maxdist,
758                                                function[extenum_cb_set_config] cbfunc,
759                                                function[extenum_cb_process_sol] cbsol,
760                                                function[extenum_cb_process_subsol] cbsubsol,
761                                                bool dual, bool findsubsols)
762
763    void set_external_enumerator(function[extenum_fc_enumerate] extenum)
764    function[extenum_fc_enumerate] get_external_enumerator()
765
766
767# SVP
768
769cdef extern from "fplll/svpcvp.h" namespace "fplll":
770    int shortest_vector(ZZ_mat[mpz_t]& b,
771                        vector[Z_NR[mpz_t]] &sol_coord,
772                        SVPMethod method, int flags) nogil
773
774    int shortest_vector_pruning(ZZ_mat[mpz_t]& b, vector[Z_NR[mpz_t]]& sol_coord,
775                                const vector[double]& pruning, int flags) nogil
776
777    int shortest_vector_pruning(ZZ_mat[mpz_t]& b, vector[Z_NR[mpz_t]]& sol_coord,
778                                vector[vector[Z_NR[mpz_t]]]& auxsol_coord,
779                                vector[double]& auxsol_dist, const int max_aux_sols,
780                                const vector[double]& pruning, int flags) nogil
781
782    int closest_vector(ZZ_mat[mpz_t] b, vector[Z_NR[mpz_t]] &intTarget,
783                       vector[Z_NR[mpz_t]]& sol_coord, CVPMethod method, int flags) nogil
784
785
786
787# BKZ
788
789cdef extern from "fplll/bkz_param.h" namespace "fplll":
790
791    cdef cppclass PruningParams:
792        double gh_factor
793        vector[double] coefficients
794        double expectation
795        PrunerMetric metric
796        vector[double] detailed_cost
797
798        PruningParams()
799
800        @staticmethod
801        PruningParams LinearPruningParams(int block_size, int level)
802
803    cdef cppclass Strategy:
804        size_t block_size
805        vector[PruningParams] pruning_parameters
806        vector[size_t] preprocessing_block_sizes
807
808        @staticmethod
809        Strategy EmptyStrategy()
810
811        PruningParams get_pruning(double radius, double gh)
812
813    cdef cppclass BKZParam:
814        BKZParam() nogil
815        BKZParam(int block_size) nogil
816        BKZParam(int block_size, vector[Strategy] strategies, double delta) nogil
817        BKZParam(int block_size, vector[Strategy] strategies, double delta, int flags, int max_loops, int max_time,
818                 double auto_abort_scale, int auto_abort_max_no_dec) nogil
819        BKZParam(int block_size, vector[Strategy] strategies, double delta, int flags, int max_loops, int max_time,
820                 double auto_abort_scale, int auto_abort_max_no_dec, double gh_factor) nogil
821        int block_size
822        double delta
823        int flags
824        int max_loops
825        double max_time
826
827        double auto_abort_scale
828        int auto_abort_max_no_dec
829
830        vector[Strategy] strategies
831
832        double gh_factor
833
834        double min_success_probability
835
836        int rerandomization_density
837
838        string dump_gso_filename
839
840    vector[Strategy] load_strategies_json(const string &filename) nogil
841    const string default_strategy_path() nogil
842    const string default_strategy() nogil
843    const string strategy_full_path(const string &strategy_path) nogil
844
845
846cdef extern from "fplll/bkz.h" namespace "fplll":
847
848    cdef cppclass BKZReduction[ZT, FT]:
849
850        BKZReduction(MatGSOInterface[ZT, FT] &m, LLLReduction[ZT, FT] &lll_obj, const BKZParam &param) nogil
851
852        int svp_preprocessing(int kappa, int block_size, const BKZParam &param) nogil
853        int svp_postprocessing(int kappa, int block_size, const vector[FT] &solution) nogil
854
855        int svp_reduction(int kappa, int block_size, const BKZParam &param, int dual) nogil except +
856
857        int tour(const int loop, int &kappa_max, const BKZParam &param, int min_row, int max_row) nogil except +
858        int sd_tour(const int loop, const BKZParam &param, int min_row, int max_row) nogil except +
859        int slide_tour(const int loop, const BKZParam &param, int min_row, int max_row) nogil except +
860
861        int hkz(int &kappaMax, const BKZParam &param, int min_row, int max_row) nogil except +
862
863        int bkz()
864
865        void rerandomize_block(int min_row, int max_row, int density) nogil except +
866
867        void dump_gso(const string filename, const string prefix, int append) nogil except +
868
869        int status
870
871        long nodes
872
873
874    cdef cppclass BKZAutoAbort[ZT, FT]:
875        BKZAutoAbort(MatGSOInterface[ZT, FT]& m, int num_rows) nogil
876        BKZAutoAbort(MatGSOInterface[ZT, FT]& m, int num_rows, int start_row) nogil
877
878        int test_abort() nogil
879        int test_abort(double scale) nogil
880        int test_abort(double scale, int max_no_dec) nogil
881
882    void adjust_radius_to_gh_bound[FT](FT& max_dist, long max_dist_expo,
883                                        int block_size, FT& root_det_mpfr, double gh_factor) nogil
884
885    FT get_root_det[FT](MatGSOInterface[Z_NR[mpz_t], FT]& m, int start, int end)
886    FT get_log_det[FT](MatGSOInterface[Z_NR[mpz_t], FT]& m, int start, int end)
887    FT get_sld_potential[FT](MatGSOInterface[Z_NR[mpz_t], FT]& m, int start, int end, int block_size)
888
889    double get_current_slope[FT](MatGSOInterface[Z_NR[mpz_t], FT]& m, int startRow, int stopRow) nogil
890
891
892# Utility
893
894cdef extern from "fplll/util.h" namespace "fplll":
895    void vector_matrix_product(vector[Z_NR[mpz_t]] &result,
896                               vector[Z_NR[mpz_t]] &x,
897                               const ZZ_mat[mpz_t] &m) nogil
898
899
900
901
902# Pruner
903
904cdef extern from "fplll/pruner/pruner.h" namespace "fplll":
905
906    cdef enum PrunerFlags:
907        PRUNER_CVP
908        PRUNER_START_FROM_INPUT
909        PRUNER_GRADIENT
910        PRUNER_NELDER_MEAD
911        PRUNER_VERBOSE
912        PRUNER_SINGLE
913        PRUNER_HALF
914
915    cdef enum PrunerMetric:
916        PRUNER_METRIC_PROBABILITY_OF_SHORTEST
917        PRUNER_METRIC_EXPECTED_SOLUTIONS
918
919    cdef cppclass Pruner[FT]:
920        Pruner(const int n)
921
922        Pruner(const FT enumeration_radius, const FT preproc_cost, const vector[double] &gso_r)
923
924        Pruner(const FT enumeration_radius, const FT preproc_cost, const vector[double] &gso_r,
925               const FT target, const PrunerMetric metric, int flags)
926
927        Pruner(const FT enumeration_radius, const FT preproc_cost, const vector[vector[double]] &gso_r)
928
929        Pruner(const FT enumeration_radius, const FT preproc_cost, const vector[vector[double]] &gso_r,
930               const FT target, const PrunerMetric metric, int flags)
931
932        void optimize_coefficients(vector[double] &pr)
933        void optimize_coefficients_cost_vary_prob(vector[double] &pr)
934        void optimize_coefficients_cost_fixed_prob(vector[double] &pr)
935        void optimize_coefficients_evec(vector[double] &pr)
936        void optimize_coefficients_full(vector[double] &pr)
937
938        double single_enum_cost(const vector[double] &pr, vector[double] *detailed_cost)
939        double single_enum_cost(const vector[double] &pr)
940
941        double repeated_enum_cost(const vector[double] &pr)
942
943        double measure_metric(const vector[double] &pr)
944
945        FT gaussian_heuristic()
946
947    void prune[FT](PruningParams &pruning, const double enumeration_radius,
948                   const double preproc_cost, const vector[double] &gso_r)
949
950    void prune[FT](PruningParams &pruning, const double enumeration_radius,
951                   const double preproc_cost, const vector[double] &gso_r,
952                   const double target, const PrunerMetric metric, const int flags)
953
954    void prune[FT](PruningParams &pruning, const double enumeration_radius,
955                   const double preproc_cost, const vector[vector[double]] &gso_r)
956
957    void prune[FT](PruningParams &pruning, const double enumeration_radius,
958                   const double preproc_cost, const vector[vector[double]] &gso_r,
959                   const double target, const PrunerMetric metric, const int flags)
960
961    FT svp_probability[FT](const PruningParams &pruning)
962    FT svp_probability[FT](const vector[double] &pr)
963
964
965# Threads
966
967cdef extern from "fplll/threadpool.h" namespace "fplll":
968    int get_threads()
969    int set_threads(int th)
970
971
972
973# Highlevel Functions
974
975cdef extern from "fplll/fplll.h" namespace "fplll":
976
977    int lll_reduction(ZZ_mat[mpz_t] b, double delta, double eta,
978                      LLLMethod method, FloatType float_type,
979                      int precision, int flags) nogil
980    int lll_reduction(ZZ_mat[mpz_t] b, ZZ_mat[mpz_t] u,
981                      double delta, double eta,
982                      LLLMethod method, FloatType float_type,
983                      int precision, int flags) nogil
984
985    int bkz_reduction(ZZ_mat[mpz_t] *b, ZZ_mat[mpz_t] *u,
986                      BKZParam &param, FloatType float_type, int precision) nogil
987    int bkz_reduction(ZZ_mat[mpz_t] *b, int block_size, int flags, FloatType float_type, int precision) nogil
988
989    int hkz_reduction(ZZ_mat[mpz_t] b) nogil
990
991    const char* get_red_status_str(int status) nogil
992
993
994