include/flint/fmpz_lll.h

0001 /*
0002     Copyright (C) 2009, 2010 William Hart
0003     Copyright (C) 2009, 2010 Andy Novocin
0004     Copyright (C) 2014 Abhinav Baid
0005
0006     This file is part of FLINT.
0007
0008     FLINT is free software: you can redistribute it and/or modify it under
0009     the terms of the GNU Lesser General Public License (LGPL) as published
0010     by the Free Software Foundation; either version 3 of the License, or
0011     (at your option) any later version.  See <https://www.gnu.org/licenses/>.
0012 */
0013
0014 #ifndef FMPZ_LLL_H
0015 #define FMPZ_LLL_H
0016
0017 #ifdef FMPZ_LLL_INLINES_C
0018 #define FMPZ_LLL_INLINE
0019 #else
0020 #define FMPZ_LLL_INLINE static inline
0021 #endif
0022
0023 #include "fmpz_types.h"
0024 #include "d_mat.h"
0025 #include "gr_types.h"
0026
0027 #ifdef __cplusplus
0028 extern "C" {
0029 #endif
0030
0031 #if FLINT_BITS == 32
0032 #define CPU_SIZE_1 31
0033 #define FMPZ_LLL_MAX_LONG WORD(2147483647)
0034 #else
0035 #define CPU_SIZE_1 53
0036 #define FMPZ_LLL_MAX_LONG WORD(9007199254740991)
0037 #endif
0038
0039 #define SIZE_RED_FAILURE_THRESH 5
0040
0041 typedef enum
0042 {
0043     GRAM,
0044     Z_BASIS
0045 } rep_type;
0046
0047 typedef enum
0048 {
0049     APPROX,
0050     EXACT
0051 } gram_type;
0052
0053 typedef struct
0054 {
0055     double delta;
0056     double eta;
0057     rep_type rt;
0058     gram_type gt;
0059 } fmpz_lll_struct;
0060
0061 typedef fmpz_lll_struct fmpz_lll_t[1];
0062
0063 typedef union
0064 {
0065     d_mat_t appSP;
0066     gr_mat_t appSP2;
0067     fmpz_mat_t exactSP;
0068 } fmpz_gram_union;
0069
0070 typedef fmpz_gram_union fmpz_gram_t[1];
0071
0072 /* Parameter manipulation  ***************************************************/
0073
0074 void fmpz_lll_context_init_default(fmpz_lll_t fl);
0075
0076 void fmpz_lll_context_init(fmpz_lll_t fl, double delta, double eta,
0077                            rep_type rt, gram_type gt);
0078
0079 /* Random parameter generation  **********************************************/
0080
0081 void fmpz_lll_randtest(fmpz_lll_t fl, flint_rand_t state);
0082
0083 /* The various Babai's  ******************************************************/
0084
0085 double fmpz_lll_heuristic_dot(const double * vec1, const double * vec2, slong len2,
0086        const fmpz_mat_t B, slong k, slong j, slong exp_adj);
0087
0088 int fmpz_lll_check_babai(int kappa, fmpz_mat_t B, fmpz_mat_t U, d_mat_t mu, d_mat_t r, double *s,
0089        d_mat_t appB, int *expo, fmpz_gram_t A,
0090        int a, int zeros, int kappamax, int n, const fmpz_lll_t fl);
0091
0092 int fmpz_lll_check_babai_heuristic_d(int kappa, fmpz_mat_t B, fmpz_mat_t U, d_mat_t mu, d_mat_t r, double *s,
0093        d_mat_t appB, int *expo, fmpz_gram_t A,
0094        int a, int zeros, int kappamax, int n, const fmpz_lll_t fl);
0095
0096 int fmpz_lll_shift(const fmpz_mat_t B);
0097
0098 int fmpz_lll_d(fmpz_mat_t B, fmpz_mat_t U, const fmpz_lll_t fl);
0099
0100 int fmpz_lll_d_heuristic(fmpz_mat_t B, fmpz_mat_t U, const fmpz_lll_t fl);
0101
0102 int fmpz_lll_check_babai_heuristic(int kappa, fmpz_mat_t B, fmpz_mat_t U,
0103                                gr_mat_t mu, gr_mat_t r, gr_ptr s,
0104                                gr_mat_t appB, fmpz_gram_t A, int a, int zeros,
0105                                int kappamax, int n, gr_ptr tmp, gr_ptr rtmp,
0106                                gr_ctx_t ctx, const fmpz_lll_t fl);
0107
0108 int fmpz_lll_mpf2(fmpz_mat_t B, fmpz_mat_t U, flint_bitcnt_t prec, const fmpz_lll_t fl);
0109
0110 int fmpz_lll_mpf(fmpz_mat_t B, fmpz_mat_t U, const fmpz_lll_t fl);
0111
0112 int fmpz_lll_wrapper(fmpz_mat_t B, fmpz_mat_t U, const fmpz_lll_t fl);
0113
0114 int fmpz_lll_advance_check_babai(int cur_kappa, int kappa, fmpz_mat_t B, fmpz_mat_t U, d_mat_t mu, d_mat_t r, double *s,
0115        d_mat_t appB, int *expo, fmpz_gram_t A,
0116        int a, int zeros, int kappamax, int n, const fmpz_lll_t fl);
0117
0118 int fmpz_lll_advance_check_babai_heuristic_d(int cur_kappa, int kappa, fmpz_mat_t B, fmpz_mat_t U, d_mat_t mu, d_mat_t r, double *s,
0119        d_mat_t appB, int *expo, fmpz_gram_t A,
0120        int a, int zeros, int kappamax, int n, const fmpz_lll_t fl);
0121
0122 /* LLL with removals  ********************************************************/
0123
0124 int fmpz_lll_d_with_removal(fmpz_mat_t B, fmpz_mat_t U, const fmpz_t gs_B, const fmpz_lll_t fl);
0125
0126 int fmpz_lll_d_heuristic_with_removal(fmpz_mat_t B, fmpz_mat_t U, const fmpz_t gs_B, const fmpz_lll_t fl);
0127
0128 int fmpz_lll_mpf2_with_removal(fmpz_mat_t B, fmpz_mat_t U, flint_bitcnt_t prec, const fmpz_t gs_B, const fmpz_lll_t fl);
0129
0130 int fmpz_lll_mpf_with_removal(fmpz_mat_t B, fmpz_mat_t U, const fmpz_t gs_B, const fmpz_lll_t fl);
0131
0132 int fmpz_lll_wrapper_with_removal(fmpz_mat_t B, fmpz_mat_t U, const fmpz_t gs_B, const fmpz_lll_t fl);
0133
0134 int fmpz_lll_d_with_removal_knapsack(fmpz_mat_t B, fmpz_mat_t U, const fmpz_t gs_B, const fmpz_lll_t fl);
0135
0136 int fmpz_lll_wrapper_with_removal_knapsack(fmpz_mat_t B, fmpz_mat_t U, const fmpz_t gs_B, const fmpz_lll_t fl);
0137
0138 /* ULLL  *********************************************************************/
0139
0140 int fmpz_lll_with_removal_ulll(fmpz_mat_t FM, fmpz_mat_t UM, slong new_size, const fmpz_t gs_B, const fmpz_lll_t fl);
0141
0142 /* LLL-reducedness ***********************************************************/
0143
0144 int fmpz_lll_is_reduced_d(const fmpz_mat_t B, const fmpz_lll_t fl);
0145
0146 int fmpz_lll_is_reduced_mpfr(const fmpz_mat_t B, const fmpz_lll_t fl, flint_bitcnt_t prec);
0147
0148 int fmpz_lll_is_reduced(const fmpz_mat_t B, const fmpz_lll_t fl, flint_bitcnt_t prec);
0149
0150 int fmpz_lll_is_reduced_d_with_removal(const fmpz_mat_t B, const fmpz_lll_t fl, const fmpz_t gs_B, int newd);
0151
0152 int fmpz_lll_is_reduced_mpfr_with_removal(const fmpz_mat_t B, const fmpz_lll_t fl, const fmpz_t gs_B, int newd,flint_bitcnt_t prec);
0153
0154 int fmpz_lll_is_reduced_with_removal(const fmpz_mat_t B, const fmpz_lll_t fl, const fmpz_t gs_B, int newd, flint_bitcnt_t prec);
0155
0156 /* Default functions *********************************************************/
0157
0158 void fmpz_lll(fmpz_mat_t B, fmpz_mat_t U, const fmpz_lll_t fl);
0159
0160 int fmpz_lll_with_removal(fmpz_mat_t B, fmpz_mat_t U, const fmpz_t gs_B, const fmpz_lll_t fl);
0161
0162 /* Modified ULLL  ************************************************************/
0163
0164 void fmpz_lll_storjohann_ulll(fmpz_mat_t FM, slong new_size, const fmpz_lll_t fl);
0165
0166 #ifdef __cplusplus
0167 }
0168 #endif
0169
0170 #endif