include/flint/nmod_poly_factor.h

0001 /*
0002     Copyright (C) 2007, David Howden
0003     Copyright (C) 2010, 2011 William Hart
0004     Copyright (C) 2011 Sebastian Pancratz
0005     Copyright (C) 2011 Fredrik Johansson
0006     Copyright (C) 2015 Tommy Hofmann
0007
0008     This file is part of FLINT.
0009
0010     FLINT is free software: you can redistribute it and/or modify it under
0011     the terms of the GNU Lesser General Public License (LGPL) as published
0012     by the Free Software Foundation; either version 3 of the License, or
0013     (at your option) any later version.  See <https://www.gnu.org/licenses/>.
0014 */
0015
0016 #ifndef NMOD_POLY_FACTOR_H
0017 #define NMOD_POLY_FACTOR_H
0018
0019 #ifdef NMOD_POLY_FACTOR_INLINES_C
0020 #define NMOD_POLY_FACTOR_INLINE
0021 #else
0022 #define NMOD_POLY_FACTOR_INLINE static inline
0023 #endif
0024
0025 #include "limb_types.h"
0026 #include "nmod_types.h"
0027
0028 #ifdef __cplusplus
0029 extern "C" {
0030 #endif
0031
0032 typedef struct
0033 {
0034     nmod_poly_struct * baby;
0035     nmod_poly_struct * res;
0036     nmod_poly_struct * H;
0037     nmod_poly_struct * v;
0038     nmod_poly_struct * vinv;
0039     nn_ptr tmp;
0040     slong m;
0041 }
0042 nmod_poly_interval_poly_arg_t;
0043
0044 /* Factoring  ****************************************************************/
0045
0046 void nmod_poly_factor_init(nmod_poly_factor_t fac);
0047
0048 void nmod_poly_factor_clear(nmod_poly_factor_t fac);
0049
0050 void nmod_poly_factor_realloc(nmod_poly_factor_t fac, slong alloc);
0051
0052 void nmod_poly_factor_fit_length(nmod_poly_factor_t fac, slong len);
0053
0054 void nmod_poly_factor_set(nmod_poly_factor_t res, const nmod_poly_factor_t fac);
0055
0056 NMOD_POLY_FACTOR_INLINE
0057 void nmod_poly_factor_swap(nmod_poly_factor_t a, nmod_poly_factor_t b)
0058 {
0059     nmod_poly_factor_struct t = *a;
0060     *a = *b;
0061     *b = t;
0062 }
0063
0064 void nmod_poly_factor_get_poly(nmod_poly_t a, const nmod_poly_factor_t b, slong i);
0065
0066 void nmod_poly_factor_insert(nmod_poly_factor_t fac,
0067                              const nmod_poly_t poly, slong exp);
0068
0069 void nmod_poly_factor_print(const nmod_poly_factor_t fac);
0070
0071 void nmod_poly_factor_print_pretty(const nmod_poly_factor_t fac,
0072                                                               const char *var);
0073
0074 void nmod_poly_factor_concat(nmod_poly_factor_t res,
0075                         const nmod_poly_factor_t fac);
0076
0077 void nmod_poly_factor_pow(nmod_poly_factor_t fac, slong exp);
0078
0079 void nmod_poly_factor_equal_deg(nmod_poly_factor_t factors,
0080                                 const nmod_poly_t pol, slong d);
0081
0082 int nmod_poly_factor_equal_deg_prob(nmod_poly_t factor,
0083     flint_rand_t state, const nmod_poly_t pol, slong d);
0084
0085 void nmod_poly_factor_distinct_deg(nmod_poly_factor_t res,
0086                                    const nmod_poly_t poly, slong * const *degs);
0087
0088 void nmod_poly_factor_distinct_deg_threaded(nmod_poly_factor_t res,
0089                                   const nmod_poly_t poly, slong * const *degs);
0090
0091 int nmod_poly_is_irreducible(const nmod_poly_t f);
0092
0093 int nmod_poly_is_irreducible_rabin(const nmod_poly_t f);
0094
0095 int nmod_poly_is_irreducible_ddf(const nmod_poly_t f);
0096
0097 int _nmod_poly_is_squarefree(nn_srcptr f, slong len, nmod_t mod);
0098
0099 int nmod_poly_is_squarefree(const nmod_poly_t f);
0100
0101 void nmod_poly_factor_cantor_zassenhaus(nmod_poly_factor_t res,
0102     const nmod_poly_t f);
0103
0104 void nmod_poly_factor_berlekamp(nmod_poly_factor_t factors,
0105     const nmod_poly_t f);
0106
0107 void nmod_poly_factor_kaltofen_shoup(nmod_poly_factor_t res,
0108                                      const nmod_poly_t poly);
0109
0110 void nmod_poly_factor_squarefree(nmod_poly_factor_t res, const nmod_poly_t f);
0111
0112 ulong nmod_poly_factor_with_berlekamp(nmod_poly_factor_t result,
0113     const nmod_poly_t input);
0114
0115 ulong nmod_poly_factor_with_cantor_zassenhaus(nmod_poly_factor_t result,
0116     const nmod_poly_t input);
0117
0118 ulong nmod_poly_factor_with_kaltofen_shoup(nmod_poly_factor_t result,
0119     const nmod_poly_t input);
0120
0121 ulong nmod_poly_factor(nmod_poly_factor_t result,
0122     const nmod_poly_t input);
0123
0124 void _nmod_poly_interval_poly_worker(void* arg_ptr);
0125
0126 /* Roots *********************************************************************/
0127
0128 void nmod_poly_roots(nmod_poly_factor_t r,
0129                                    const nmod_poly_t f, int with_multiplicity);
0130
0131 int nmod_poly_roots_factored(nmod_poly_factor_t r,
0132              const nmod_poly_t f, int with_multiplicity, const n_factor_t * n);
0133
0134 /* Declare dead functions ****************************************************/
0135
0136 #define nmod_poly_factor_get_nmod_poly _Pragma("GCC error \"'nmod_poly_factor_get_nmod_poly' is deprecated. Use 'nmod_poly_factor_get_poly' instead.\"")
0137
0138 #ifdef __cplusplus
0139 }
0140 #endif
0141
0142 #endif