include/flint/fmpz_poly_factor.h

0001 /*
0002     Copyright (C) 2006, 2007, 2008, 2009, 2010, 2016 William Hart
0003     Copyright (C) 2009, 2011 Andy Novocin
0004     Copyright (C) 2010 Sebastian Pancratz
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_POLY_FACTOR_H
0015 #define FMPZ_POLY_FACTOR_H
0016
0017 #ifdef FMPZ_POLY_FACTOR_INLINES_C
0018 #define FMPZ_POLY_FACTOR_INLINE
0019 #else
0020 #define FMPZ_POLY_FACTOR_INLINE static inline
0021 #endif
0022
0023 #include "nmod_types.h"
0024 #include "fmpz_types.h"
0025
0026 #ifdef __cplusplus
0027 extern "C" {
0028 #endif
0029
0030 void fmpz_poly_factor_init(fmpz_poly_factor_t fac);
0031
0032 void fmpz_poly_factor_init2(fmpz_poly_factor_t fac, slong alloc);
0033
0034 void fmpz_poly_factor_realloc(fmpz_poly_factor_t fac, slong alloc);
0035
0036 void fmpz_poly_factor_fit_length(fmpz_poly_factor_t fac, slong len);
0037
0038 void fmpz_poly_factor_clear(fmpz_poly_factor_t fac);
0039
0040 void fmpz_poly_factor_set(fmpz_poly_factor_t res,
0041                                                  const fmpz_poly_factor_t fac);
0042
0043 void fmpz_poly_factor_insert(fmpz_poly_factor_t fac,
0044                              const fmpz_poly_t p, slong exp);
0045
0046 void fmpz_poly_factor_concat(fmpz_poly_factor_t res,
0047                              const fmpz_poly_factor_t fac);
0048
0049 void fmpz_poly_factor_print(const fmpz_poly_factor_t fac);
0050
0051 void fmpz_poly_factor_zassenhaus_recombination(
0052             fmpz_poly_factor_t final_fac, const fmpz_poly_factor_t lifted_fac,
0053                                const fmpz_poly_t F, const fmpz_t P, slong exp);
0054
0055 void fmpz_poly_factor_squarefree(fmpz_poly_factor_t fac,
0056                                                           const fmpz_poly_t F);
0057
0058 void fmpz_poly_factor_mignotte(fmpz_t B, const fmpz_poly_t f);
0059
0060 void _fmpz_poly_factor_zassenhaus(fmpz_poly_factor_t final_fac,
0061               slong exp, const fmpz_poly_t f, slong cutoff, int use_van_hoeij);
0062
0063 void fmpz_poly_factor_zassenhaus(fmpz_poly_factor_t fac,
0064                                                           const fmpz_poly_t G);
0065
0066 void _fmpz_poly_factor_quadratic(fmpz_poly_factor_t fac,
0067                                                const fmpz_poly_t f, slong exp);
0068
0069 void _fmpz_poly_factor_cubic(fmpz_poly_factor_t fac,
0070                                                const fmpz_poly_t f, slong exp);
0071
0072 slong _fmpz_poly_factor_CLD_mat(fmpz_mat_t res, const fmpz_poly_t f,
0073                              fmpz_poly_factor_t lifted_fac, fmpz_t P, ulong k);
0074
0075 int fmpz_poly_factor_van_hoeij_check_if_solved(fmpz_mat_t M,
0076           fmpz_poly_factor_t final_fac, fmpz_poly_factor_t lifted_fac,
0077                           const fmpz_poly_t f, fmpz_t P, slong exp, fmpz_t lc);
0078
0079 void fmpz_poly_factor_van_hoeij(fmpz_poly_factor_t final_fac,
0080         const nmod_poly_factor_t fac, const fmpz_poly_t f, slong exp, ulong p);
0081
0082 void fmpz_poly_factor(fmpz_poly_factor_t fac, const fmpz_poly_t G);
0083
0084 /* Inlines *******************************************************************/
0085
0086 void fmpz_poly_factor_get_fmpz_poly(fmpz_poly_t z, const fmpz_poly_factor_t F, slong i);
0087 void fmpz_poly_factor_get_fmpz(fmpz_t z, const fmpz_poly_factor_t F);
0088
0089 /* zassenhaus ****************************************************************/
0090
0091 void zassenhaus_subset_first(slong * s, slong r, slong m);
0092
0093 int zassenhaus_subset_next(slong * s, slong r);
0094
0095 slong zassenhaus_subset_next_disjoint(slong * s, slong r);
0096
0097 typedef struct {
0098     slong deg;
0099     unsigned char * pos_degs;   /* possible degrees: entries are 0 or 1*/
0100     slong new_length;
0101     slong new_total;
0102     slong * new_degs;
0103     slong alloc;
0104 } zassenhaus_prune_struct;
0105
0106 typedef zassenhaus_prune_struct zassenhaus_prune_t[1];
0107
0108 FMPZ_POLY_FACTOR_INLINE
0109 void zassenhaus_prune_init(zassenhaus_prune_t Z)
0110 {
0111     Z->deg = 0;
0112     Z->pos_degs = NULL;
0113     Z->new_length = 0;
0114     Z->new_total = 0;
0115     Z->new_degs = NULL;
0116     Z->alloc = 0;
0117 }
0118
0119 void zassenhaus_prune_clear(zassenhaus_prune_t Z);
0120
0121 void zassenhaus_prune_set_degree(zassenhaus_prune_t Z, slong d);
0122
0123 FMPZ_POLY_FACTOR_INLINE
0124 void zassenhaus_prune_start_add_factors(zassenhaus_prune_t Z)
0125 {
0126     Z->new_length = 0;
0127     Z->new_total = 0;
0128 }
0129
0130 void zassenhaus_prune_add_factor(zassenhaus_prune_t Z,
0131                                                          slong deg, slong exp);
0132
0133 void zassenhaus_prune_end_add_factors(zassenhaus_prune_t Z);
0134
0135 int zassenhaus_prune_must_be_irreducible(const zassenhaus_prune_t Z);
0136
0137 FMPZ_POLY_FACTOR_INLINE
0138 int zassenhaus_prune_degree_is_possible(const zassenhaus_prune_t Z, slong d)
0139 {
0140     if (d <= 0)
0141         return d == 0;
0142
0143     if (d >= Z->deg)
0144         return d == Z->deg;
0145
0146     return Z->pos_degs[d];
0147 }
0148
0149 void fmpz_poly_factor_zassenhaus_recombination_with_prune(
0150             fmpz_poly_factor_t final_fac, const fmpz_poly_factor_t lifted_fac,
0151                                 const fmpz_poly_t F, const fmpz_t P, slong exp,
0152                                                    const zassenhaus_prune_t Z);
0153
0154 #ifdef __cplusplus
0155 }
0156 #endif
0157
0158 #endif