include/flint/fmpz_mod_poly.h

0001 /*
0002     Copyright (C) 2011 Sebastian Pancratz
0003     Copyright (C) 2014 William Hart
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_H
0014 #define FMPZ_MOD_POLY_H
0015
0016 #ifdef FMPZ_MOD_POLY_INLINES_C
0017 #define FMPZ_MOD_POLY_INLINE
0018 #else
0019 #define FMPZ_MOD_POLY_INLINE static inline
0020 #endif
0021
0022 #include "nmod_types.h"
0023 #include "fmpz_mod_types.h"
0024
0025 #ifdef __cplusplus
0026 extern "C" {
0027 #endif
0028
0029 #define FMPZ_MOD_POLY_HGCD_CUTOFF  128      /* HGCD: Basecase -> Recursion      */
0030 #define FMPZ_MOD_POLY_GCD_CUTOFF  256       /* GCD:  Euclidean -> HGCD          */
0031
0032 #define FMPZ_MOD_POLY_INV_NEWTON_CUTOFF  64 /* Inv series newton: Basecase -> Newton */
0033 #define FMPZ_MOD_POLY_DIV_DIVCONQUER_CUTOFF
0034
0035 #define FMPZ_MOD_POLY_EVALUATE_FMPZ_VEC  32 /* Evaluate fmpz_vec: Iter -> Fast  */
0036
0037 /*  Type definitions *********************************************************/
0038
0039 typedef struct
0040 {
0041    fmpz_t res;
0042    fmpz_t lc;
0043    slong len0;
0044    slong len1;
0045    slong off;
0046 } fmpz_mod_poly_res_struct;
0047
0048 typedef fmpz_mod_poly_res_struct fmpz_mod_poly_res_t[1];
0049
0050 typedef struct
0051 {
0052    fmpz_mod_poly_struct * pow;
0053    slong len;
0054 } fmpz_mod_poly_frobenius_powers_2exp_struct;
0055
0056 typedef fmpz_mod_poly_frobenius_powers_2exp_struct fmpz_mod_poly_frobenius_powers_2exp_t[1];
0057
0058 typedef struct
0059 {
0060    fmpz_mod_poly_struct * pow;
0061    slong len;
0062 } fmpz_mod_poly_frobenius_powers_struct;
0063
0064 typedef fmpz_mod_poly_frobenius_powers_struct fmpz_mod_poly_frobenius_powers_t[1];
0065
0066 typedef struct
0067 {
0068     fmpz_mat_struct * A;
0069     fmpz_mod_poly_struct * poly1;
0070     fmpz_mod_poly_struct * poly2;
0071     fmpz_mod_poly_struct * poly2inv;
0072     const fmpz_mod_ctx_struct * ctx;
0073 }
0074 fmpz_mod_poly_matrix_precompute_arg_t;
0075
0076 typedef struct
0077 {
0078     fmpz_mat_struct * A;
0079     fmpz_mod_poly_struct * res;
0080     fmpz_mod_poly_struct * poly1;
0081     fmpz_mod_poly_struct * poly3;
0082     fmpz_mod_poly_struct * poly3inv;
0083     const fmpz_mod_ctx_struct * ctx;
0084 }
0085 fmpz_mod_poly_compose_mod_precomp_preinv_arg_t;
0086
0087
0088 /*  Initialisation and memory management *************************************/
0089
0090 FMPZ_MOD_POLY_INLINE
0091 void fmpz_mod_poly_init(fmpz_mod_poly_t poly, const fmpz_mod_ctx_t FLINT_UNUSED(ctx))
0092 {
0093     poly->coeffs = NULL;
0094     poly->alloc  = 0;
0095     poly->length = 0;
0096 }
0097
0098 void fmpz_mod_poly_init2(fmpz_mod_poly_t poly, slong alloc,
0099                                                      const fmpz_mod_ctx_t FLINT_UNUSED(ctx));
0100
0101 void fmpz_mod_poly_clear(fmpz_mod_poly_t poly, const fmpz_mod_ctx_t FLINT_UNUSED(ctx));
0102
0103 void fmpz_mod_poly_realloc(fmpz_mod_poly_t poly, slong alloc,
0104                                                      const fmpz_mod_ctx_t ctx);
0105
0106 void _fmpz_mod_poly_fit_length(fmpz_mod_poly_t poly, slong len);
0107
0108 FMPZ_MOD_POLY_INLINE
0109 void fmpz_mod_poly_fit_length(fmpz_mod_poly_t poly, slong len,
0110                                                       const fmpz_mod_ctx_t FLINT_UNUSED(ctx))
0111 {
0112     _fmpz_mod_poly_fit_length(poly, len);
0113 }
0114
0115
0116 /*  Normalisation and truncation *********************************************/
0117
0118 FMPZ_MOD_POLY_INLINE
0119 void _fmpz_mod_poly_normalise(fmpz_mod_poly_t poly)
0120 {
0121     slong i;
0122
0123     for (i = poly->length - 1; (i >= 0) && !poly->coeffs[i]; i--) ;
0124     poly->length = i + 1;
0125 }
0126
0127 void _fmpz_mod_poly_set_length(fmpz_mod_poly_t poly, slong len);
0128
0129 void fmpz_mod_poly_truncate(fmpz_mod_poly_t poly, slong len, const fmpz_mod_ctx_t FLINT_UNUSED(ctx));
0130
0131 void fmpz_mod_poly_set_trunc(fmpz_mod_poly_t res, const fmpz_mod_poly_t poly, slong n, const fmpz_mod_ctx_t ctx);
0132
0133 int fmpz_mod_poly_is_canonical(const fmpz_mod_poly_t A, const fmpz_mod_ctx_t ctx);
0134
0135
0136 /*  Randomisation ************************************************************/
0137
0138 void fmpz_mod_poly_randtest(fmpz_mod_poly_t f, flint_rand_t state,
0139                                           slong len, const fmpz_mod_ctx_t ctx);
0140
0141 void fmpz_mod_poly_randtest_irreducible(fmpz_mod_poly_t f,
0142                       flint_rand_t state, slong len, const fmpz_mod_ctx_t ctx);
0143
0144 void fmpz_mod_poly_randtest_not_zero(fmpz_mod_poly_t f,
0145                       flint_rand_t state, slong len, const fmpz_mod_ctx_t ctx);
0146
0147 void fmpz_mod_poly_randtest_monic(fmpz_mod_poly_t f,
0148                       flint_rand_t state, slong len, const fmpz_mod_ctx_t ctx);
0149
0150 void fmpz_mod_poly_randtest_monic_irreducible(fmpz_mod_poly_t f,
0151                       flint_rand_t state, slong len, const fmpz_mod_ctx_t ctx);
0152
0153 void fmpz_mod_poly_randtest_monic_primitive(fmpz_mod_poly_t f,
0154                       flint_rand_t state, slong len, const fmpz_mod_ctx_t ctx);
0155
0156 void fmpz_mod_poly_randtest_trinomial(fmpz_mod_poly_t f, flint_rand_t state, slong len, const fmpz_mod_ctx_t ctx);
0157
0158 int fmpz_mod_poly_randtest_trinomial_irreducible(fmpz_mod_poly_t f,
0159                             flint_rand_t state, slong len, slong max_attempts,
0160                                                      const fmpz_mod_ctx_t ctx);
0161
0162 void fmpz_mod_poly_randtest_pentomial(fmpz_mod_poly_t f, flint_rand_t state, slong len, const fmpz_mod_ctx_t ctx);
0163
0164 int fmpz_mod_poly_randtest_pentomial_irreducible(fmpz_mod_poly_t f,
0165                             flint_rand_t state, slong len, slong max_attempts,
0166                                                      const fmpz_mod_ctx_t ctx);
0167
0168 void fmpz_mod_poly_randtest_sparse_irreducible(fmpz_mod_poly_t poly,
0169                       flint_rand_t state, slong len, const fmpz_mod_ctx_t ctx);
0170
0171 /*  Attributes ***************************************************************/
0172
0173 FMPZ_MOD_POLY_INLINE
0174 slong fmpz_mod_poly_length(const fmpz_mod_poly_t poly, const fmpz_mod_ctx_t FLINT_UNUSED(ctx))
0175 {
0176     return poly->length;
0177 }
0178 FMPZ_MOD_POLY_INLINE
0179 slong fmpz_mod_poly_degree(const fmpz_mod_poly_t poly, const fmpz_mod_ctx_t FLINT_UNUSED(ctx))
0180 {
0181     return poly->length - 1;
0182 }
0183
0184 FMPZ_MOD_POLY_INLINE
0185 fmpz * fmpz_mod_poly_lead(const fmpz_mod_poly_t poly, const fmpz_mod_ctx_t FLINT_UNUSED(ctx))
0186 {
0187     if (poly->length)
0188         return poly->coeffs + (poly->length - 1);
0189     else
0190         return NULL;
0191 }
0192
0193 FMPZ_MOD_POLY_INLINE
0194 int fmpz_mod_poly_is_monic(const fmpz_mod_poly_t f, const fmpz_mod_ctx_t FLINT_UNUSED(ctx))
0195 {
0196     return f->length > 0 && f->coeffs[f->length - 1] == WORD(1);
0197 }
0198
0199 FMPZ_MOD_POLY_INLINE
0200 int fmpz_mod_poly_is_one(const fmpz_mod_poly_t poly, const fmpz_mod_ctx_t FLINT_UNUSED(ctx))
0201 {
0202    return poly->length == 1 && poly->coeffs[0] == WORD(1);
0203 }
0204
0205 int fmpz_mod_poly_is_gen(const fmpz_mod_poly_t op, const fmpz_mod_ctx_t ctx);
0206
0207 int fmpz_mod_poly_is_unit(const fmpz_mod_poly_t op, const fmpz_mod_ctx_t ctx);
0208
0209 /*  Assignment and basic manipulation ****************************************/
0210
0211 void fmpz_mod_poly_set(fmpz_mod_poly_t poly1,
0212                         const fmpz_mod_poly_t poly2, const fmpz_mod_ctx_t ctx);
0213
0214 FMPZ_MOD_POLY_INLINE
0215 void fmpz_mod_poly_swap(fmpz_mod_poly_t poly1,
0216                                fmpz_mod_poly_t poly2, const fmpz_mod_ctx_t FLINT_UNUSED(ctx))
0217 {
0218     FLINT_SWAP(fmpz_mod_poly_struct, *poly1, *poly2);
0219 }
0220
0221 void _fmpz_mod_poly_reverse(fmpz * res, const fmpz * poly, slong len, slong n);
0222
0223 void fmpz_mod_poly_reverse(fmpz_mod_poly_t res,
0224                 const fmpz_mod_poly_t poly, slong n, const fmpz_mod_ctx_t ctx);
0225
0226 FMPZ_MOD_POLY_INLINE
0227 void fmpz_mod_poly_zero(fmpz_mod_poly_t poly, const fmpz_mod_ctx_t FLINT_UNUSED(ctx))
0228 {
0229    _fmpz_mod_poly_set_length(poly, 0);
0230 }
0231
0232 void fmpz_mod_poly_one(fmpz_mod_poly_t poly, const fmpz_mod_ctx_t ctx);
0233
0234 void fmpz_mod_poly_gen(fmpz_mod_poly_t poly, const fmpz_mod_ctx_t ctx);
0235
0236 void fmpz_mod_poly_zero_coeffs(fmpz_mod_poly_t poly, slong i, slong j, const fmpz_mod_ctx_t FLINT_UNUSED(ctx));
0237
0238 ulong fmpz_mod_poly_deflation(const fmpz_mod_poly_t input, const fmpz_mod_ctx_t FLINT_UNUSED(ctx));
0239 void fmpz_mod_poly_deflate(fmpz_mod_poly_t result, const fmpz_mod_poly_t input, ulong deflation, const fmpz_mod_ctx_t ctx);
0240 void fmpz_mod_poly_inflate(fmpz_mod_poly_t result, const fmpz_mod_poly_t input, ulong inflation, const fmpz_mod_ctx_t ctx);
0241
0242 /*  Conversion ***************************************************************/
0243
0244 void fmpz_mod_poly_set_ui(fmpz_mod_poly_t f, ulong x, const fmpz_mod_ctx_t ctx);
0245 void fmpz_mod_poly_set_nmod_poly(fmpz_mod_poly_t f, const nmod_poly_t g);
0246 void fmpz_mod_poly_set_fmpz(fmpz_mod_poly_t poly, const fmpz_t c, const fmpz_mod_ctx_t ctx);
0247 void fmpz_mod_poly_set_fmpz_poly(fmpz_mod_poly_t f, const fmpz_poly_t g, const fmpz_mod_ctx_t ctx);
0248
0249 void fmpz_mod_poly_get_nmod_poly(nmod_poly_t f, const fmpz_mod_poly_t g);
0250 void fmpz_mod_poly_get_fmpz_poly(fmpz_poly_t f, const fmpz_mod_poly_t g, const fmpz_mod_ctx_t FLINT_UNUSED(ctx));
0251
0252 /*  Comparison ***************************************************************/
0253
0254 int fmpz_mod_poly_equal(const fmpz_mod_poly_t poly1, const fmpz_mod_poly_t poly2, const fmpz_mod_ctx_t FLINT_UNUSED(ctx));
0255 int fmpz_mod_poly_equal_trunc(const fmpz_mod_poly_t poly1, const fmpz_mod_poly_t poly2, slong n, const fmpz_mod_ctx_t FLINT_UNUSED(ctx));
0256
0257 int fmpz_mod_poly_is_zero(const fmpz_mod_poly_t poly, const fmpz_mod_ctx_t FLINT_UNUSED(ctx));
0258
0259 /*  Getting and setting coefficients *****************************************/
0260
0261 void fmpz_mod_poly_set_coeff_fmpz(fmpz_mod_poly_t poly, slong n, const fmpz_t x, const fmpz_mod_ctx_t ctx);
0262 void fmpz_mod_poly_set_coeff_ui(fmpz_mod_poly_t poly, slong n, ulong x, const fmpz_mod_ctx_t ctx);
0263 void fmpz_mod_poly_set_coeff_si(fmpz_mod_poly_t poly, slong n, slong x, const fmpz_mod_ctx_t ctx);
0264
0265 void fmpz_mod_poly_get_coeff_fmpz(fmpz_t x, const fmpz_mod_poly_t poly, slong n, const fmpz_mod_ctx_t FLINT_UNUSED(ctx));
0266
0267 /*  Shifting *****************************************************************/
0268
0269 void _fmpz_mod_poly_shift_left(fmpz * res, const fmpz * poly, slong len, slong n);
0270 void fmpz_mod_poly_shift_left(fmpz_mod_poly_t f, const fmpz_mod_poly_t g, slong n, const fmpz_mod_ctx_t ctx);
0271
0272 void _fmpz_mod_poly_shift_right(fmpz * res, const fmpz * poly, slong len, slong n);
0273
0274 void fmpz_mod_poly_shift_right(fmpz_mod_poly_t f, const fmpz_mod_poly_t g, slong n, const fmpz_mod_ctx_t ctx);
0275
0276 /*  Addition and subtraction *************************************************/
0277
0278 void _fmpz_mod_poly_neg(fmpz *res, const fmpz *poly, slong len, const fmpz_mod_ctx_t ctx);
0279 void fmpz_mod_poly_neg(fmpz_mod_poly_t res, const fmpz_mod_poly_t poly, const fmpz_mod_ctx_t ctx);
0280
0281 void _fmpz_mod_poly_add(fmpz *res, const fmpz *poly1, slong len1, const fmpz *poly2, slong len2, const fmpz_mod_ctx_t ctx);
0282 void fmpz_mod_poly_add(fmpz_mod_poly_t res, const fmpz_mod_poly_t poly1, const fmpz_mod_poly_t poly2, const fmpz_mod_ctx_t ctx);
0283
0284 void _fmpz_mod_poly_sub(fmpz *res, const fmpz *poly1, slong len1, const fmpz *poly2, slong len2, const fmpz_mod_ctx_t ctx);
0285 void fmpz_mod_poly_sub(fmpz_mod_poly_t res, const fmpz_mod_poly_t poly1, const fmpz_mod_poly_t poly2, const fmpz_mod_ctx_t ctx);
0286
0287 void fmpz_mod_poly_add_series(fmpz_mod_poly_t res, const fmpz_mod_poly_t poly1, const fmpz_mod_poly_t poly2, slong n, const fmpz_mod_ctx_t ctx);
0288 void fmpz_mod_poly_sub_series(fmpz_mod_poly_t res, const fmpz_mod_poly_t poly1, const fmpz_mod_poly_t poly2, slong n, const fmpz_mod_ctx_t ctx);
0289
0290 /*  Scalar multiplication ****************************************************/
0291
0292 void _fmpz_mod_poly_scalar_mul_fmpz(fmpz *res, const fmpz *poly, slong len, const fmpz_t x, const fmpz_mod_ctx_t ctx);
0293 void _fmpz_mod_poly_scalar_mul_ui(fmpz *res, const fmpz *poly, slong len, ulong x, const fmpz_mod_ctx_t ctx);
0294
0295 void fmpz_mod_poly_scalar_mul_fmpz(fmpz_mod_poly_t res, const fmpz_mod_poly_t poly, const fmpz_t x, const fmpz_mod_ctx_t ctx);
0296 void fmpz_mod_poly_scalar_mul_ui(fmpz_mod_poly_t res, const fmpz_mod_poly_t poly, ulong x, const fmpz_mod_ctx_t ctx);
0297
0298 void fmpz_mod_poly_scalar_addmul_fmpz(fmpz_mod_poly_t A, const fmpz_mod_poly_t B, const fmpz_t x, const fmpz_mod_ctx_t ctx);
0299
0300 /*  Scalar division ****************************************************/
0301
0302 void _fmpz_mod_poly_scalar_div_fmpz(fmpz *res, const fmpz *poly, slong len, const fmpz_t x, const fmpz_mod_ctx_t ctx);
0303 void fmpz_mod_poly_scalar_div_fmpz(fmpz_mod_poly_t res, const fmpz_mod_poly_t poly, const fmpz_t x, const fmpz_mod_ctx_t ctx);
0304
0305 /*  Multiplication ***********************************************************/
0306
0307 void _fmpz_mod_poly_mul(fmpz *res, const fmpz *poly1, slong len1, const fmpz *poly2, slong len2, const fmpz_mod_ctx_t ctx);
0308 void fmpz_mod_poly_mul(fmpz_mod_poly_t res, const fmpz_mod_poly_t poly1, const fmpz_mod_poly_t poly2, const fmpz_mod_ctx_t ctx);
0309
0310 void _fmpz_mod_poly_mullow(fmpz *res, const fmpz *poly1, slong len1, const fmpz *poly2, slong len2, slong n, const fmpz_mod_ctx_t ctx);
0311 void fmpz_mod_poly_mullow(fmpz_mod_poly_t res, const fmpz_mod_poly_t poly1, const fmpz_mod_poly_t poly2, slong n, const fmpz_mod_ctx_t ctx);
0312
0313 void _fmpz_mod_poly_mulmid(fmpz *res, const fmpz *poly1, slong len1, const fmpz *poly2, slong len2, slong nlo, slong nhi, const fmpz_mod_ctx_t ctx);
0314 void fmpz_mod_poly_mulmid(fmpz_mod_poly_t res, const fmpz_mod_poly_t poly1, const fmpz_mod_poly_t poly2, slong nlo, slong nhi, const fmpz_mod_ctx_t ctx);
0315
0316 void _fmpz_mod_poly_sqr(fmpz *res, const fmpz *poly, slong len, const fmpz_mod_ctx_t ctx);
0317
0318 void fmpz_mod_poly_mulhigh(fmpz_mod_poly_t res, const fmpz_mod_poly_t poly1, const fmpz_mod_poly_t poly2, slong start, const fmpz_mod_ctx_t ctx);
0319
0320 void fmpz_mod_poly_sqr(fmpz_mod_poly_t res, const fmpz_mod_poly_t poly, const fmpz_mod_ctx_t ctx);
0321
0322 void _fmpz_mod_poly_mulmod(fmpz * res, const fmpz * poly1, slong len1, const fmpz * poly2, slong len2, const fmpz * f, slong lenf, const fmpz_mod_ctx_t ctx);
0323 void fmpz_mod_poly_mulmod(fmpz_mod_poly_t res, const fmpz_mod_poly_t poly1, const fmpz_mod_poly_t poly2, const fmpz_mod_poly_t f, const fmpz_mod_ctx_t ctx);
0324
0325 void _fmpz_mod_poly_mulmod_preinv(fmpz * res, const fmpz * poly1, slong len1, const fmpz * poly2, slong len2, const fmpz * f, slong lenf, const fmpz* finv, slong lenfinv, const fmpz_mod_ctx_t ctx);
0326 void fmpz_mod_poly_mulmod_preinv(fmpz_mod_poly_t res, const fmpz_mod_poly_t poly1, const fmpz_mod_poly_t poly2, const fmpz_mod_poly_t f, const fmpz_mod_poly_t finv, const fmpz_mod_ctx_t ctx);
0327
0328 /*  Powering *****************************************************************/
0329
0330 void _fmpz_mod_poly_pow(fmpz *rop, const fmpz *op, slong len, ulong e, const fmpz_mod_ctx_t ctx);
0331 void fmpz_mod_poly_pow(fmpz_mod_poly_t rop, const fmpz_mod_poly_t op, ulong e, const fmpz_mod_ctx_t ctx);
0332
0333 void _fmpz_mod_poly_pow_trunc(fmpz * res, const fmpz * poly, ulong e, slong trunc, const fmpz_mod_ctx_t ctx);
0334
0335 void fmpz_mod_poly_pow_trunc(fmpz_mod_poly_t res, const fmpz_mod_poly_t poly, ulong e, slong trunc, const fmpz_mod_ctx_t ctx);
0336 void _fmpz_mod_poly_pow_trunc_binexp(fmpz * res, const fmpz * poly, ulong e, slong trunc, const fmpz_mod_ctx_t ctx);
0337
0338 void fmpz_mod_poly_pow_trunc_binexp(fmpz_mod_poly_t res, const fmpz_mod_poly_t poly, ulong e, slong trunc, const fmpz_mod_ctx_t ctx);
0339
0340 void _fmpz_mod_poly_powmod_ui_binexp(fmpz * res, const fmpz * poly, ulong e, const fmpz * f, slong lenf, const fmpz_mod_ctx_t ctx);
0341 void fmpz_mod_poly_powmod_ui_binexp(fmpz_mod_poly_t res, const fmpz_mod_poly_t poly, ulong e, const fmpz_mod_poly_t f, const fmpz_mod_ctx_t ctx);
0342
0343 void _fmpz_mod_poly_powmod_ui_binexp_preinv(fmpz * res, const fmpz * poly,
0344                               ulong e, const fmpz * f, slong lenf,
0345                               const fmpz * finv, slong lenfinv, const fmpz_mod_ctx_t ctx);
0346
0347 void fmpz_mod_poly_powmod_ui_binexp_preinv(fmpz_mod_poly_t res,
0348                          const fmpz_mod_poly_t poly, ulong e,
0349                          const fmpz_mod_poly_t f, const fmpz_mod_poly_t finv,
0350                                                      const fmpz_mod_ctx_t ctx);
0351
0352 void _fmpz_mod_poly_powmod_fmpz_binexp(fmpz * res, const fmpz * poly,
0353                                   const fmpz_t e, const fmpz * f,
0354                                   slong lenf, const fmpz_mod_ctx_t ctx);
0355
0356 void fmpz_mod_poly_powmod_fmpz_binexp(fmpz_mod_poly_t res,
0357                             const fmpz_mod_poly_t poly, const fmpz_t e,
0358                             const fmpz_mod_poly_t f, const fmpz_mod_ctx_t ctx);
0359
0360 void _fmpz_mod_poly_powmod_fmpz_binexp_preinv(fmpz * res, const fmpz * poly,
0361                               const fmpz_t e, const fmpz * f, slong lenf,
0362                               const fmpz* finv, slong lenfinv, const fmpz_mod_ctx_t ctx);
0363
0364 void fmpz_mod_poly_powmod_fmpz_binexp_preinv(fmpz_mod_poly_t res,
0365                           const fmpz_mod_poly_t poly, const fmpz_t e,
0366                           const fmpz_mod_poly_t f, const fmpz_mod_poly_t finv,
0367                                                      const fmpz_mod_ctx_t ctx);
0368
0369 void _fmpz_mod_poly_powmod_x_fmpz_preinv(fmpz * res, const fmpz_t e,
0370                   const fmpz * f, slong lenf, const fmpz* finv, slong lenfinv,
0371                                                                const fmpz_mod_ctx_t ctx);
0372
0373 void fmpz_mod_poly_powmod_x_fmpz_preinv(fmpz_mod_poly_t res,
0374          const fmpz_t e, const fmpz_mod_poly_t f, const fmpz_mod_poly_t finv,
0375                                                      const fmpz_mod_ctx_t ctx);
0376
0377 void fmpz_mod_poly_powmod_linear_fmpz_preinv(fmpz_mod_poly_t res,
0378                       const fmpz_t a, const fmpz_t e, const fmpz_mod_poly_t f,
0379                          const fmpz_mod_poly_t finv, const fmpz_mod_ctx_t ctx);
0380
0381 void _fmpz_mod_poly_powers_mod_preinv_naive(fmpz ** res,
0382                     const fmpz * f, slong flen, slong n, const fmpz * g,
0383                  slong glen, const fmpz * ginv, slong ginvlen, const fmpz_mod_ctx_t ctx);
0384
0385 void fmpz_mod_poly_powers_mod_naive(fmpz_mod_poly_struct * res,
0386                     const fmpz_mod_poly_t f, slong n, const fmpz_mod_poly_t g,
0387                                                      const fmpz_mod_ctx_t ctx);
0388
0389 void _fmpz_mod_poly_powers_mod_preinv_threaded_pool(fmpz ** res,
0390        const fmpz * f, slong flen, slong n, const fmpz * g, slong glen,
0391                           const fmpz * ginv, slong ginvlen, const fmpz_mod_ctx_t ctx,
0392                           thread_pool_handle * threads, slong num_threads);
0393
0394 void fmpz_mod_poly_powers_mod_bsgs(fmpz_mod_poly_struct * res,
0395                     const fmpz_mod_poly_t f, slong n, const fmpz_mod_poly_t g,
0396                                                      const fmpz_mod_ctx_t ctx);
0397
0398 void fmpz_mod_poly_frobenius_powers_2exp_precomp(
0399             fmpz_mod_poly_frobenius_powers_2exp_t pow, const fmpz_mod_poly_t f,
0400                 const fmpz_mod_poly_t finv, ulong m, const fmpz_mod_ctx_t ctx);
0401
0402
0403 void fmpz_mod_poly_frobenius_powers_2exp_clear(
0404           fmpz_mod_poly_frobenius_powers_2exp_t pow, const fmpz_mod_ctx_t ctx);
0405
0406 void fmpz_mod_poly_frobenius_power(fmpz_mod_poly_t res,
0407                             fmpz_mod_poly_frobenius_powers_2exp_t pow,
0408                    const fmpz_mod_poly_t f, ulong m, const fmpz_mod_ctx_t ctx);
0409
0410 void fmpz_mod_poly_frobenius_powers_precomp(
0411                 fmpz_mod_poly_frobenius_powers_t pow, const fmpz_mod_poly_t f,
0412                 const fmpz_mod_poly_t finv, ulong m, const fmpz_mod_ctx_t ctx);
0413
0414 void fmpz_mod_poly_frobenius_powers_clear(
0415                fmpz_mod_poly_frobenius_powers_t pow, const fmpz_mod_ctx_t ctx);
0416
0417 /*  Division *****************************************************************/
0418
0419 void _fmpz_mod_poly_divrem_basecase(fmpz * Q, fmpz * R,
0420                     const fmpz * A, slong lenA, const fmpz * B, slong lenB,
0421                                             const fmpz_t invB, const fmpz_mod_ctx_t ctx);
0422
0423 void fmpz_mod_poly_divrem_basecase(fmpz_mod_poly_t Q, fmpz_mod_poly_t R,
0424                              const fmpz_mod_poly_t A, const fmpz_mod_poly_t B,
0425                                                      const fmpz_mod_ctx_t ctx);
0426
0427 void _fmpz_mod_poly_div_newton_n_preinv (fmpz* Q, const fmpz* A, slong lenA,
0428                                    const fmpz* FLINT_UNUSED(B), slong lenB, const fmpz* Binv,
0429                                    slong lenBinv, const fmpz_mod_ctx_t ctx);
0430
0431 void fmpz_mod_poly_div_newton_n_preinv(fmpz_mod_poly_t Q,
0432                          const fmpz_mod_poly_t A, const fmpz_mod_poly_t B,
0433                          const fmpz_mod_poly_t Binv, const fmpz_mod_ctx_t ctx);
0434
0435 void _fmpz_mod_poly_divrem_newton_n_preinv (fmpz* Q, fmpz* R,
0436              const fmpz* A, slong lenA, const fmpz* B, slong lenB,
0437                             const fmpz* Binv, slong lenBinv, const fmpz_mod_ctx_t ctx);
0438
0439 void fmpz_mod_poly_divrem_newton_n_preinv(fmpz_mod_poly_t Q,
0440           fmpz_mod_poly_t R, const fmpz_mod_poly_t A, const fmpz_mod_poly_t B,
0441                          const fmpz_mod_poly_t Binv, const fmpz_mod_ctx_t ctx);
0442
0443 ulong fmpz_mod_poly_remove(fmpz_mod_poly_t f,
0444                             const fmpz_mod_poly_t p, const fmpz_mod_ctx_t ctx);
0445
0446 void _fmpz_mod_poly_rem_basecase(fmpz * R,
0447                         const fmpz * A, slong lenA, const fmpz * B, slong lenB,
0448                                             const fmpz_t invB, const fmpz_mod_ctx_t ctx);
0449
0450 void fmpz_mod_poly_rem_basecase(fmpz_mod_poly_t R,
0451                             const fmpz_mod_poly_t A, const fmpz_mod_poly_t B,
0452                                                      const fmpz_mod_ctx_t ctx);
0453
0454 void _fmpz_mod_poly_divrem(fmpz *Q, fmpz *R,
0455                            const fmpz *A, slong lenA, const fmpz *B, slong lenB,
0456                            const fmpz_t invB, const fmpz_mod_ctx_t ctx);
0457
0458 void fmpz_mod_poly_divrem(fmpz_mod_poly_t Q, fmpz_mod_poly_t R,
0459     const fmpz_mod_poly_t A, const fmpz_mod_poly_t B, const fmpz_mod_ctx_t ctx);
0460
0461 void _fmpz_mod_poly_div(fmpz *Q,
0462                            const fmpz *A, slong lenA, const fmpz *B, slong lenB,
0463                            const fmpz_t invB, const fmpz_mod_ctx_t ctx);
0464
0465 void fmpz_mod_poly_div(fmpz_mod_poly_t Q, const fmpz_mod_poly_t A,
0466                               const fmpz_mod_poly_t B, const fmpz_mod_ctx_t ctx);
0467
0468 void _fmpz_mod_poly_divrem_f(fmpz_t f, fmpz *Q, fmpz *R,
0469                              const fmpz *A, slong lenA,
0470                              const fmpz *B, slong lenB, const fmpz_mod_ctx_t ctx);
0471
0472 void fmpz_mod_poly_divrem_f(fmpz_t f, fmpz_mod_poly_t Q,
0473           fmpz_mod_poly_t R, const fmpz_mod_poly_t A, const fmpz_mod_poly_t B,
0474                                                      const fmpz_mod_ctx_t ctx);
0475
0476 void _fmpz_mod_poly_rem(fmpz *R, const fmpz *A, slong lenA, const fmpz *B, slong lenB, const fmpz_t invB, const fmpz_mod_ctx_t ctx);
0477 void fmpz_mod_poly_rem(fmpz_mod_poly_t R, const fmpz_mod_poly_t A, const fmpz_mod_poly_t B, const fmpz_mod_ctx_t ctx);
0478 void fmpz_mod_poly_rem_f(fmpz_t f, fmpz_mod_poly_t R, const fmpz_mod_poly_t A, const fmpz_mod_poly_t B, const fmpz_mod_ctx_t ctx);
0479
0480 /* Divisibility testing ******************************************************/
0481
0482 int _fmpz_mod_poly_divides_classical(fmpz * Q, const fmpz * A,
0483              slong lenA, const fmpz * B, slong lenB, const fmpz_mod_ctx_t ctx);
0484
0485 int fmpz_mod_poly_divides_classical(fmpz_mod_poly_t Q,
0486                         const fmpz_mod_poly_t A, const fmpz_mod_poly_t B,
0487                                                      const fmpz_mod_ctx_t ctx);
0488
0489 int _fmpz_mod_poly_divides(fmpz * Q, const fmpz * A, slong lenA,
0490                          const fmpz * B, slong lenB, const fmpz_mod_ctx_t ctx);
0491
0492 int fmpz_mod_poly_divides(fmpz_mod_poly_t Q, const fmpz_mod_poly_t A,
0493                             const fmpz_mod_poly_t B, const fmpz_mod_ctx_t ctx);
0494
0495 /*  Power series inversion ***************************************************/
0496
0497 void _fmpz_mod_poly_inv_series(fmpz * Qinv, const fmpz * Q, slong Qlen, slong n, const fmpz_mod_ctx_t ctx);
0498 void fmpz_mod_poly_inv_series(fmpz_mod_poly_t Qinv, const fmpz_mod_poly_t Q, slong n, const fmpz_mod_ctx_t ctx);
0499
0500 void
0501 fmpz_mod_poly_inv_series_f(fmpz_t f, fmpz_mod_poly_t Qinv,
0502                     const fmpz_mod_poly_t Q, slong n, const fmpz_mod_ctx_t ctx);
0503
0504 void _fmpz_mod_poly_div_series(fmpz * Q, const fmpz * A, slong Alen,
0505                       const fmpz * B, slong Blen, slong n, const fmpz_mod_ctx_t ctx);
0506 void fmpz_mod_poly_div_series(fmpz_mod_poly_t Q,
0507                     const fmpz_mod_poly_t A, const fmpz_mod_poly_t B, slong n,
0508                                                      const fmpz_mod_ctx_t ctx);
0509
0510 /*  Greatest common divisor **************************************************/
0511
0512 void fmpz_mod_poly_make_monic(fmpz_mod_poly_t res,
0513                          const fmpz_mod_poly_t poly, const fmpz_mod_ctx_t ctx);
0514
0515 void fmpz_mod_poly_make_monic_f(fmpz_t f, fmpz_mod_poly_t res,
0516                          const fmpz_mod_poly_t poly, const fmpz_mod_ctx_t ctx);
0517
0518 slong _fmpz_mod_poly_gcd(fmpz *G, const fmpz *A, slong lenA,
0519                                            const fmpz *B, slong lenB,
0520                                            const fmpz_mod_ctx_t ctx);
0521
0522 void fmpz_mod_poly_gcd(fmpz_mod_poly_t G,
0523                              const fmpz_mod_poly_t A, const fmpz_mod_poly_t B,
0524                                                      const fmpz_mod_ctx_t ctx);
0525
0526 slong _fmpz_mod_poly_gcd_euclidean_f(fmpz_t f, fmpz *G,
0527                                     const fmpz *A, slong lenA,
0528                                     const fmpz *B, slong lenB, const fmpz_mod_ctx_t ctx);
0529
0530 void fmpz_mod_poly_gcd_euclidean_f(fmpz_t f, fmpz_mod_poly_t G,
0531                              const fmpz_mod_poly_t A, const fmpz_mod_poly_t B,
0532                                                      const fmpz_mod_ctx_t ctx);
0533
0534 FMPZ_MOD_POLY_INLINE
0535 slong _fmpz_mod_poly_gcd_f(fmpz_t f, fmpz *G,
0536                           const fmpz *A, slong lenA,
0537                           const fmpz *B, slong lenB, const fmpz_mod_ctx_t ctx)
0538 {
0539     return _fmpz_mod_poly_gcd_euclidean_f(f, G, A, lenA, B, lenB, ctx);
0540 }
0541
0542 FMPZ_MOD_POLY_INLINE
0543 void fmpz_mod_poly_gcd_f(fmpz_t f, fmpz_mod_poly_t G, const fmpz_mod_poly_t A,
0544                              const fmpz_mod_poly_t B, const fmpz_mod_ctx_t ctx)
0545 {
0546     fmpz_mod_poly_gcd_euclidean_f(f, G, A, B, ctx);
0547 }
0548
0549 slong _fmpz_mod_poly_hgcd(fmpz **M, slong *lenM,
0550                      fmpz *A, slong *lenA, fmpz *B, slong *lenB,
0551                      const fmpz *a, slong lena, const fmpz *b, slong lenb,
0552                      const fmpz_mod_ctx_t ctx);
0553
0554 slong _fmpz_mod_poly_xgcd_euclidean_f(fmpz_t f, fmpz *G, fmpz *S, fmpz *T,
0555                                    const fmpz *A, slong lenA,
0556                                    const fmpz *B, slong lenB,
0557                                    const fmpz_t invB, const fmpz_mod_ctx_t ctx);
0558
0559 void fmpz_mod_poly_xgcd_euclidean_f(fmpz_t f, fmpz_mod_poly_t G,
0560                              fmpz_mod_poly_t S, fmpz_mod_poly_t T,
0561                              const fmpz_mod_poly_t A, const fmpz_mod_poly_t B,
0562                                                      const fmpz_mod_ctx_t ctx);
0563
0564 slong _fmpz_mod_poly_xgcd(fmpz *G, fmpz *S, fmpz *T,
0565                           const fmpz *A, slong lenA, const fmpz *B, slong lenB,
0566                           const fmpz_t FLINT_UNUSED(invB), const fmpz_mod_ctx_t ctx);
0567
0568 void fmpz_mod_poly_xgcd(fmpz_mod_poly_t G, fmpz_mod_poly_t S,
0569           fmpz_mod_poly_t T, const fmpz_mod_poly_t A, const fmpz_mod_poly_t B,
0570                                                      const fmpz_mod_ctx_t ctx);
0571
0572 FMPZ_MOD_POLY_INLINE slong
0573 _fmpz_mod_poly_xgcd_f(fmpz_t f, fmpz *G, fmpz *S, fmpz *T,
0574                     const fmpz *A, slong lenA, const fmpz *B, slong lenB,
0575                     const fmpz_t invB, const fmpz_mod_ctx_t ctx)
0576 {
0577     return _fmpz_mod_poly_xgcd_euclidean_f(f, G, S, T, A, lenA, B, lenB, invB, ctx);
0578 }
0579
0580 FMPZ_MOD_POLY_INLINE void
0581 fmpz_mod_poly_xgcd_f(fmpz_t f, fmpz_mod_poly_t G, fmpz_mod_poly_t S,
0582           fmpz_mod_poly_t T, const fmpz_mod_poly_t A, const fmpz_mod_poly_t B,
0583                                                       const fmpz_mod_ctx_t ctx)
0584 {
0585     fmpz_mod_poly_xgcd_euclidean_f(f, G, S, T, A, B, ctx);
0586 }
0587
0588 slong _fmpz_mod_poly_gcdinv_euclidean_f(fmpz_t f, fmpz *G, fmpz *S,
0589                                    const fmpz *A, slong lenA,
0590                                    const fmpz *B, slong lenB,
0591                                    const fmpz_t FLINT_UNUSED(invA), const fmpz_mod_ctx_t ctx);
0592
0593 void fmpz_mod_poly_gcdinv_euclidean_f(fmpz_t f, fmpz_mod_poly_t G,
0594           fmpz_mod_poly_t S, const fmpz_mod_poly_t A, const fmpz_mod_poly_t B,
0595                                                      const fmpz_mod_ctx_t ctx);
0596
0597 slong _fmpz_mod_poly_gcdinv_euclidean(fmpz *G, fmpz *S,
0598                   const fmpz *A, slong lenA, const fmpz *B, slong lenB,
0599                                             const fmpz_t invA, const fmpz_mod_ctx_t ctx);
0600
0601 void fmpz_mod_poly_gcdinv_euclidean(fmpz_mod_poly_t G,
0602           fmpz_mod_poly_t S, const fmpz_mod_poly_t A, const fmpz_mod_poly_t B,
0603                                                      const fmpz_mod_ctx_t ctx);
0604
0605 slong _fmpz_mod_poly_gcdinv(fmpz *G, fmpz *S,
0606                            const fmpz *A, slong lenA, const fmpz *B, slong lenB,
0607                            const fmpz_mod_ctx_t ctx);
0608
0609 void fmpz_mod_poly_gcdinv(fmpz_mod_poly_t G, fmpz_mod_poly_t S,
0610                           const fmpz_mod_poly_t A, const fmpz_mod_poly_t B,
0611                                                      const fmpz_mod_ctx_t ctx);
0612
0613 slong _fmpz_mod_poly_gcdinv_f(fmpz_t f, fmpz *G, fmpz *S,
0614                            const fmpz *A, slong lenA, const fmpz *B, slong lenB,
0615                            const fmpz_mod_ctx_t ctx);
0616
0617 void fmpz_mod_poly_gcdinv_f(fmpz_t f, fmpz_mod_poly_t G,
0618           fmpz_mod_poly_t S, const fmpz_mod_poly_t A, const fmpz_mod_poly_t B,
0619                                                      const fmpz_mod_ctx_t ctx);
0620
0621 int _fmpz_mod_poly_invmod(fmpz *A,
0622                           const fmpz *B, slong lenB,
0623                           const fmpz *P, slong lenP, const fmpz_mod_ctx_t ctx);
0624
0625 int _fmpz_mod_poly_invmod_f(fmpz_t f, fmpz *A,
0626                           const fmpz *B, slong lenB,
0627                           const fmpz *P, slong lenP, const fmpz_mod_ctx_t ctx);
0628
0629 int fmpz_mod_poly_invmod(fmpz_mod_poly_t A, const fmpz_mod_poly_t B,
0630                             const fmpz_mod_poly_t P, const fmpz_mod_ctx_t ctx);
0631
0632 int fmpz_mod_poly_invmod_f(fmpz_t f, fmpz_mod_poly_t A,
0633                          const fmpz_mod_poly_t B, const fmpz_mod_poly_t P,
0634                                                      const fmpz_mod_ctx_t ctx);
0635
0636 /* Square root ***************************************************************/
0637
0638 void _fmpz_mod_poly_invsqrt_series(fmpz * g,
0639                                   const fmpz * h, slong hlen, slong n, const fmpz_mod_ctx_t mod);
0640
0641 void fmpz_mod_poly_invsqrt_series(fmpz_mod_poly_t g,
0642                          const fmpz_mod_poly_t h, slong n, const fmpz_mod_ctx_t ctx);
0643
0644 void _fmpz_mod_poly_sqrt_series(fmpz * g,
0645                                   const fmpz * h, slong hlen, slong n, const fmpz_mod_ctx_t mod);
0646
0647 void fmpz_mod_poly_sqrt_series(fmpz_mod_poly_t g,
0648                          const fmpz_mod_poly_t h, slong n, const fmpz_mod_ctx_t ctx);
0649
0650 int _fmpz_mod_poly_sqrt(fmpz * s,
0651                                 const fmpz * p, slong len, const fmpz_mod_ctx_t mod);
0652
0653 int fmpz_mod_poly_sqrt(fmpz_mod_poly_t b,
0654                                   const fmpz_mod_poly_t a, const fmpz_mod_ctx_t ctx);
0655
0656 /*  Minpoly  *****************************************************************/
0657
0658 slong _fmpz_mod_poly_minpoly_bm(fmpz * poly, const fmpz * seq, slong len, const fmpz_mod_ctx_t ctx);
0659 void fmpz_mod_poly_minpoly_bm(fmpz_mod_poly_t poly, const fmpz * seq, slong len, const fmpz_mod_ctx_t ctx);
0660
0661 slong _fmpz_mod_poly_minpoly_hgcd(fmpz * poly, const fmpz* seq, slong len, const fmpz_mod_ctx_t ctx);
0662 void fmpz_mod_poly_minpoly_hgcd(fmpz_mod_poly_t poly, const fmpz* seq, slong len, const fmpz_mod_ctx_t ctx);
0663
0664 slong _fmpz_mod_poly_minpoly(fmpz* poly, const fmpz* seq, slong len, const fmpz_mod_ctx_t ctx);
0665 void fmpz_mod_poly_minpoly(fmpz_mod_poly_t poly, const fmpz* seq, slong len, const fmpz_mod_ctx_t ctx);
0666
0667 /*  Resultant  ***************************************************************/
0668
0669 void _fmpz_mod_poly_resultant(fmpz_t res, const fmpz *A, slong lenA, const fmpz *B, slong lenB, const fmpz_mod_ctx_t ctx);
0670 void fmpz_mod_poly_resultant(fmpz_t res, const fmpz_mod_poly_t A, const fmpz_mod_poly_t B, const fmpz_mod_ctx_t ctx);
0671
0672 /*  Discriminant  ************************************************************/
0673
0674 void _fmpz_mod_poly_discriminant(fmpz_t d, const fmpz *poly, slong len, const fmpz_mod_ctx_t ctx);
0675 void fmpz_mod_poly_discriminant(fmpz_t d, const fmpz_mod_poly_t f, const fmpz_mod_ctx_t ctx);
0676
0677 /*  Derivative  **************************************************************/
0678
0679 void _fmpz_mod_poly_derivative(fmpz *res, const fmpz *poly, slong len, const fmpz_mod_ctx_t ctx);
0680 void fmpz_mod_poly_derivative(fmpz_mod_poly_t res, const fmpz_mod_poly_t poly, const fmpz_mod_ctx_t ctx);
0681
0682 /*  Evaluation  **************************************************************/
0683
0684 void _fmpz_mod_poly_evaluate_fmpz(fmpz_t res, const fmpz *poly, slong len, const fmpz_t a, const fmpz_mod_ctx_t ctx);
0685 void fmpz_mod_poly_evaluate_fmpz(fmpz_t res, const fmpz_mod_poly_t poly, const fmpz_t a, const fmpz_mod_ctx_t ctx);
0686
0687 fmpz_poly_struct ** _fmpz_mod_poly_tree_alloc(slong len);
0688 void _fmpz_mod_poly_tree_free(fmpz_poly_struct ** tree, slong len);
0689 void _fmpz_mod_poly_tree_build(fmpz_poly_struct ** tree, const fmpz * roots, slong len, const fmpz_mod_ctx_t ctx);
0690
0691 void _fmpz_mod_poly_evaluate_fmpz_vec_iter(fmpz * ys, const fmpz * coeffs, slong len, const fmpz * xs, slong n, const fmpz_mod_ctx_t ctx);
0692 void fmpz_mod_poly_evaluate_fmpz_vec_iter(fmpz * ys, const fmpz_mod_poly_t poly, const fmpz * xs, slong n, const fmpz_mod_ctx_t ctx);
0693
0694 void _fmpz_mod_poly_evaluate_fmpz_vec_fast_precomp(fmpz * vs, const fmpz * poly, slong plen, fmpz_poly_struct * const * tree, slong len, const fmpz_mod_ctx_t ctx);
0695
0696 void _fmpz_mod_poly_evaluate_fmpz_vec_fast(fmpz * ys, const fmpz * poly, slong plen, const fmpz * xs, slong n, const fmpz_mod_ctx_t ctx);
0697 void fmpz_mod_poly_evaluate_fmpz_vec_fast(fmpz * ys, const fmpz_mod_poly_t poly, const fmpz * xs, slong n, const fmpz_mod_ctx_t ctx);
0698
0699 void _fmpz_mod_poly_evaluate_fmpz_vec(fmpz * ys, const fmpz * coeffs, slong len, const fmpz * xs, slong n, const fmpz_mod_ctx_t ctx);
0700 void fmpz_mod_poly_evaluate_fmpz_vec(fmpz * ys, const fmpz_mod_poly_t poly, const fmpz * xs, slong n, const fmpz_mod_ctx_t ctx);
0701
0702 /*  Composition  *************************************************************/
0703
0704 void _fmpz_mod_poly_compose(fmpz *res, const fmpz *poly1, slong len1,
0705                                               const fmpz *poly2, slong len2,
0706                                               const fmpz_mod_ctx_t ctx);
0707
0708 void fmpz_mod_poly_compose(fmpz_mod_poly_t res,
0709                     const fmpz_mod_poly_t poly1, const fmpz_mod_poly_t poly2,
0710                                                      const fmpz_mod_ctx_t ctx);
0711
0712 /* Modular composition  ******************************************************/
0713
0714 void _fmpz_mod_poly_compose_mod(fmpz * res, const fmpz * f, slong lenf, const fmpz * g,
0715                                        const fmpz * h, slong lenh, const fmpz_mod_ctx_t ctx);
0716
0717 void fmpz_mod_poly_compose_mod(fmpz_mod_poly_t res,
0718                      const fmpz_mod_poly_t poly1, const fmpz_mod_poly_t poly2,
0719                         const fmpz_mod_poly_t poly3, const fmpz_mod_ctx_t ctx);
0720
0721 void _fmpz_mod_poly_compose_mod_brent_kung(fmpz * res, const fmpz * poly1, slong len1,
0722                               const fmpz * poly2, const fmpz * poly3, slong len3, const fmpz_mod_ctx_t ctx);
0723
0724 void fmpz_mod_poly_compose_mod_brent_kung(fmpz_mod_poly_t res,
0725                      const fmpz_mod_poly_t poly1, const fmpz_mod_poly_t poly2,
0726                         const fmpz_mod_poly_t poly3, const fmpz_mod_ctx_t ctx);
0727
0728 void _fmpz_mod_poly_reduce_matrix_mod_poly (fmpz_mat_t A,
0729         const fmpz_mat_t B, const fmpz_mod_poly_t f, const fmpz_mod_ctx_t ctx);
0730
0731 void _fmpz_mod_poly_precompute_matrix(fmpz_mat_t A, const fmpz * poly1,
0732                           const fmpz * poly2, slong len2, const fmpz * poly2inv,
0733                           slong len2inv, const fmpz_mod_ctx_t ctx);
0734
0735 void _fmpz_mod_poly_precompute_matrix_worker(void * arg_ptr);
0736
0737 void fmpz_mod_poly_precompute_matrix(fmpz_mat_t A,
0738                      const fmpz_mod_poly_t poly1, const fmpz_mod_poly_t poly2,
0739                      const fmpz_mod_poly_t poly2inv, const fmpz_mod_ctx_t ctx);
0740
0741 void _fmpz_mod_poly_compose_mod_brent_kung_precomp_preinv(fmpz * res,
0742          const fmpz * poly1, slong len1, const fmpz_mat_t A, const fmpz * poly3,
0743          slong len3, const fmpz * poly3inv, slong len3inv, const fmpz_mod_ctx_t ctx);
0744
0745 void _fmpz_mod_poly_compose_mod_brent_kung_precomp_preinv_worker(void * arg_ptr);
0746
0747 void fmpz_mod_poly_compose_mod_brent_kung_precomp_preinv(fmpz_mod_poly_t res,
0748                    const fmpz_mod_poly_t poly1, const fmpz_mat_t A,
0749                    const fmpz_mod_poly_t poly3, const fmpz_mod_poly_t poly3inv,
0750                                                      const fmpz_mod_ctx_t ctx);
0751
0752 void _fmpz_mod_poly_compose_mod_brent_kung_preinv(fmpz * res, const fmpz * poly1,
0753                  slong len1, const fmpz * poly2, const fmpz * poly3, slong len3,
0754                  const fmpz * poly3inv, slong len3inv, const fmpz_mod_ctx_t ctx);
0755
0756 void fmpz_mod_poly_compose_mod_brent_kung_preinv(fmpz_mod_poly_t res,
0757                    const fmpz_mod_poly_t poly1, const fmpz_mod_poly_t poly2,
0758                    const fmpz_mod_poly_t poly3, const fmpz_mod_poly_t poly3inv,
0759                                                      const fmpz_mod_ctx_t ctx);
0760
0761 void _fmpz_mod_poly_compose_mod_horner(fmpz * res, const fmpz * f, slong lenf, const fmpz * g,
0762                                               const fmpz * h, slong lenh, const fmpz_mod_ctx_t ctx);
0763
0764 void fmpz_mod_poly_compose_mod_horner(fmpz_mod_poly_t res,
0765                      const fmpz_mod_poly_t poly1, const fmpz_mod_poly_t poly2,
0766                         const fmpz_mod_poly_t poly3, const fmpz_mod_ctx_t ctx);
0767
0768 void
0769 _fmpz_mod_poly_compose_mod_brent_kung_vec_preinv(fmpz_mod_poly_struct * res,
0770                                                 const fmpz_mod_poly_struct *
0771                                                 polys, slong FLINT_UNUSED(lenpolys), slong l,
0772                                                 const fmpz * g, slong glen,
0773                                                 const fmpz * poly, slong len,
0774                                                 const fmpz * polyinv,
0775                                                 slong leninv, const fmpz_mod_ctx_t ctx);
0776
0777 void fmpz_mod_poly_compose_mod_brent_kung_vec_preinv(
0778       fmpz_mod_poly_struct * res, const fmpz_mod_poly_struct * polys,
0779       slong len1,slong n, const fmpz_mod_poly_t g, const fmpz_mod_poly_t poly,
0780                       const fmpz_mod_poly_t polyinv, const fmpz_mod_ctx_t ctx);
0781
0782 void
0783 _fmpz_mod_poly_compose_mod_brent_kung_vec_preinv_threaded_pool(fmpz_mod_poly_struct * res,
0784                                                  const fmpz_mod_poly_struct * polys,
0785                                                  slong FLINT_UNUSED(lenpolys), slong l,
0786                                                  const fmpz * g, slong glen,
0787                                                  const fmpz * poly, slong len,
0788                                                  const fmpz * polyinv, slong leninv,
0789                                                  const fmpz_mod_ctx_t ctx,
0790                                                  thread_pool_handle * threads,
0791                                                  slong num_threads);
0792
0793 void fmpz_mod_poly_compose_mod_brent_kung_vec_preinv_threaded_pool(fmpz_mod_poly_struct * res,
0794             const fmpz_mod_poly_struct * polys, slong len1, slong n,
0795             const fmpz_mod_poly_t g, const fmpz_mod_poly_t poly,
0796             const fmpz_mod_poly_t polyinv, const fmpz_mod_ctx_t ctx,
0797                               thread_pool_handle * threads, slong num_threads);
0798
0799 void
0800 fmpz_mod_poly_compose_mod_brent_kung_vec_preinv_threaded(fmpz_mod_poly_struct * res,
0801                     const fmpz_mod_poly_struct * polys, slong len1, slong n,
0802                     const fmpz_mod_poly_t g, const fmpz_mod_poly_t poly,
0803                       const fmpz_mod_poly_t polyinv, const fmpz_mod_ctx_t ctx);
0804
0805 /* Norms *********************************************************************/
0806
0807 slong fmpz_mod_poly_hamming_weight(const fmpz_mod_poly_t A, const fmpz_mod_ctx_t FLINT_UNUSED(ctx));
0808
0809 /*  Radix conversion *********************************************************/
0810
0811 typedef struct {
0812     fmpz *V;
0813     fmpz *W;
0814     fmpz **Rpow;
0815     fmpz **Rinv;
0816     slong degR;
0817     slong k;
0818     fmpz invL;
0819 } fmpz_mod_poly_radix_struct;
0820
0821 typedef fmpz_mod_poly_radix_struct fmpz_mod_poly_radix_t[1];
0822
0823 void _fmpz_mod_poly_radix_init(fmpz **Rpow, fmpz **Rinv,
0824                     const fmpz *R, slong lenR, slong k,
0825                     const fmpz_t invL, const fmpz_mod_ctx_t ctx);
0826
0827 void fmpz_mod_poly_radix_init(fmpz_mod_poly_radix_t D,
0828                 const fmpz_mod_poly_t R, slong degF, const fmpz_mod_ctx_t ctx);
0829
0830 void fmpz_mod_poly_radix_clear(fmpz_mod_poly_radix_t D);
0831
0832 void _fmpz_mod_poly_radix(fmpz **B, const fmpz *F, fmpz **Rpow, fmpz **Rinv,
0833                           slong degR, slong k, slong i, fmpz *W, const fmpz_mod_ctx_t ctx);
0834
0835 void fmpz_mod_poly_radix(fmpz_mod_poly_struct **B, const fmpz_mod_poly_t F,
0836                       const fmpz_mod_poly_radix_t D, const fmpz_mod_ctx_t ctx);
0837
0838 /*  Input and output *********************************************************/
0839
0840 char * fmpz_mod_poly_get_str(const fmpz_mod_poly_t poly, const fmpz_mod_ctx_t FLINT_UNUSED(ctx));
0841 char * fmpz_mod_poly_get_str_pretty(const fmpz_mod_poly_t poly, const char * x, const fmpz_mod_ctx_t FLINT_UNUSED(ctx));
0842
0843 #ifdef FLINT_HAVE_FILE
0844 int _fmpz_mod_poly_fprint(FILE * file, const fmpz *poly, slong len, const fmpz_t p);
0845 int fmpz_mod_poly_fprint(FILE * file, const fmpz_mod_poly_t poly, const fmpz_mod_ctx_t ctx);
0846 int fmpz_mod_poly_fprint_pretty(FILE * file, const fmpz_mod_poly_t poly, const char * x, const fmpz_mod_ctx_t FLINT_UNUSED(ctx));
0847
0848 int fmpz_mod_poly_fread(FILE * file, fmpz_mod_poly_t poly, fmpz_mod_ctx_t ctx);
0849 #endif
0850
0851 int _fmpz_mod_poly_print(const fmpz *poly, slong len, const fmpz_t p);
0852 int fmpz_mod_poly_print(const fmpz_mod_poly_t poly, const fmpz_mod_ctx_t ctx);
0853 int fmpz_mod_poly_print_pretty(const fmpz_mod_poly_t poly, const char * x, const fmpz_mod_ctx_t ctx);
0854
0855 /* Products *****************************************************************/
0856
0857 void _fmpz_mod_poly_product_roots_fmpz_vec(fmpz * poly,
0858                                    const fmpz * xs, slong n, const fmpz_mod_ctx_t ctx);
0859
0860 void fmpz_mod_poly_product_roots_fmpz_vec(fmpz_mod_poly_t poly,
0861                            const fmpz * xs, slong n, const fmpz_mod_ctx_t ctx);
0862
0863 int fmpz_mod_poly_find_distinct_nonzero_roots(fmpz * roots,
0864                             const fmpz_mod_poly_t P, const fmpz_mod_ctx_t ctx);
0865
0866 void _fmpz_mod_poly_split_rabin(fmpz_mod_poly_t a, fmpz_mod_poly_t b,
0867                const fmpz_mod_poly_t f, const fmpz_t halfp, fmpz_mod_poly_t t,
0868          fmpz_mod_poly_t t2, flint_rand_t randstate, const fmpz_mod_ctx_t ctx);
0869
0870 /* Characteristic polynomial and minimal polynomial */
0871
0872 void _fmpz_mod_mat_charpoly(fmpz * p,
0873                              const fmpz_mod_mat_t M, const fmpz_mod_ctx_t ctx);
0874 void fmpz_mod_mat_charpoly(fmpz_mod_poly_t p,
0875                               const fmpz_mod_mat_t M, const fmpz_mod_ctx_t ctx);
0876
0877 void fmpz_mod_mat_minpoly(fmpz_mod_poly_t p, const fmpz_mod_mat_t M,
0878                                                      const fmpz_mod_ctx_t ctx);
0879
0880 /* Berlekamp-Massey Algorithm - see fmpz_mod_poly/berlekamp_massey.c for more info ********/
0881 typedef struct {
0882     slong npoints;
0883     fmpz_mod_poly_t R0, R1;
0884     fmpz_mod_poly_t V0, V1;
0885     fmpz_mod_poly_t qt, rt;
0886     fmpz_mod_poly_t points;
0887 } fmpz_mod_berlekamp_massey_struct;
0888 typedef fmpz_mod_berlekamp_massey_struct fmpz_mod_berlekamp_massey_t[1];
0889
0890 void fmpz_mod_berlekamp_massey_init(
0891                       fmpz_mod_berlekamp_massey_t B, const fmpz_mod_ctx_t ctx);
0892
0893 void fmpz_mod_berlekamp_massey_start_over(
0894                       fmpz_mod_berlekamp_massey_t B, const fmpz_mod_ctx_t ctx);
0895
0896 void fmpz_mod_berlekamp_massey_clear(fmpz_mod_berlekamp_massey_t B,
0897                                                      const fmpz_mod_ctx_t ctx);
0898
0899 void fmpz_mod_berlekamp_massey_print(
0900                 const fmpz_mod_berlekamp_massey_t B, const fmpz_mod_ctx_t ctx);
0901
0902 void fmpz_mod_berlekamp_massey_add_points(
0903                    fmpz_mod_berlekamp_massey_t B, const fmpz * a, slong count,
0904                                                      const fmpz_mod_ctx_t ctx);
0905
0906 void fmpz_mod_berlekamp_massey_add_zeros(
0907                                    fmpz_mod_berlekamp_massey_t B, slong count,
0908                                                      const fmpz_mod_ctx_t ctx);
0909
0910 void fmpz_mod_berlekamp_massey_add_point(
0911                                 fmpz_mod_berlekamp_massey_t B, const fmpz_t a,
0912                                                      const fmpz_mod_ctx_t ctx);
0913
0914 void fmpz_mod_berlekamp_massey_add_point_ui(
0915                                       fmpz_mod_berlekamp_massey_t B, ulong a,
0916                                                      const fmpz_mod_ctx_t ctx);
0917
0918 int fmpz_mod_berlekamp_massey_reduce(
0919                       fmpz_mod_berlekamp_massey_t B, const fmpz_mod_ctx_t ctx);
0920
0921 FMPZ_MOD_POLY_INLINE const fmpz * fmpz_mod_berlekamp_massey_points(
0922                         const fmpz_mod_berlekamp_massey_t B)
0923 {
0924     return B->points->coeffs;
0925 }
0926
0927 FMPZ_MOD_POLY_INLINE slong fmpz_mod_berlekamp_massey_point_count(
0928                         const fmpz_mod_berlekamp_massey_t B)
0929 {
0930     return B->points->length;
0931 }
0932
0933 FMPZ_MOD_POLY_INLINE const fmpz_mod_poly_struct * fmpz_mod_berlekamp_massey_V_poly(
0934                         const fmpz_mod_berlekamp_massey_t B)
0935 {
0936     return B->V1;
0937 }
0938
0939 FMPZ_MOD_POLY_INLINE const fmpz_mod_poly_struct * fmpz_mod_berlekamp_massey_R_poly(
0940                         const fmpz_mod_berlekamp_massey_t B)
0941 {
0942     return B->R1;
0943 }
0944
0945 /* Inlines *******************************************************************/
0946
0947 void fmpz_mod_poly_add_si(fmpz_mod_poly_t res,
0948                 const fmpz_mod_poly_t poly, slong c, const fmpz_mod_ctx_t ctx);
0949
0950 void fmpz_mod_poly_sub_si(fmpz_mod_poly_t res,
0951                 const fmpz_mod_poly_t poly, slong c, const fmpz_mod_ctx_t ctx);
0952
0953 void fmpz_mod_poly_si_sub(fmpz_mod_poly_t res, slong c,
0954                          const fmpz_mod_poly_t poly, const fmpz_mod_ctx_t ctx);
0955
0956 void fmpz_mod_poly_add_fmpz(fmpz_mod_poly_t res,
0957          const fmpz_mod_poly_t poly, const fmpz_t c, const fmpz_mod_ctx_t ctx);
0958
0959 void fmpz_mod_poly_sub_fmpz(fmpz_mod_poly_t res,
0960          const fmpz_mod_poly_t poly, const fmpz_t c, const fmpz_mod_ctx_t ctx);
0961
0962 void fmpz_mod_poly_fmpz_sub(fmpz_mod_poly_t res, const fmpz_t c,
0963                          const fmpz_mod_poly_t poly, const fmpz_mod_ctx_t ctx);
0964
0965 /* Declare dead functions *******************************************************************/
0966
0967 #define fmpz_mod_poly_set_coeff_mpz _Pragma("GCC error \"'fmpz_mod_poly_set_coeff_mpz' is deprecated. Use 'fmpz_mod_poly_set_coeff_fmpz' instead.\"")
0968 #define fmpz_mod_poly_get_coeff_mpz _Pragma("GCC error \"'fmpz_mod_poly_get_coeff_mpz' is deprecated. Use 'fmpz_mod_poly_get_coeff_fmpz' instead.\"")
0969
0970 #ifdef __cplusplus
0971 }
0972 #endif
0973
0974 #endif