include/flint/fmpz_mod_poly_factor.h

0001 /*
0002     Copyright (C) 2011 Sebastian Pancratz
0003     Copyright (C) 2012 Lina Kulakova
0004
0005     This file is part of FLINT.
0006
0007     FLINT is free software: you can redistribute it and/or modify it under
0008     the terms of the GNU Lesser General Public License (LGPL) as published
0009     by the Free Software Foundation; either version 3 of the License, or
0010     (at your option) any later version.  See <https://www.gnu.org/licenses/>.
0011 */
0012
0013 #ifndef FMPZ_MOD_POLY_FACTOR_H
0014 #define FMPZ_MOD_POLY_FACTOR_H
0015
0016 #ifdef FMPZ_MOD_POLY_FACTOR_INLINES_C
0017 #define FMPZ_MOD_POLY_FACTOR_INLINE
0018 #else
0019 #define FMPZ_MOD_POLY_FACTOR_INLINE static inline
0020 #endif
0021
0022 #include "fmpz_mod_types.h"
0023
0024 #ifdef __cplusplus
0025 extern "C" {
0026 #endif
0027
0028 /* Factoring  ****************************************************************/
0029
0030 void fmpz_mod_poly_factor_init(fmpz_mod_poly_factor_t fac,
0031                                                      const fmpz_mod_ctx_t FLINT_UNUSED(ctx));
0032
0033 typedef struct
0034 {
0035     fmpz_mod_poly_struct * baby;
0036     fmpz_mod_poly_struct * res;
0037     fmpz_mod_poly_struct * H;
0038     fmpz_mod_poly_struct * v;
0039     fmpz_mod_poly_struct * vinv;
0040     const fmpz_mod_ctx_struct * ctx;
0041     fmpz * tmp;
0042     slong m;
0043 }
0044 fmpz_mod_poly_interval_poly_arg_t;
0045
0046 void fmpz_mod_poly_factor_clear(fmpz_mod_poly_factor_t fac,
0047                                                      const fmpz_mod_ctx_t ctx);
0048
0049 void fmpz_mod_poly_factor_realloc(fmpz_mod_poly_factor_t fac,
0050                                         slong alloc, const fmpz_mod_ctx_t ctx);
0051
0052 void fmpz_mod_poly_factor_fit_length(fmpz_mod_poly_factor_t fac,
0053                                           slong len, const fmpz_mod_ctx_t ctx);
0054
0055 void fmpz_mod_poly_factor_set(fmpz_mod_poly_factor_t res,
0056                    const fmpz_mod_poly_factor_t fac, const fmpz_mod_ctx_t ctx);
0057
0058 FMPZ_MOD_POLY_FACTOR_INLINE
0059 void fmpz_mod_poly_factor_swap(fmpz_mod_poly_factor_t a,
0060                             fmpz_mod_poly_factor_t b, const fmpz_mod_ctx_t FLINT_UNUSED(ctx))
0061 {
0062     fmpz_mod_poly_factor_struct t = *a;
0063     *a = *b;
0064     *b = t;
0065 }
0066
0067 void fmpz_mod_poly_factor_get_poly(fmpz_mod_poly_t a, const fmpz_mod_poly_factor_t b, slong i, const fmpz_mod_ctx_t ctx);
0068
0069 void fmpz_mod_poly_factor_insert(fmpz_mod_poly_factor_t fac,
0070               const fmpz_mod_poly_t poly, slong exp, const fmpz_mod_ctx_t ctx);
0071
0072 void fmpz_mod_poly_factor_print(const fmpz_mod_poly_factor_t fac,
0073                                                      const fmpz_mod_ctx_t ctx);
0074
0075 void fmpz_mod_poly_factor_print_pretty(const fmpz_mod_poly_factor_t fac,
0076                                     const char *var, const fmpz_mod_ctx_t ctx);
0077
0078 void fmpz_mod_poly_factor_concat(fmpz_mod_poly_factor_t res,
0079                    const fmpz_mod_poly_factor_t fac, const fmpz_mod_ctx_t ctx);
0080
0081 void fmpz_mod_poly_factor_pow(fmpz_mod_poly_factor_t fac, slong exp,
0082                                                      const fmpz_mod_ctx_t FLINT_UNUSED(ctx));
0083
0084 int fmpz_mod_poly_is_irreducible(const fmpz_mod_poly_t f,
0085                                                      const fmpz_mod_ctx_t ctx);
0086
0087 int fmpz_mod_poly_is_irreducible_ddf(const fmpz_mod_poly_t f,
0088                                                      const fmpz_mod_ctx_t ctx);
0089
0090 int fmpz_mod_poly_is_irreducible_rabin(const fmpz_mod_poly_t f,
0091                                                      const fmpz_mod_ctx_t ctx);
0092
0093 int fmpz_mod_poly_is_irreducible_rabin_f(fmpz_t fac,
0094                             const fmpz_mod_poly_t f, const fmpz_mod_ctx_t ctx);
0095
0096 int _fmpz_mod_poly_is_squarefree(const fmpz * f, slong len, const fmpz_mod_ctx_t ctx);
0097
0098 int _fmpz_mod_poly_is_squarefree_f(fmpz_t fac,
0099                                     const fmpz * f, slong len, const fmpz_mod_ctx_t ctx);
0100
0101 int fmpz_mod_poly_is_squarefree(const fmpz_mod_poly_t f,
0102                                                      const fmpz_mod_ctx_t ctx);
0103
0104 int fmpz_mod_poly_is_squarefree_f(fmpz_t fac,
0105                             const fmpz_mod_poly_t f, const fmpz_mod_ctx_t ctx);
0106
0107 int fmpz_mod_poly_factor_equal_deg_prob(fmpz_mod_poly_t factor,
0108                        flint_rand_t state, const fmpz_mod_poly_t pol, slong d,
0109                                                      const fmpz_mod_ctx_t ctx);
0110
0111 void fmpz_mod_poly_factor_equal_deg_with_frob(
0112              fmpz_mod_poly_factor_t factors, const fmpz_mod_poly_t f, slong d,
0113                          const fmpz_mod_poly_t frob, const fmpz_mod_ctx_t ctx);
0114
0115 void fmpz_mod_poly_factor_equal_deg(fmpz_mod_poly_factor_t factors,
0116                  const fmpz_mod_poly_t pol, slong d, const fmpz_mod_ctx_t ctx);
0117
0118 void fmpz_mod_poly_factor_distinct_deg_with_frob(
0119                     fmpz_mod_poly_factor_t res,  const fmpz_mod_poly_t poly,
0120                     const fmpz_mod_poly_t polyinv, const fmpz_mod_poly_t frob,
0121                                                      const fmpz_mod_ctx_t ctx);
0122
0123 void fmpz_mod_poly_factor_distinct_deg(fmpz_mod_poly_factor_t res,
0124                               const fmpz_mod_poly_t poly, slong * const *degs,
0125                                                      const fmpz_mod_ctx_t ctx);
0126
0127 void fmpz_mod_poly_factor_distinct_deg_threaded_with_frob(
0128                     fmpz_mod_poly_factor_t res, const fmpz_mod_poly_t poly,
0129                     const fmpz_mod_poly_t polyinv, const fmpz_mod_poly_t frob,
0130                                                      const fmpz_mod_ctx_t ctx);
0131
0132 void fmpz_mod_poly_factor_distinct_deg_threaded(
0133                     fmpz_mod_poly_factor_t res, const fmpz_mod_poly_t poly,
0134                                slong * const * degs, const fmpz_mod_ctx_t ctx);
0135
0136 void fmpz_mod_poly_factor_squarefree(fmpz_mod_poly_factor_t res,
0137                             const fmpz_mod_poly_t f, const fmpz_mod_ctx_t ctx);
0138
0139 void fmpz_mod_poly_factor(fmpz_mod_poly_factor_t res,
0140                             const fmpz_mod_poly_t f, const fmpz_mod_ctx_t ctx);
0141
0142 void fmpz_mod_poly_factor_cantor_zassenhaus(fmpz_mod_poly_factor_t res,
0143                             const fmpz_mod_poly_t f, const fmpz_mod_ctx_t ctx);
0144
0145 void fmpz_mod_poly_factor_kaltofen_shoup(fmpz_mod_poly_factor_t res,
0146                          const fmpz_mod_poly_t poly, const fmpz_mod_ctx_t ctx);
0147
0148 void fmpz_mod_poly_factor_berlekamp(fmpz_mod_poly_factor_t factors,
0149                             const fmpz_mod_poly_t f, const fmpz_mod_ctx_t ctx);
0150
0151 void _fmpz_mod_poly_interval_poly_worker(void * arg_ptr);
0152
0153 /* Roots *********************************************************************/
0154
0155 void fmpz_mod_poly_roots(fmpz_mod_poly_factor_t r,
0156                             const fmpz_mod_poly_t f, int with_multiplicity,
0157                                                      const fmpz_mod_ctx_t ctx);
0158
0159 int fmpz_mod_poly_roots_factored(fmpz_mod_poly_factor_t r,
0160         const fmpz_mod_poly_t f, int with_multiplicity, const fmpz_factor_t n,
0161                                                      const fmpz_mod_ctx_t ctx);
0162
0163 int fmpz_mod_poly_roots_factored_with_length_limit(fmpz_mod_poly_factor_t x0,
0164                            const fmpz_mod_poly_t f, int with_mult,
0165                             slong length_limit,
0166                              const fmpz_factor_t fac, const fmpz_mod_ctx_t ctx);
0167
0168 /* Inlines *******************************************************************/
0169
0170 void fmpz_mod_poly_factor_get_fmpz_mod_poly(fmpz_mod_poly_t z,
0171                 fmpz_mod_poly_factor_t fac, slong i, const fmpz_mod_ctx_t ctx);
0172
0173 #ifdef __cplusplus
0174 }
0175 #endif
0176
0177 #endif