include/flint/nmod_mpoly.h

0001 /*
0002     Copyright (C) 2017 - 2020 Daniel Schultz
0003
0004     This file is part of FLINT.
0005
0006     FLINT is free software: you can redistribute it and/or modify it under
0007     the terms of the GNU Lesser General Public License (LGPL) as published
0008     by the Free Software Foundation; either version 3 of the License, or
0009     (at your option) any later version.  See <https://www.gnu.org/licenses/>.
0010 */
0011
0012 #ifndef NMOD_MPOLY_H
0013 #define NMOD_MPOLY_H
0014
0015 #ifdef NMOD_MPOLY_INLINES_C
0016 #define NMOD_MPOLY_INLINE
0017 #else
0018 #define NMOD_MPOLY_INLINE static inline
0019 #endif
0020
0021 #include "nmod_types.h"
0022 #include "mpoly_types.h"
0023
0024 #if FLINT_WANT_ASSERT
0025 # include "n_poly.h"
0026 # include "mpoly.h"
0027 #endif
0028
0029 #ifdef __cplusplus
0030 extern "C" {
0031 #endif
0032
0033 FLINT_FORCE_INLINE
0034 ulong * nmod_mpoly_term_coeff_ref(nmod_mpoly_t A, slong i,
0035                                                     const nmod_mpoly_ctx_t FLINT_UNUSED(ctx))
0036 {
0037     FLINT_ASSERT(i < A->length);
0038     return A->coeffs + i;
0039 }
0040
0041
0042 /* Internal type definitions *************************************************/
0043
0044 FLINT_FORCE_INLINE n_poly_struct *
0045 evil_cast_nmod_poly_to_n_poly(nmod_poly_struct * a)
0046 {
0047     return (n_poly_struct *) a;
0048 }
0049
0050 FLINT_FORCE_INLINE const n_poly_struct *
0051 evil_const_cast_nmod_poly_to_n_poly(const nmod_poly_struct * a)
0052 {
0053     return (const n_poly_struct *) a;
0054 }
0055
0056
0057 /*
0058     nmod_mpoly_univar_t
0059     sparse univariates with multivariate coefficients
0060 */
0061 typedef struct
0062 {
0063    nmod_mpoly_struct * coeffs; /* multivariate coefficients */
0064    fmpz * exps;
0065    slong alloc;
0066    slong length;
0067 } nmod_mpoly_univar_struct;
0068
0069 typedef nmod_mpoly_univar_struct nmod_mpoly_univar_t[1];
0070
0071 /*
0072     nmod_mpolyu_t
0073     sparse univariates with nmod_mpoly_t coefficients
0074         with uniform bits and LEX ordering
0075 */
0076 typedef struct
0077 {
0078    nmod_mpoly_struct * coeffs;
0079    ulong * exps;
0080    slong alloc;
0081    slong length;
0082    flint_bitcnt_t bits;    /* default bits to construct coeffs */
0083 } nmod_mpolyu_struct;
0084 typedef nmod_mpolyu_struct nmod_mpolyu_t[1];
0085
0086 /*
0087     nmod_mpolyd_t
0088     A dense mpoly is stored as a flat array of coefficients.
0089     Suppose deg_bounds = {r0, r1, r2}. The coefficient of the monomial with
0090     exponents {e0, e1, e2} is stored at the coefficient of index
0091         e2 + r2*(e1 + r1*(e0 + r0*0))
0092 */
0093 typedef struct
0094 {
0095     slong nvars;
0096     slong degb_alloc;
0097     slong * deg_bounds;
0098     slong coeff_alloc;
0099     ulong * coeffs;
0100 } nmod_mpolyd_struct;
0101
0102 typedef nmod_mpolyd_struct nmod_mpolyd_t[1];
0103
0104 /* stack type used in gcd which are generally useful as well *****************/
0105
0106 typedef struct
0107 {
0108     n_poly_struct ** poly_array;
0109     slong poly_alloc;
0110     slong poly_top;
0111     nmod_mpolyun_struct ** mpolyun_array;
0112     slong mpolyun_alloc;
0113     slong mpolyun_top;
0114     nmod_mpolyn_struct ** mpolyn_array;
0115     slong mpolyn_alloc;
0116     slong mpolyn_top;
0117     const nmod_mpoly_ctx_struct * ctx;
0118     flint_bitcnt_t bits;
0119 } nmod_poly_stack_struct;
0120
0121 typedef nmod_poly_stack_struct nmod_poly_stack_t[1];
0122
0123 void nmod_poly_stack_init(nmod_poly_stack_t S, flint_bitcnt_t bits, const nmod_mpoly_ctx_t ctx);
0124 void nmod_poly_stack_clear(nmod_poly_stack_t S);
0125
0126 void nmod_poly_stack_set_ctx(nmod_poly_stack_t S, const nmod_mpoly_ctx_t ctx);
0127
0128 n_poly_struct ** nmod_poly_stack_fit_request_poly(nmod_poly_stack_t S, slong k);
0129
0130 nmod_mpolyun_struct ** nmod_poly_stack_fit_request_mpolyun(nmod_poly_stack_t S, slong k);
0131
0132 nmod_mpolyn_struct ** nmod_poly_stack_fit_request_mpolyn(nmod_poly_stack_t S, slong k);
0133
0134 FLINT_FORCE_INLINE
0135 n_poly_struct ** nmod_poly_stack_request_poly(nmod_poly_stack_t S, slong k)
0136 {
0137     n_poly_struct ** poly_top;
0138     poly_top = nmod_poly_stack_fit_request_poly(S, k);
0139     S->poly_top += k;
0140     return poly_top;
0141 }
0142
0143 FLINT_FORCE_INLINE
0144 n_poly_struct * nmod_poly_stack_take_top_poly(nmod_poly_stack_t S)
0145 {
0146     /* assume the request for 1 has already been fitted */
0147     n_poly_struct ** poly_top;
0148     FLINT_ASSERT(S->poly_top + 1 <= S->poly_alloc);
0149     poly_top = S->poly_array + S->poly_top;
0150     S->poly_top += 1;
0151     return poly_top[0];
0152 }
0153
0154 FLINT_FORCE_INLINE
0155 void nmod_poly_stack_give_back_poly(nmod_poly_stack_t S, slong k)
0156 {
0157     FLINT_ASSERT(S->poly_top >= k);
0158     S->poly_top -= k;
0159 }
0160
0161 FLINT_FORCE_INLINE
0162 slong nmod_poly_stack_size_poly(const nmod_poly_stack_t S)
0163 {
0164     return S->poly_top;
0165 }
0166
0167
0168 FLINT_FORCE_INLINE
0169 nmod_mpolyun_struct ** nmod_poly_stack_request_mpolyun(nmod_poly_stack_t S, slong k)
0170 {
0171     nmod_mpolyun_struct ** mpolyun_top;
0172     mpolyun_top = nmod_poly_stack_fit_request_mpolyun(S, k);
0173     S->mpolyun_top += k;
0174     return mpolyun_top;
0175 }
0176
0177 FLINT_FORCE_INLINE
0178 nmod_mpolyun_struct * nmod_poly_stack_take_top_mpolyun(nmod_poly_stack_t S)
0179 {
0180     /* assume the request for 1 has already been fitted */
0181     nmod_mpolyun_struct ** mpolyun_top;
0182     FLINT_ASSERT(S->mpolyun_top + 1 <= S->mpolyun_alloc);
0183     mpolyun_top = S->mpolyun_array + S->mpolyun_top;
0184     S->mpolyun_top += 1;
0185     return mpolyun_top[0];
0186 }
0187
0188 FLINT_FORCE_INLINE
0189 void nmod_poly_stack_give_back_mpolyun(nmod_poly_stack_t S, slong k)
0190 {
0191     FLINT_ASSERT(S->mpolyun_top >= k);
0192     S->mpolyun_top -= k;
0193 }
0194
0195 FLINT_FORCE_INLINE
0196 slong nmod_poly_stack_size_mpolyun(const nmod_poly_stack_t S)
0197 {
0198     return S->mpolyun_top;
0199 }
0200
0201 FLINT_FORCE_INLINE
0202 nmod_mpolyn_struct ** nmod_poly_stack_request_mpolyn(nmod_poly_stack_t S, slong k)
0203 {
0204     nmod_mpolyn_struct ** mpolyn_top;
0205     mpolyn_top = nmod_poly_stack_fit_request_mpolyn(S, k);
0206     S->mpolyn_top += k;
0207     return mpolyn_top;
0208 }
0209
0210 FLINT_FORCE_INLINE
0211 nmod_mpolyn_struct * nmod_poly_stack_take_top_mpolyn(nmod_poly_stack_t S)
0212 {
0213     /* assume the request for 1 has already been fitted */
0214     nmod_mpolyn_struct ** mpolyn_top;
0215     FLINT_ASSERT(S->mpolyn_top + 1 <= S->mpolyn_alloc);
0216     mpolyn_top = S->mpolyn_array + S->mpolyn_top;
0217     S->mpolyn_top += 1;
0218     return mpolyn_top[0];
0219 }
0220
0221 FLINT_FORCE_INLINE
0222 void nmod_poly_stack_give_back_mpolyn(nmod_poly_stack_t S, slong k)
0223 {
0224     FLINT_ASSERT(S->mpolyn_top >= k);
0225     S->mpolyn_top -= k;
0226 }
0227
0228 FLINT_FORCE_INLINE
0229 slong nmod_poly_stack_size_mpolyn(const nmod_poly_stack_t S)
0230 {
0231     return S->mpolyn_top;
0232 }
0233
0234 /* Context object ************************************************************/
0235
0236 void nmod_mpoly_ctx_init(nmod_mpoly_ctx_t ctx, slong nvars, const ordering_t ord, ulong modulus);
0237
0238 void nmod_mpoly_ctx_init_rand(nmod_mpoly_ctx_t ctx, flint_rand_t state, slong max_nvars, ulong modulus);
0239
0240 void nmod_mpoly_ctx_clear(nmod_mpoly_ctx_t ctx);
0241
0242 void nmod_mpoly_ctx_set_modulus(nmod_mpoly_ctx_t ctx, ulong modulus);
0243
0244 NMOD_MPOLY_INLINE
0245 slong nmod_mpoly_ctx_nvars(const nmod_mpoly_ctx_t ctx)
0246 {
0247     return ctx->minfo->nvars;
0248 }
0249
0250 NMOD_MPOLY_INLINE
0251 ordering_t nmod_mpoly_ctx_ord(const nmod_mpoly_ctx_t ctx)
0252 {
0253     return ctx->minfo->ord;
0254 }
0255
0256 NMOD_MPOLY_INLINE
0257 ulong nmod_mpoly_ctx_modulus(const nmod_mpoly_ctx_t ctx)
0258 {
0259     return ctx->mod.n;
0260 }
0261
0262 /*  Memory management ********************************************************/
0263
0264 NMOD_MPOLY_INLINE
0265 void nmod_mpoly_init(nmod_mpoly_t A, const nmod_mpoly_ctx_t FLINT_UNUSED(ctx))
0266 {
0267     A->coeffs = NULL;
0268     A->exps = NULL;
0269     A->length = 0;
0270     A->bits = MPOLY_MIN_BITS;
0271     A->coeffs_alloc = 0;
0272     A->exps_alloc = 0;
0273 }
0274
0275 void nmod_mpoly_init2(nmod_mpoly_t A, slong alloc, const nmod_mpoly_ctx_t ctx);
0276 void nmod_mpoly_init3(nmod_mpoly_t A, slong alloc, flint_bitcnt_t bits, const nmod_mpoly_ctx_t ctx);
0277
0278 void nmod_mpoly_realloc(nmod_mpoly_t A, slong alloc, const nmod_mpoly_ctx_t ctx);
0279
0280 NMOD_MPOLY_INLINE
0281 void nmod_mpoly_clear(nmod_mpoly_t A, const nmod_mpoly_ctx_t FLINT_UNUSED(ctx))
0282 {
0283     if (A->coeffs_alloc > 0)
0284         flint_free(A->coeffs);
0285
0286     if (A->exps_alloc > 0)
0287         flint_free(A->exps);
0288 }
0289
0290 void nmod_mpoly_fit_length(nmod_mpoly_t A, slong length, const nmod_mpoly_ctx_t ctx);
0291
0292 void nmod_mpoly_fit_length_fit_bits(nmod_mpoly_t A, slong len, flint_bitcnt_t bits, const nmod_mpoly_ctx_t ctx);
0293 void nmod_mpoly_fit_length_reset_bits(nmod_mpoly_t A, slong len, flint_bitcnt_t bits, const nmod_mpoly_ctx_t ctx);
0294
0295 NMOD_MPOLY_INLINE
0296 void _nmod_mpoly_fit_length(
0297     ulong ** coeffs,
0298     slong * coeffs_alloc,
0299     ulong ** exps,
0300     slong * exps_alloc,
0301     slong N,
0302     slong length)
0303 {
0304     if (length > *coeffs_alloc)
0305     {
0306         *coeffs_alloc = FLINT_MAX(length, *coeffs_alloc*2);
0307         *coeffs = (ulong *) flint_realloc(*coeffs,
0308                                               *coeffs_alloc*sizeof(ulong));
0309     }
0310
0311     if (N*length > *exps_alloc)
0312     {
0313         *exps_alloc = FLINT_MAX(N*length, *exps_alloc*2);
0314         *exps = (ulong *) flint_realloc(*exps, *exps_alloc*sizeof(ulong));
0315     }
0316 }
0317
0318 NMOD_MPOLY_INLINE
0319 void _nmod_mpoly_set_length(nmod_mpoly_t A, slong newlen, const nmod_mpoly_ctx_t FLINT_UNUSED(ctx))
0320 {
0321     FLINT_ASSERT(newlen <= A->coeffs_alloc);
0322     FLINT_ASSERT(mpoly_words_per_exp(A->bits, ctx->minfo)*newlen <= A->exps_alloc);
0323     A->length = newlen;
0324 }
0325
0326 NMOD_MPOLY_INLINE
0327 void nmod_mpoly_truncate(nmod_mpoly_t A, slong newlen, const nmod_mpoly_ctx_t FLINT_UNUSED(ctx))
0328 {
0329     if (A->length > newlen)
0330     {
0331         A->length = newlen;
0332     }
0333 }
0334
0335 /* Input/output **************************************************************/
0336
0337 int nmod_mpoly_set_str_pretty(nmod_mpoly_t A, const char * str,
0338                                   const char ** x, const nmod_mpoly_ctx_t ctx);
0339
0340 char * nmod_mpoly_get_str_pretty(const nmod_mpoly_t A,
0341                                   const char ** x, const nmod_mpoly_ctx_t ctx);
0342
0343 #ifdef FLINT_HAVE_FILE
0344 int nmod_mpoly_fprint_pretty(FILE * file, const nmod_mpoly_t A, const char ** x, const nmod_mpoly_ctx_t ctx);
0345 #endif
0346
0347 int nmod_mpoly_print_pretty(const nmod_mpoly_t A, const char ** x, const nmod_mpoly_ctx_t ctx);
0348
0349 /*  Basic manipulation *******************************************************/
0350
0351 void nmod_mpoly_gen(nmod_mpoly_t A, slong var, const nmod_mpoly_ctx_t ctx);
0352
0353 int nmod_mpoly_is_gen(const nmod_mpoly_t A, slong var, const nmod_mpoly_ctx_t ctx);
0354
0355 void nmod_mpoly_set(nmod_mpoly_t A, const nmod_mpoly_t B, const nmod_mpoly_ctx_t ctx);
0356
0357 int nmod_mpoly_equal(const nmod_mpoly_t A, const nmod_mpoly_t B, const nmod_mpoly_ctx_t ctx);
0358
0359 NMOD_MPOLY_INLINE
0360 void nmod_mpoly_swap(nmod_mpoly_t A, nmod_mpoly_t B, const nmod_mpoly_ctx_t FLINT_UNUSED(ctx))
0361 {
0362     FLINT_SWAP(nmod_mpoly_struct, *A, *B);
0363 }
0364
0365 /* Constants *****************************************************************/
0366
0367 int nmod_mpoly_is_ui(const nmod_mpoly_t A, const nmod_mpoly_ctx_t ctx);
0368
0369 ulong nmod_mpoly_get_ui(const nmod_mpoly_t A, const nmod_mpoly_ctx_t ctx);
0370
0371 void nmod_mpoly_set_ui(nmod_mpoly_t A, ulong c, const nmod_mpoly_ctx_t ctx);
0372 void nmod_mpoly_set_fmpz(nmod_mpoly_t A, const fmpz_t c, const nmod_mpoly_ctx_t ctx);
0373
0374 NMOD_MPOLY_INLINE
0375 void nmod_mpoly_zero(nmod_mpoly_t A, const nmod_mpoly_ctx_t ctx)
0376 {
0377    _nmod_mpoly_set_length(A, 0, ctx);
0378 }
0379
0380 NMOD_MPOLY_INLINE
0381 void nmod_mpoly_one(nmod_mpoly_t A, const nmod_mpoly_ctx_t ctx)
0382 {
0383     nmod_mpoly_set_ui(A, UWORD(1), ctx);
0384 }
0385
0386 int nmod_mpoly_equal_ui(const nmod_mpoly_t A, ulong c, const nmod_mpoly_ctx_t ctx);
0387
0388 NMOD_MPOLY_INLINE
0389 int nmod_mpoly_is_zero(const nmod_mpoly_t A, const nmod_mpoly_ctx_t FLINT_UNUSED(ctx))
0390 {
0391    return A->length == 0;
0392 }
0393
0394 NMOD_MPOLY_INLINE
0395 int nmod_mpoly_is_one(const nmod_mpoly_t A, const nmod_mpoly_ctx_t ctx)
0396 {
0397    return nmod_mpoly_equal_ui(A, 1, ctx);
0398 }
0399
0400 /* Degrees *******************************************************************/
0401
0402 int nmod_mpoly_degrees_fit_si(const nmod_mpoly_t A, const nmod_mpoly_ctx_t ctx);
0403
0404 void nmod_mpoly_degrees_fmpz(fmpz ** degs, const nmod_mpoly_t A, const nmod_mpoly_ctx_t ctx);
0405 void nmod_mpoly_degrees_si(slong * degs, const nmod_mpoly_t A, const nmod_mpoly_ctx_t ctx);
0406
0407 void nmod_mpoly_degree_fmpz(fmpz_t deg, const nmod_mpoly_t A, slong var, const nmod_mpoly_ctx_t ctx);
0408 slong nmod_mpoly_degree_si(const nmod_mpoly_t A, slong var, const nmod_mpoly_ctx_t ctx);
0409
0410 int nmod_mpoly_total_degree_fits_si(const nmod_mpoly_t A, const nmod_mpoly_ctx_t ctx);
0411
0412 void nmod_mpoly_total_degree_fmpz(fmpz_t td, const nmod_mpoly_t A, const nmod_mpoly_ctx_t ctx);
0413 slong nmod_mpoly_total_degree_si(const nmod_mpoly_t A, const nmod_mpoly_ctx_t ctx);
0414
0415 void nmod_mpoly_used_vars(int * used, const nmod_mpoly_t A, const nmod_mpoly_ctx_t ctx);
0416
0417 /* Coefficients **************************************************************/
0418
0419 ulong nmod_mpoly_get_coeff_ui_monomial(const nmod_mpoly_t A, const nmod_mpoly_t M, const nmod_mpoly_ctx_t ctx);
0420
0421 void nmod_mpoly_set_coeff_ui_monomial(nmod_mpoly_t A, ulong c, const nmod_mpoly_t M, const nmod_mpoly_ctx_t ctx);
0422
0423 ulong nmod_mpoly_get_coeff_ui_ui(const nmod_mpoly_t A, const ulong * exp, const nmod_mpoly_ctx_t ctx);
0424 ulong nmod_mpoly_get_coeff_ui_fmpz(const nmod_mpoly_t A, fmpz * const * exp, const nmod_mpoly_ctx_t ctx);
0425
0426 void _nmod_mpoly_set_coeff_ui_fmpz(nmod_mpoly_t A, ulong c, const fmpz * exp, const nmod_mpoly_ctx_t ctx);
0427 void nmod_mpoly_set_coeff_ui_fmpz(nmod_mpoly_t A, ulong c, fmpz * const * exp, const nmod_mpoly_ctx_t ctx);
0428
0429 void nmod_mpoly_set_coeff_ui_ui(nmod_mpoly_t A, ulong c, const ulong * exp, const nmod_mpoly_ctx_t ctx);
0430
0431 void nmod_mpoly_get_coeff_vars_ui(nmod_mpoly_t C,
0432         const nmod_mpoly_t A, const slong * vars, const ulong * exps,
0433         slong length, const nmod_mpoly_ctx_t ctx);
0434
0435 NMOD_MPOLY_INLINE
0436 ulong nmod_mpoly_leadcoeff(nmod_mpoly_t A, const nmod_mpoly_ctx_t FLINT_UNUSED(ctx))
0437 {
0438     FLINT_ASSERT(A->length > 0);
0439     return A->coeffs[0];
0440 }
0441
0442 /* conversion ****************************************************************/
0443
0444 int nmod_mpoly_is_nmod_poly(const nmod_mpoly_t A, slong var, const nmod_mpoly_ctx_t ctx);
0445
0446 int nmod_mpoly_get_n_poly(n_poly_t A, const nmod_mpoly_t B, slong var, const nmod_mpoly_ctx_t ctx);
0447
0448 int nmod_mpoly_get_nmod_poly(nmod_poly_t A, const nmod_mpoly_t B, slong var, const nmod_mpoly_ctx_t ctx);
0449
0450 void nmod_mpoly_set_n_poly_mod(nmod_mpoly_t A, const n_poly_t B, slong var, const nmod_mpoly_ctx_t ctx);
0451
0452 void _nmod_mpoly_set_nmod_poly(nmod_mpoly_t A, flint_bitcnt_t Abits, const ulong * Bcoeffs, slong Blen, slong var, const nmod_mpoly_ctx_t ctx);
0453 void nmod_mpoly_set_nmod_poly(nmod_mpoly_t A, const nmod_poly_t B, slong var, const nmod_mpoly_ctx_t ctx);
0454
0455 /* comparison ****************************************************************/
0456
0457 int nmod_mpoly_cmp(const nmod_mpoly_t A, const nmod_mpoly_t B, const nmod_mpoly_ctx_t ctx);
0458
0459 /* container operations ******************************************************/
0460
0461 int nmod_mpoly_is_canonical(const nmod_mpoly_t A, const nmod_mpoly_ctx_t ctx);
0462
0463 NMOD_MPOLY_INLINE
0464 slong nmod_mpoly_length(const nmod_mpoly_t A, const nmod_mpoly_ctx_t FLINT_UNUSED(ctx))
0465 {
0466     return A->length;
0467 }
0468
0469 void nmod_mpoly_resize(nmod_mpoly_t A, slong new_length, const nmod_mpoly_ctx_t ctx);
0470
0471 ulong nmod_mpoly_get_term_coeff_ui(const nmod_mpoly_t A, slong i, const nmod_mpoly_ctx_t FLINT_UNUSED(ctx));
0472
0473 void nmod_mpoly_set_term_coeff_ui(nmod_mpoly_t A, slong i, ulong c, const nmod_mpoly_ctx_t ctx);
0474
0475 int nmod_mpoly_term_exp_fits_ui(const nmod_mpoly_t A, slong i, const nmod_mpoly_ctx_t ctx);
0476 int nmod_mpoly_term_exp_fits_si(const nmod_mpoly_t A, slong i, const nmod_mpoly_ctx_t ctx);
0477
0478 void nmod_mpoly_get_term_exp_si(slong * exp, const nmod_mpoly_t A, slong i, const nmod_mpoly_ctx_t ctx);
0479 void nmod_mpoly_get_term_exp_ui(ulong * exp, const nmod_mpoly_t A, slong i, const nmod_mpoly_ctx_t ctx);
0480 void nmod_mpoly_get_term_exp_fmpz(fmpz ** exp, const nmod_mpoly_t A, slong i, const nmod_mpoly_ctx_t ctx);
0481
0482 slong nmod_mpoly_get_term_var_exp_si(const nmod_mpoly_t A, slong i, slong var, const nmod_mpoly_ctx_t ctx);
0483 ulong nmod_mpoly_get_term_var_exp_ui(const nmod_mpoly_t A, slong i, slong var, const nmod_mpoly_ctx_t ctx);
0484
0485 void nmod_mpoly_set_term_exp_ui(nmod_mpoly_t A, slong i, const ulong * exp, const nmod_mpoly_ctx_t ctx);
0486 void nmod_mpoly_set_term_exp_fmpz(nmod_mpoly_t A, slong i, fmpz * const * exp, const nmod_mpoly_ctx_t ctx);
0487
0488 void nmod_mpoly_get_term(nmod_mpoly_t M, const nmod_mpoly_t A, slong i, const nmod_mpoly_ctx_t ctx);
0489
0490 void nmod_mpoly_get_term_monomial(nmod_mpoly_t M, const nmod_mpoly_t A, slong i, const nmod_mpoly_ctx_t ctx);
0491
0492 void nmod_mpoly_push_term_ui_ui(nmod_mpoly_t A, ulong c, const ulong * exp, const nmod_mpoly_ctx_t ctx);
0493 void nmod_mpoly_push_term_ui_fmpz(nmod_mpoly_t A, ulong c, fmpz * const * exp, const nmod_mpoly_ctx_t ctx);
0494 void nmod_mpoly_push_term_ui_ffmpz(nmod_mpoly_t A, ulong c, const fmpz * exp, const nmod_mpoly_ctx_t ctx);
0495
0496 void nmod_mpoly_sort_terms(nmod_mpoly_t A, const nmod_mpoly_ctx_t ctx);
0497
0498 void nmod_mpoly_combine_like_terms(nmod_mpoly_t A, const nmod_mpoly_ctx_t ctx);
0499
0500 void nmod_mpoly_reverse(nmod_mpoly_t A, const nmod_mpoly_t B, const nmod_mpoly_ctx_t ctx);
0501
0502 void nmod_mpoly_assert_canonical(const nmod_mpoly_t A, const nmod_mpoly_ctx_t ctx);
0503
0504 void _nmod_mpoly_radix_sort1(nmod_mpoly_t A, slong left, slong right, flint_bitcnt_t pos, ulong cmpmask, ulong totalmask);
0505 void _nmod_mpoly_radix_sort(nmod_mpoly_t A, slong left, slong right, flint_bitcnt_t pos, slong N, ulong * cmpmask);
0506
0507 void _nmod_mpoly_push_exp_ui(nmod_mpoly_t A, const ulong * exp, const nmod_mpoly_ctx_t ctx);
0508 void _nmod_mpoly_push_exp_ffmpz(nmod_mpoly_t A, const fmpz * exp, const nmod_mpoly_ctx_t ctx);
0509 void _nmod_mpoly_push_exp_pfmpz(nmod_mpoly_t A, fmpz * const * exp, const nmod_mpoly_ctx_t ctx);
0510
0511 /* Random generation *********************************************************/
0512
0513 void nmod_mpoly_randtest_bounds(nmod_mpoly_t A, flint_rand_t state,
0514                  slong length, ulong * exp_bounds, const nmod_mpoly_ctx_t ctx);
0515
0516 void nmod_mpoly_randtest_bound(nmod_mpoly_t A, flint_rand_t state,
0517                     slong length, ulong exp_bound, const nmod_mpoly_ctx_t ctx);
0518
0519 void nmod_mpoly_randtest_bits(nmod_mpoly_t A, flint_rand_t state,
0520                slong length, flint_bitcnt_t exp_bits, const nmod_mpoly_ctx_t ctx);
0521
0522 ulong _nmod_mpoly_get_term_ui_fmpz(const nmod_mpoly_t poly, const fmpz * exp, const nmod_mpoly_ctx_t ctx);
0523 ulong nmod_mpoly_get_term_ui_fmpz(const nmod_mpoly_t poly, fmpz * const * exp, const nmod_mpoly_ctx_t ctx);
0524 ulong nmod_mpoly_get_term_ui_ui(const nmod_mpoly_t poly, const ulong * exp, const nmod_mpoly_ctx_t ctx);
0525
0526 void _nmod_mpoly_max_degrees(ulong * max_degs, const ulong * exps, slong len, slong bits, slong n, int deg, int rev, slong N);
0527 void nmod_mpoly_max_degrees(ulong * max_degs, const nmod_mpoly_t poly, const nmod_mpoly_ctx_t ctx);
0528
0529 void nmod_mpoly_set_nmod(nmod_mpoly_t poly, const nmod_t c, const nmod_mpoly_ctx_t ctx);
0530
0531
0532 ulong nmod_mpoly_get_coeff_ui(nmod_t x, const nmod_mpoly_t poly, slong n, const nmod_mpoly_ctx_t ctx);
0533
0534 void nmod_mpoly_set_coeff_ui(nmod_mpoly_t poly, slong n, ulong x, const nmod_mpoly_ctx_t ctx);
0535
0536 void nmod_mpoly_get_monomial(ulong * exps, const nmod_mpoly_t poly, slong n, const nmod_mpoly_ctx_t ctx);
0537
0538 void nmod_mpoly_set_monomial(nmod_mpoly_t poly, slong n, const ulong * exps, const nmod_mpoly_ctx_t ctx);
0539
0540 /* Addition/Subtraction ******************************************************/
0541
0542 void nmod_mpoly_add_ui(nmod_mpoly_t A, const nmod_mpoly_t B, ulong c, const nmod_mpoly_ctx_t ctx);
0543 void nmod_mpoly_add(nmod_mpoly_t A, const nmod_mpoly_t B, const nmod_mpoly_t C, const nmod_mpoly_ctx_t ctx);
0544
0545 void nmod_mpoly_sub_ui(nmod_mpoly_t A, const nmod_mpoly_t B, ulong c, const nmod_mpoly_ctx_t ctx);
0546 void nmod_mpoly_sub(nmod_mpoly_t A, const nmod_mpoly_t B, const nmod_mpoly_t C, const nmod_mpoly_ctx_t ctx);
0547
0548 slong _nmod_mpoly_add(ulong * coeff1, ulong * exp1, const ulong * coeff2, const ulong * exp2, slong len2, const ulong * coeff3, const ulong * exp3, slong len3, slong N, const ulong * cmpmask, nmod_t fctx);
0549 slong _nmod_mpoly_sub(ulong * coeff1, ulong * exp1, const ulong * coeff2, const ulong * exp2, slong len2, const ulong * coeff3, const ulong * exp3, slong len3, slong N, const ulong * cmpmask, nmod_t fctx);
0550
0551 /* Scalar operations *********************************************************/
0552
0553 void nmod_mpoly_neg(nmod_mpoly_t A, const nmod_mpoly_t B, const nmod_mpoly_ctx_t ctx);
0554
0555 void nmod_mpoly_scalar_mul_ui(nmod_mpoly_t A, const nmod_mpoly_t B, ulong c, const nmod_mpoly_ctx_t ctx);
0556
0557 void nmod_mpoly_make_monic(nmod_mpoly_t A, const nmod_mpoly_t B, const nmod_mpoly_ctx_t ctx);
0558
0559 void nmod_mpoly_scalar_mul_nmod_invertible(nmod_mpoly_t A,
0560         const nmod_mpoly_t B, ulong c, const nmod_mpoly_ctx_t ctx);
0561
0562 void nmod_mpoly_scalar_addmul_ui(nmod_mpoly_t A,
0563         const nmod_mpoly_t B, const nmod_mpoly_t C, ulong d,
0564         const nmod_mpoly_ctx_t ctx);
0565
0566 /* Differention **************************************************************/
0567
0568 void nmod_mpoly_derivative(nmod_mpoly_t A, const nmod_mpoly_t B, slong var, const nmod_mpoly_ctx_t ctx);
0569
0570 /* Evaluation ****************************************************************/
0571
0572 int _ff_poly_pow_ui_is_not_feasible(slong length, ulong e);
0573 int _ff_poly_pow_fmpz_is_not_feasible(slong length, const fmpz_t e);
0574
0575 ulong _nmod_mpoly_eval_all_ui(const ulong * Acoeffs, const ulong * Aexps, slong Alen, flint_bitcnt_t Abits, const ulong * alphas, const mpoly_ctx_t mctx, nmod_t mod);
0576 ulong nmod_mpoly_evaluate_all_ui(const nmod_mpoly_t A, const ulong * vals, const nmod_mpoly_ctx_t ctx);
0577
0578 void nmod_mpoly_evaluate_one_ui(nmod_mpoly_t A, const nmod_mpoly_t B, slong var, ulong val, const nmod_mpoly_ctx_t ctx);
0579
0580 int nmod_mpoly_compose_nmod_poly(nmod_poly_t A, const nmod_mpoly_t B, nmod_poly_struct * const * C, const nmod_mpoly_ctx_t ctx);
0581
0582 void _nmod_mpoly_compose_mat(nmod_mpoly_t A, const nmod_mpoly_t B, const fmpz_mat_t M, const nmod_mpoly_ctx_t ctxB, const nmod_mpoly_ctx_t ctxAC);
0583
0584 int nmod_mpoly_compose_nmod_mpoly_geobucket(nmod_mpoly_t A, const nmod_mpoly_t B, nmod_mpoly_struct * const * C, const nmod_mpoly_ctx_t ctxB, const nmod_mpoly_ctx_t ctxAC);
0585 int nmod_mpoly_compose_nmod_mpoly_horner(nmod_mpoly_t A, const nmod_mpoly_t B, nmod_mpoly_struct * const * C, const nmod_mpoly_ctx_t ctxB, const nmod_mpoly_ctx_t ctxAC);
0586 int nmod_mpoly_compose_nmod_mpoly(nmod_mpoly_t A, const nmod_mpoly_t B, nmod_mpoly_struct * const * C, const nmod_mpoly_ctx_t ctxB, const nmod_mpoly_ctx_t ctxAC);
0587
0588 void nmod_mpoly_compose_nmod_mpoly_gen(nmod_mpoly_t A, const nmod_mpoly_t B, const slong * c, const nmod_mpoly_ctx_t ctxB, const nmod_mpoly_ctx_t ctxAC);
0589
0590 /* Multiplication ************************************************************/
0591
0592 void nmod_mpoly_mul(nmod_mpoly_t A, const nmod_mpoly_t B, const nmod_mpoly_t C, const nmod_mpoly_ctx_t ctx);
0593
0594 void nmod_mpoly_mul_johnson(nmod_mpoly_t A, const nmod_mpoly_t B, const nmod_mpoly_t C, const nmod_mpoly_ctx_t ctx);
0595
0596 void nmod_mpoly_mul_heap_threaded(nmod_mpoly_t A, const nmod_mpoly_t B, const nmod_mpoly_t C, const nmod_mpoly_ctx_t ctx);
0597
0598 int nmod_mpoly_mul_array(nmod_mpoly_t A, const nmod_mpoly_t B, const nmod_mpoly_t C, const nmod_mpoly_ctx_t ctx);
0599 int nmod_mpoly_mul_array_threaded(nmod_mpoly_t A, const nmod_mpoly_t B, const nmod_mpoly_t C, const nmod_mpoly_ctx_t ctx);
0600
0601 int _nmod_mpoly_mul_dense(nmod_mpoly_t P, const nmod_mpoly_t A, fmpz * maxAfields, const nmod_mpoly_t B, fmpz * maxBfields, const nmod_mpoly_ctx_t ctx);
0602 int nmod_mpoly_mul_dense(nmod_mpoly_t A, const nmod_mpoly_t B, const nmod_mpoly_t C, const nmod_mpoly_ctx_t ctx);
0603
0604 slong _nmod_mpoly_mul_johnson(nmod_mpoly_t A, const ulong * coeff2, const ulong * exp2, slong len2, const ulong * coeff3, const ulong * exp3, slong len3, flint_bitcnt_t bits, slong N, const ulong * cmpmask, nmod_t fctx);
0605
0606 void _nmod_mpoly_mul_johnson_maxfields(nmod_mpoly_t A, const nmod_mpoly_t B, fmpz * maxBfields, const nmod_mpoly_t C, fmpz * maxCfields, const nmod_mpoly_ctx_t ctx);
0607
0608 void _nmod_mpoly_mul_heap_threaded_pool_maxfields(nmod_mpoly_t A,
0609         const nmod_mpoly_t B, fmpz * maxBfields,
0610         const nmod_mpoly_t C, fmpz * maxCfields, const nmod_mpoly_ctx_t ctx,
0611         const thread_pool_handle * handles, slong num_handles);
0612
0613 int _nmod_mpoly_mul_array_DEG(nmod_mpoly_t A, const nmod_mpoly_t B, fmpz * maxBfields, const nmod_mpoly_t C, fmpz * maxCfields, const nmod_mpoly_ctx_t ctx);
0614 int _nmod_mpoly_mul_array_LEX(nmod_mpoly_t A, const nmod_mpoly_t B, fmpz * maxBfields, const nmod_mpoly_t C, fmpz * maxCfields, const nmod_mpoly_ctx_t ctx);
0615
0616 int _nmod_mpoly_mul_array_threaded_pool_DEG(nmod_mpoly_t A, const nmod_mpoly_t B, fmpz * maxBfields, const nmod_mpoly_t C, fmpz * maxCfields, const nmod_mpoly_ctx_t ctx, const thread_pool_handle * handles, slong num_handles);
0617 int _nmod_mpoly_mul_array_threaded_pool_LEX(nmod_mpoly_t A, const nmod_mpoly_t B, fmpz * maxBfields, const nmod_mpoly_t C, fmpz * maxCfields, const nmod_mpoly_ctx_t ctx, const thread_pool_handle * handles, slong num_handles);
0618
0619 /* Powering ******************************************************************/
0620
0621 void _nmod_mpoly_pow_rmul(nmod_mpoly_t A, const ulong * Bcoeffs, const ulong * Bexps, slong Blen, ulong k, slong N, const ulong * cmpmask, nmod_t mod, nmod_mpoly_t T);
0622 void nmod_mpoly_pow_rmul(nmod_mpoly_t A, const nmod_mpoly_t B, ulong k, const nmod_mpoly_ctx_t ctx);
0623
0624 int nmod_mpoly_pow_ui(nmod_mpoly_t A, const nmod_mpoly_t B, ulong k, const nmod_mpoly_ctx_t ctx);
0625 int nmod_mpoly_pow_fmpz(nmod_mpoly_t A, const nmod_mpoly_t B, const fmpz_t k, const nmod_mpoly_ctx_t ctx);
0626
0627 /* Division ******************************************************************/
0628
0629 int nmod_mpoly_divides(nmod_mpoly_t Q,
0630        const nmod_mpoly_t A, const nmod_mpoly_t B, const nmod_mpoly_ctx_t ctx);
0631
0632 int _nmod_mpoly_divides_threaded_pool(nmod_mpoly_t Q,
0633        const nmod_mpoly_t A, const nmod_mpoly_t B, const nmod_mpoly_ctx_t ctx,
0634                         const thread_pool_handle * handles, slong num_handles);
0635
0636 int nmod_mpoly_divides_monagan_pearce(nmod_mpoly_t Q,
0637        const nmod_mpoly_t A, const nmod_mpoly_t B, const nmod_mpoly_ctx_t ctx);
0638
0639 #if FLINT_KNOW_STRONG_ORDER
0640 #define nmod_mpoly_divides_heap_threaded nmod_mpoly_divides_heap_threaded
0641 int nmod_mpoly_divides_heap_threaded(nmod_mpoly_t Q,
0642        const nmod_mpoly_t A, const nmod_mpoly_t B, const nmod_mpoly_ctx_t ctx);
0643
0644 #define _nmod_mpoly_divides_heap_threaded_pool _nmod_mpoly_divides_heap_threaded_pool
0645 int _nmod_mpoly_divides_heap_threaded_pool(nmod_mpoly_t Q,
0646        const nmod_mpoly_t A, const nmod_mpoly_t B, const nmod_mpoly_ctx_t ctx,
0647                         const thread_pool_handle * handles, slong num_handles);
0648 #endif
0649
0650 int nmod_mpoly_divides_dense(nmod_mpoly_t Q,
0651        const nmod_mpoly_t A, const nmod_mpoly_t B, const nmod_mpoly_ctx_t ctx);
0652
0653 void nmod_mpoly_div(nmod_mpoly_t Q,
0654        const nmod_mpoly_t A, const nmod_mpoly_t B, const nmod_mpoly_ctx_t ctx);
0655
0656 void nmod_mpoly_divrem(nmod_mpoly_t Q, nmod_mpoly_t R,
0657        const nmod_mpoly_t A, const nmod_mpoly_t B, const nmod_mpoly_ctx_t ctx);
0658
0659 void nmod_mpoly_divrem_ideal(nmod_mpoly_struct ** Q, nmod_mpoly_t R,
0660                 const nmod_mpoly_t A, nmod_mpoly_struct * const * B, slong len,
0661                                                    const nmod_mpoly_ctx_t ctx);
0662
0663 NMOD_MPOLY_INLINE
0664 void nmod_mpoly_divexact(nmod_mpoly_t Q, const nmod_mpoly_t A,
0665                               const nmod_mpoly_t B, const nmod_mpoly_ctx_t ctx)
0666 {
0667     if (nmod_mpoly_divides(Q, A, B, ctx))
0668         return;
0669
0670     flint_throw(FLINT_ERROR, "nmod_mpoly_divexact: nonexact division");
0671 }
0672
0673 int _nmod_mpoly_divides_monagan_pearce(nmod_mpoly_t Q,
0674                     const ulong * coeff2, const ulong * exp2, slong len2,
0675                     const ulong * coeff3, const ulong * exp3, slong len3,
0676                     flint_bitcnt_t bits, slong N, const ulong * cmpmask,
0677                                                                   nmod_t fctx);
0678
0679 void nmod_mpoly_div_monagan_pearce(nmod_mpoly_t Q,
0680                                  const nmod_mpoly_t A, const nmod_mpoly_t B,
0681                                                    const nmod_mpoly_ctx_t ctx);
0682
0683 void nmod_mpoly_divrem_monagan_pearce(nmod_mpoly_t q, nmod_mpoly_t r,
0684                   const nmod_mpoly_t poly2, const nmod_mpoly_t poly3,
0685                                                    const nmod_mpoly_ctx_t ctx);
0686
0687 void
0688 nmod_mpoly_divrem_ideal_monagan_pearce(nmod_mpoly_struct ** Q, nmod_mpoly_t R,
0689     const nmod_mpoly_t A, nmod_mpoly_struct * const * B, slong len,
0690                                                    const nmod_mpoly_ctx_t ctx);
0691
0692 /* Square root ***************************************************************/
0693
0694 int nmod_mpoly_sqrt_heap(nmod_mpoly_t Q, const nmod_mpoly_t A,
0695                                                    const nmod_mpoly_ctx_t ctx);
0696
0697 NMOD_MPOLY_INLINE
0698 int nmod_mpoly_sqrt(nmod_mpoly_t Q, const nmod_mpoly_t A,
0699                                                     const nmod_mpoly_ctx_t ctx)
0700 {
0701     return nmod_mpoly_sqrt_heap(Q, A, ctx);
0702 }
0703
0704 NMOD_MPOLY_INLINE
0705 int nmod_mpoly_is_square(const nmod_mpoly_t A, const nmod_mpoly_ctx_t ctx)
0706 {
0707     int res;
0708     nmod_mpoly_t Q;
0709     nmod_mpoly_init(Q, ctx);
0710     res = nmod_mpoly_sqrt_heap(Q, A, ctx);
0711     nmod_mpoly_clear(Q, ctx);
0712     return res;
0713 }
0714
0715 int nmod_mpoly_quadratic_root(nmod_mpoly_t Q, const nmod_mpoly_t A,
0716                              const nmod_mpoly_t B, const nmod_mpoly_ctx_t ctx);
0717
0718 /* GCD ***********************************************************************/
0719
0720 void nmod_mpoly_term_content(nmod_mpoly_t M, const nmod_mpoly_t A,
0721                                                    const nmod_mpoly_ctx_t ctx);
0722
0723 int nmod_mpoly_content_vars(nmod_mpoly_t g, const nmod_mpoly_t A,
0724                   slong * vars, slong vars_length, const nmod_mpoly_ctx_t ctx);
0725
0726 int nmod_mpoly_gcd(nmod_mpoly_t G, const nmod_mpoly_t A,
0727                              const nmod_mpoly_t B, const nmod_mpoly_ctx_t ctx);
0728
0729 int _nmod_mpoly_gcd_algo_small(
0730     nmod_mpoly_t G,
0731     nmod_mpoly_t Abar, /* could be NULL */
0732     nmod_mpoly_t Bbar, /* could be NULL */
0733     const nmod_mpoly_t A,
0734     const nmod_mpoly_t B,
0735     const nmod_mpoly_ctx_t ctx,
0736     unsigned int algo);
0737
0738 int _nmod_mpoly_gcd_algo(nmod_mpoly_t G, nmod_mpoly_t Abar,
0739                 nmod_mpoly_t Bbar, const nmod_mpoly_t A, const nmod_mpoly_t B,
0740                                 const nmod_mpoly_ctx_t ctx, unsigned int algo);
0741
0742 int nmod_mpoly_gcd_cofactors(nmod_mpoly_t G,
0743                 nmod_mpoly_t Abar, nmod_mpoly_t Bbar, const nmod_mpoly_t A,
0744                              const nmod_mpoly_t B, const nmod_mpoly_ctx_t ctx);
0745
0746 int nmod_mpoly_gcd_brown(nmod_mpoly_t G, const nmod_mpoly_t A,
0747                              const nmod_mpoly_t B, const nmod_mpoly_ctx_t ctx);
0748
0749 int nmod_mpoly_gcd_hensel(nmod_mpoly_t G, const nmod_mpoly_t A,
0750                              const nmod_mpoly_t B, const nmod_mpoly_ctx_t ctx);
0751
0752 int nmod_mpoly_gcd_zippel(nmod_mpoly_t G, const nmod_mpoly_t A,
0753                              const nmod_mpoly_t B, const nmod_mpoly_ctx_t ctx);
0754
0755 int nmod_mpoly_gcd_zippel2(nmod_mpoly_t G, const nmod_mpoly_t A,
0756                              const nmod_mpoly_t B, const nmod_mpoly_ctx_t ctx);
0757
0758 void nmod_mpoly_deflation(fmpz * shift, fmpz * stride,
0759                              const nmod_mpoly_t A, const nmod_mpoly_ctx_t ctx);
0760
0761 void nmod_mpoly_deflate(nmod_mpoly_t A, const nmod_mpoly_t B,
0762           const fmpz * shift, const fmpz * stride, const nmod_mpoly_ctx_t ctx);
0763
0764 void nmod_mpoly_inflate(nmod_mpoly_t A, const nmod_mpoly_t B,
0765           const fmpz * shift, const fmpz * stride, const nmod_mpoly_ctx_t ctx);
0766
0767
0768 /******************************************************************************
0769
0770    Internal functions (guaranteed to change without notice)
0771
0772 ******************************************************************************/
0773
0774 void mpoly_void_ring_init_nmod_mpoly_ctx(mpoly_void_ring_t R,
0775                                                    const nmod_mpoly_ctx_t ctx);
0776
0777 void nmod_mpolyl_lead_coeff(nmod_mpoly_t c, const nmod_mpoly_t A,
0778                                    slong num_vars, const nmod_mpoly_ctx_t ctx);
0779
0780 int nmod_mpolyl_content(nmod_mpoly_t g, const nmod_mpoly_t A,
0781                                    slong num_vars, const nmod_mpoly_ctx_t ctx);
0782
0783 void _nmod_mpoly_to_nmod_poly_deflate(nmod_poly_t A, const nmod_mpoly_t B,
0784                         slong var, const ulong * Bshift, const ulong * Bstride,
0785                                                    const nmod_mpoly_ctx_t ctx);
0786
0787 void _nmod_mpoly_from_nmod_poly_inflate(nmod_mpoly_t A, flint_bitcnt_t Abits,
0788                          const nmod_poly_t B, slong var, const ulong * Ashift,
0789                             const ulong * Astride, const nmod_mpoly_ctx_t ctx);
0790
0791 int nmod_mpoly_repack_bits(nmod_mpoly_t A, const nmod_mpoly_t B,
0792                              flint_bitcnt_t Abits, const nmod_mpoly_ctx_t ctx);
0793
0794 int nmod_mpoly_repack_bits_inplace(nmod_mpoly_t A,
0795                              flint_bitcnt_t Abits, const nmod_mpoly_ctx_t ctx);
0796
0797 typedef struct
0798 {
0799     slong nvars;
0800     slong * perm;
0801 } nmod_mpolyd_ctx_struct;
0802
0803 typedef nmod_mpolyd_ctx_struct nmod_mpolyd_ctx_t[1];
0804
0805
0806 /* data is passed to the threaded mul/div functions via a stripe struct */
0807
0808 typedef struct _nmod_mpoly_stripe_struct
0809 {
0810     char * big_mem;
0811     slong big_mem_alloc;
0812     const nmod_mpoly_ctx_struct * ctx;
0813     slong N;
0814     flint_bitcnt_t bits;
0815     nmod_t mod;
0816     ulong lc_minus_inv;
0817     const ulong * cmpmask;
0818     slong * startidx;
0819     slong * endidx;
0820     ulong * emin;
0821     ulong * emax;
0822     int upperclosed;
0823 } nmod_mpoly_stripe_struct;
0824
0825 typedef nmod_mpoly_stripe_struct nmod_mpoly_stripe_t[1];
0826
0827
0828 /* Univariates ***************************************************************/
0829
0830 void nmod_mpoly_univar_init(nmod_mpoly_univar_t A, const nmod_mpoly_ctx_t ctx);
0831 void nmod_mpoly_univar_clear(nmod_mpoly_univar_t A, const nmod_mpoly_ctx_t ctx);
0832
0833 void nmod_mpoly_univar_fit_length(nmod_mpoly_univar_t A,
0834                                      slong length, const nmod_mpoly_ctx_t ctx);
0835
0836 void nmod_mpoly_univar_print_pretty(const nmod_mpoly_univar_t A,
0837                                   const char ** x, const nmod_mpoly_ctx_t ctx);
0838
0839 void nmod_mpoly_univar_assert_canonical(nmod_mpoly_univar_t A,
0840                                                    const nmod_mpoly_ctx_t ctx);
0841
0842 NMOD_MPOLY_INLINE
0843 void nmod_mpoly_univar_zero(nmod_mpoly_univar_t A, const nmod_mpoly_ctx_t FLINT_UNUSED(ctx))
0844 {
0845     A->length = 0;
0846 }
0847
0848 void nmod_mpoly_univar_set_coeff_ui(nmod_mpoly_univar_t A,
0849                     ulong e, const nmod_mpoly_t c, const nmod_mpoly_ctx_t ctx);
0850
0851 void nmod_mpoly_to_univar(nmod_mpoly_univar_t A,
0852                   const nmod_mpoly_t B, slong var, const nmod_mpoly_ctx_t ctx);
0853
0854 void _nmod_mpoly_from_univar(nmod_mpoly_t A, flint_bitcnt_t Abits,
0855            const nmod_mpoly_univar_t B, slong var, const nmod_mpoly_ctx_t ctx);
0856
0857 void nmod_mpoly_from_univar(nmod_mpoly_t A,
0858            const nmod_mpoly_univar_t B, slong var, const nmod_mpoly_ctx_t ctx);
0859
0860 NMOD_MPOLY_INLINE
0861 void nmod_mpoly_univar_swap(nmod_mpoly_univar_t A, nmod_mpoly_univar_t B, const nmod_mpoly_ctx_t FLINT_UNUSED(ctx))
0862 {
0863     FLINT_SWAP(nmod_mpoly_univar_struct, *A, *B);
0864 }
0865
0866 int nmod_mpoly_univar_degree_fits_si(const nmod_mpoly_univar_t A, const nmod_mpoly_ctx_t ctx);
0867
0868 NMOD_MPOLY_INLINE
0869 slong nmod_mpoly_univar_length(const nmod_mpoly_univar_t A,
0870                                                     const nmod_mpoly_ctx_t FLINT_UNUSED(ctx))
0871 {
0872     return A->length;
0873 }
0874
0875 slong nmod_mpoly_univar_get_term_exp_si(nmod_mpoly_univar_t A, slong i, const nmod_mpoly_ctx_t ctx);
0876
0877 NMOD_MPOLY_INLINE
0878 void nmod_mpoly_univar_get_term_coeff(nmod_mpoly_t c,
0879               const nmod_mpoly_univar_t A, slong i, const nmod_mpoly_ctx_t ctx)
0880 {
0881     FLINT_ASSERT((ulong)i < (ulong)A->length);
0882     nmod_mpoly_set(c, A->coeffs + i, ctx);
0883 }
0884
0885 NMOD_MPOLY_INLINE
0886 void nmod_mpoly_univar_swap_term_coeff(nmod_mpoly_t c,
0887                     nmod_mpoly_univar_t A, slong i, const nmod_mpoly_ctx_t ctx)
0888 {
0889     FLINT_ASSERT((ulong)i < (ulong)A->length);
0890     nmod_mpoly_swap(c, A->coeffs + i, ctx);
0891 }
0892
0893 int nmod_mpoly_univar_pseudo_gcd(nmod_mpoly_univar_t Gx,
0894         const nmod_mpoly_univar_t Ax, const nmod_mpoly_univar_t Bx,
0895                                                const nmod_mpoly_ctx_t ctx);
0896
0897 int nmod_mpoly_univar_resultant(nmod_mpoly_t R,
0898         const nmod_mpoly_univar_t Ax, const nmod_mpoly_univar_t Bx,
0899                                                const nmod_mpoly_ctx_t ctx);
0900
0901 int nmod_mpoly_univar_discriminant(nmod_mpoly_t D,
0902              const nmod_mpoly_univar_t Fx, const nmod_mpoly_ctx_t ctx);
0903
0904 int nmod_mpoly_resultant(nmod_mpoly_t R,
0905                         const nmod_mpoly_t A, const nmod_mpoly_t B,
0906                                     slong var, const nmod_mpoly_ctx_t ctx);
0907
0908 int nmod_mpoly_discriminant(nmod_mpoly_t R,
0909           const nmod_mpoly_t A, slong var, const nmod_mpoly_ctx_t ctx);
0910
0911 /* Helpers for array methods *************************************************/
0912
0913 void _nmod_mpoly_mul_array_chunked_LEX(nmod_mpoly_t P, const nmod_mpoly_t A, const nmod_mpoly_t B, const ulong * mults, const nmod_mpoly_ctx_t ctx);
0914 void _nmod_mpoly_mul_array_chunked_DEG(nmod_mpoly_t P, const nmod_mpoly_t A, const nmod_mpoly_t B, ulong degb, const nmod_mpoly_ctx_t ctx);
0915
0916 void _nmod_mpoly_addmul_array1_ulong1(ulong * poly1, const ulong * poly2, const ulong * exp2, slong len2, const ulong * poly3, const ulong * exp3, slong len3);
0917 void _nmod_mpoly_addmul_array1_ulong2(ulong * poly1, const ulong * poly2, const ulong * exp2, slong len2, const ulong * poly3, const ulong * exp3, slong len3);
0918 void _nmod_mpoly_addmul_array1_ulong3(ulong * poly1, const ulong * poly2, const ulong * exp2, slong len2, const ulong * poly3, const ulong * exp3, slong len3);
0919
0920 slong nmod_mpoly_append_array_sm1_LEX(nmod_mpoly_t P, slong Plen, ulong * coeff_array, const ulong * mults, slong num, slong array_size, slong top, const nmod_mpoly_ctx_t ctx);
0921 slong nmod_mpoly_append_array_sm2_LEX(nmod_mpoly_t P, slong Plen, ulong * coeff_array, const ulong * mults, slong num, slong array_size, slong top, const nmod_mpoly_ctx_t ctx);
0922 slong nmod_mpoly_append_array_sm3_LEX(nmod_mpoly_t P, slong Plen, ulong * coeff_array, const ulong * mults, slong num, slong array_size, slong top, const nmod_mpoly_ctx_t ctx);
0923
0924 slong nmod_mpoly_append_array_sm1_DEGLEX(nmod_mpoly_t P, slong Plen, ulong * coeff_array, slong top, slong nvars, slong degb, const nmod_mpoly_ctx_t ctx);
0925 slong nmod_mpoly_append_array_sm2_DEGLEX(nmod_mpoly_t P, slong Plen, ulong * coeff_array, slong top, slong nvars, slong degb, const nmod_mpoly_ctx_t ctx);
0926 slong nmod_mpoly_append_array_sm3_DEGLEX(nmod_mpoly_t P, slong Plen, ulong * coeff_array, slong top, slong nvars, slong degb, const nmod_mpoly_ctx_t ctx);
0927
0928 slong nmod_mpoly_append_array_sm1_DEGREVLEX(nmod_mpoly_t P, slong Plen, ulong * coeff_array, slong top, slong nvars, slong degb, const nmod_mpoly_ctx_t ctx);
0929 slong nmod_mpoly_append_array_sm2_DEGREVLEX(nmod_mpoly_t P, slong Plen, ulong * coeff_array, slong top, slong nvars, slong degb, const nmod_mpoly_ctx_t ctx);
0930 slong nmod_mpoly_append_array_sm3_DEGREVLEX(nmod_mpoly_t P, slong Plen, ulong * coeff_array, slong top, slong nvars, slong degb, const nmod_mpoly_ctx_t ctx);
0931
0932 /* mpolyd ********************************************************************/
0933
0934 void nmod_mpolyd_ctx_init(nmod_mpolyd_ctx_t dctx, slong nvars);
0935 void nmod_mpolyd_ctx_clear(nmod_mpolyd_ctx_t dctx);
0936
0937 FLINT_FORCE_INLINE void nmod_mpolyd_swap(nmod_mpolyd_t poly1, nmod_mpolyd_t poly2)
0938 {
0939    FLINT_SWAP(nmod_mpolyd_struct, *poly1, *poly2);
0940 }
0941
0942 int nmod_mpolyd_set_degbounds(nmod_mpolyd_t A, slong * bounds);
0943
0944 int nmod_mpolyd_set_degbounds_perm(nmod_mpolyd_t A, const nmod_mpolyd_ctx_t dctx, slong * bounds);
0945
0946 void nmod_mpoly_convert_to_nmod_mpolyd(
0947         nmod_mpolyd_t A, const nmod_mpolyd_ctx_t dctx,
0948         const nmod_mpoly_t B, const nmod_mpoly_ctx_t ctx);
0949
0950 void nmod_mpoly_convert_to_nmod_mpolyd_degbound(
0951         nmod_mpolyd_t A, const nmod_mpolyd_ctx_t dctx,
0952         const nmod_mpoly_t B, const nmod_mpoly_ctx_t ctx);
0953
0954 void nmod_mpoly_convert_from_nmod_mpolyd(
0955         nmod_mpoly_t A, const nmod_mpoly_ctx_t ctx,
0956         const nmod_mpolyd_t B, const nmod_mpolyd_ctx_t dctx);
0957
0958 void nmod_mpolyd_init(nmod_mpolyd_t poly, slong nvars);
0959
0960 void nmod_mpolyd_fit_length(nmod_mpolyd_t poly, slong len);
0961
0962 void nmod_mpolyd_zero(nmod_mpolyd_t poly);
0963
0964 void nmod_mpolyd_set_nvars(nmod_mpolyd_t poly, slong nvars);
0965
0966 void nmod_mpolyd_set(nmod_mpolyd_t A, const nmod_mpolyd_t B);
0967
0968 void nmod_mpolyd_clear(nmod_mpolyd_t poly);
0969
0970 void nmod_mpolyd_print(nmod_mpolyd_t poly);
0971
0972 slong nmod_mpolyd_length(const nmod_mpolyd_t A);
0973
0974
0975 /* mpolyu ********************************************************************/
0976
0977 void nmod_mpolyu_init(nmod_mpolyu_t A, flint_bitcnt_t bits, const nmod_mpoly_ctx_t FLINT_UNUSED(ctx));
0978 void nmod_mpolyu_clear(nmod_mpolyu_t A, const nmod_mpoly_ctx_t uctx);
0979
0980 FLINT_FORCE_INLINE
0981 void nmod_mpolyu_swap(nmod_mpolyu_t A, nmod_mpolyu_t B, const nmod_mpoly_ctx_t FLINT_UNUSED(uctx))
0982 {
0983    FLINT_SWAP(nmod_mpolyu_struct, *A, *B);
0984 }
0985
0986 FLINT_FORCE_INLINE
0987 void nmod_mpolyu_zero(nmod_mpolyu_t A, const nmod_mpoly_ctx_t FLINT_UNUSED(uctx))
0988 {
0989     A->length = 0;
0990 }
0991
0992 int nmod_mpolyu_is_one(nmod_mpolyu_t A, const nmod_mpoly_ctx_t uctx);
0993
0994 void nmod_mpolyu_print_pretty(const nmod_mpolyu_t poly,
0995                                   const char ** x, const nmod_mpoly_ctx_t ctx);
0996
0997 void nmod_mpolyu_fit_length(nmod_mpolyu_t A, slong length,
0998                                                   const nmod_mpoly_ctx_t uctx);
0999
1000 void nmod_mpolyu_one(nmod_mpolyu_t A, const nmod_mpoly_ctx_t uctx);
1001
1002 void nmod_mpolyu_degrees_si(
1003     slong * degs,
1004     const nmod_mpolyu_t A,
1005     const nmod_mpoly_ctx_t ctx);
1006
1007 void nmod_mpolyu_repack_bits_inplace(
1008     nmod_mpolyu_t A,
1009     flint_bitcnt_t bits,
1010     const nmod_mpoly_ctx_t ctx);
1011
1012 nmod_mpoly_struct * _nmod_mpolyu_get_coeff(nmod_mpolyu_t A,
1013                                        ulong pow, const nmod_mpoly_ctx_t uctx);
1014
1015 void nmod_mpolyu_shift_right(nmod_mpolyu_t A, ulong s);
1016 void nmod_mpolyu_shift_left(nmod_mpolyu_t A, ulong s);
1017
1018 int nmod_mpolyu_content_mpoly(nmod_mpoly_t g,
1019                            const nmod_mpolyu_t A, const nmod_mpoly_ctx_t ctx);
1020
1021 void nmod_mpolyu_scalar_mul_nmod(nmod_mpolyu_t A, ulong c,
1022                                                   const nmod_mpoly_ctx_t ctx);
1023
1024 void nmod_mpolyu_set(nmod_mpolyu_t A, const nmod_mpolyu_t B,
1025                                                   const nmod_mpoly_ctx_t uctx);
1026
1027 void nmod_mpolyu_cvtto_poly(nmod_poly_t a, nmod_mpolyu_t A,
1028                                                    const nmod_mpoly_ctx_t FLINT_UNUSED(ctx));
1029
1030 void nmod_mpolyu_cvtfrom_poly(nmod_mpolyu_t A, nmod_poly_t a,
1031                                                    const nmod_mpoly_ctx_t ctx);
1032
1033 void nmod_mpolyu_cvtfrom_poly_notmain(nmod_mpolyu_t A, nmod_poly_t a,
1034                                         slong var, const nmod_mpoly_ctx_t ctx);
1035
1036 void nmod_mpoly_to_mpolyu_perm_deflate_threaded_pool(
1037                 nmod_mpolyu_t A, const nmod_mpoly_ctx_t uctx,
1038                 const nmod_mpoly_t B, const nmod_mpoly_ctx_t ctx,
1039                 const slong * perm, const ulong * shift, const ulong * stride,
1040                        const thread_pool_handle * handles, slong num_handles);
1041
1042 void nmod_mpoly_from_mpolyu_perm_inflate(
1043             nmod_mpoly_t A, flint_bitcnt_t Abits, const nmod_mpoly_ctx_t ctx,
1044                         const nmod_mpolyu_t B, const nmod_mpoly_ctx_t uctx,
1045                 const slong * perm, const ulong * shift, const ulong * stride);
1046
1047 int nmod_mpolyuu_divides(nmod_mpolyu_t Q, const nmod_mpolyu_t A,
1048            const nmod_mpolyu_t B, slong nmainvars, const nmod_mpoly_ctx_t ctx);
1049
1050 void nmod_mpolyu_divexact_mpoly_inplace(nmod_mpolyu_t A,
1051                                    nmod_mpoly_t c, const nmod_mpoly_ctx_t ctx);
1052
1053 void nmod_mpolyu_mul_mpoly(nmod_mpolyu_t A, nmod_mpolyu_t B,
1054                                    nmod_mpoly_t c, const nmod_mpoly_ctx_t ctx);
1055
1056 void nmod_mpolyu_mul_mpoly_inplace(nmod_mpolyu_t A, nmod_mpoly_t c,
1057                                                    const nmod_mpoly_ctx_t ctx);
1058
1059 void nmod_mpolyu_setform(nmod_mpolyu_t A, nmod_mpolyu_t B,
1060                                                    const nmod_mpoly_ctx_t ctx);
1061
1062 int nmod_mpolyu_gcdm_zippel(nmod_mpolyu_t G, nmod_mpolyu_t Abar,
1063                        nmod_mpolyu_t Bbar, nmod_mpolyu_t A, nmod_mpolyu_t B,
1064                                  nmod_mpoly_ctx_t ctx, flint_rand_t randstate);
1065
1066 NMOD_MPOLY_INLINE ulong nmod_mpolyu_leadcoeff(
1067                                    nmod_mpolyu_t A, const nmod_mpoly_ctx_t ctx)
1068 {
1069     FLINT_ASSERT(A->length > 0);
1070     return nmod_mpoly_leadcoeff(A->coeffs + 0, ctx);
1071 }
1072
1073 /* mpolyn ********************************************************************/
1074
1075 void nmod_mpolyn_init(nmod_mpolyn_t A, flint_bitcnt_t bits,
1076                                                    const nmod_mpoly_ctx_t FLINT_UNUSED(ctx));
1077
1078 void nmod_mpolyn_clear(nmod_mpolyn_t A, const nmod_mpoly_ctx_t FLINT_UNUSED(ctx));
1079
1080 void nmod_mpolyn_swap(nmod_mpolyn_t A, nmod_mpolyn_t B);
1081
1082 void nmod_mpolyn_zero(nmod_mpolyn_t A, const nmod_mpoly_ctx_t FLINT_UNUSED(ctx));
1083
1084 int nmod_mpolyn_is_zero(nmod_mpolyn_t A, const nmod_mpoly_ctx_t FLINT_UNUSED(ctx));
1085
1086 void nmod_mpolyn_print_pretty(const nmod_mpolyn_t A, const char ** x_in,
1087                                                    const nmod_mpoly_ctx_t ctx);
1088
1089 void nmod_mpolyn_fit_length(nmod_mpolyn_t A, slong length,
1090                                                    const nmod_mpoly_ctx_t ctx);
1091
1092 void nmod_mpolyn_set_length(nmod_mpolyn_t A, slong newlen,
1093                                                    const nmod_mpoly_ctx_t FLINT_UNUSED(ctx));
1094
1095 void nmod_mpolyn_fit_bits(nmod_mpolyn_t A, slong bits,
1096                                                    const nmod_mpoly_ctx_t ctx);
1097
1098 int nmod_mpolyn_is_canonical(const nmod_mpolyn_t A,
1099                                                    const nmod_mpoly_ctx_t ctx);
1100
1101 void nmod_mpolyn_set(nmod_mpolyn_t A, const nmod_mpolyn_t B,
1102                                                    const nmod_mpoly_ctx_t ctx);
1103
1104 void nmod_mpolyn_set_mpoly(nmod_mpolyn_t A, const nmod_mpoly_t B,
1105                                                    const nmod_mpoly_ctx_t ctx);
1106
1107 void nmod_mpoly_cvtfrom_mpolyn(nmod_mpoly_t A, const nmod_mpolyn_t B,
1108                                         slong var, const nmod_mpoly_ctx_t ctx);
1109
1110 void nmod_mpolyn_mul_poly(nmod_mpolyn_t A, const nmod_mpolyn_t B,
1111                                  const n_poly_t c, const nmod_mpoly_ctx_t ctx);
1112
1113 void nmod_mpoly_cvtto_mpolyn(nmod_mpolyn_t A, const nmod_mpoly_t B,
1114                                         slong var, const nmod_mpoly_ctx_t ctx);
1115
1116 NMOD_MPOLY_INLINE ulong nmod_mpolyn_leadcoeff(nmod_mpolyn_t A,
1117                                                     const nmod_mpoly_ctx_t FLINT_UNUSED(ctx))
1118 {
1119     n_poly_struct * leadpoly;
1120
1121     FLINT_ASSERT(A->length > 0);
1122     FLINT_ASSERT(n_poly_degree(A->coeffs + 0) >= 0);
1123
1124     leadpoly = A->coeffs + 0;
1125     return leadpoly->coeffs[leadpoly->length - 1];
1126 }
1127
1128 NMOD_MPOLY_INLINE n_poly_struct * nmod_mpolyn_leadcoeff_poly(
1129                                    nmod_mpolyn_t A, const nmod_mpoly_ctx_t FLINT_UNUSED(ctx))
1130 {
1131     FLINT_ASSERT(A->length > 0);
1132     return A->coeffs + 0;
1133 }
1134
1135 /* mpolyun *******************************************************************/
1136
1137 void nmod_mpolyun_init(nmod_mpolyun_t A, flint_bitcnt_t bits,
1138                                                    const nmod_mpoly_ctx_t FLINT_UNUSED(ctx));
1139
1140 void nmod_mpolyun_clear(nmod_mpolyun_t A, const nmod_mpoly_ctx_t ctx);
1141
1142 FLINT_FORCE_INLINE
1143 void nmod_mpolyun_swap(nmod_mpolyun_t A, nmod_mpolyun_t B)
1144 {
1145     FLINT_SWAP(nmod_mpolyun_struct, *A, *B);
1146 }
1147
1148 void nmod_mpolyun_zero(nmod_mpolyun_t A, const nmod_mpoly_ctx_t ctx);
1149
1150 void nmod_mpolyun_print_pretty(const nmod_mpolyun_t poly,
1151                                    const char ** x, const nmod_mpoly_ctx_t ctx);
1152
1153 void nmod_mpolyun_fit_length(nmod_mpolyun_t A, slong length,
1154                                                    const nmod_mpoly_ctx_t ctx);
1155
1156 int nmod_mpolyun_is_canonical(const nmod_mpolyun_t A, const nmod_mpoly_ctx_t ctx);
1157
1158 void nmod_mpolyun_shift_right(nmod_mpolyun_t A, ulong s);
1159
1160 void nmod_mpolyun_shift_left(nmod_mpolyun_t A, ulong s);
1161
1162 slong nmod_mpolyn_lastdeg(nmod_mpolyn_t A, const nmod_mpoly_ctx_t FLINT_UNUSED(ctx));
1163
1164 slong nmod_mpolyun_lastdeg(nmod_mpolyun_t A, const nmod_mpoly_ctx_t FLINT_UNUSED(ctx));
1165
1166 void nmod_mpolyun_set(nmod_mpolyun_t A, const nmod_mpolyun_t B, const nmod_mpoly_ctx_t ctx);
1167
1168 void nmod_mpolyn_one(nmod_mpolyn_t A, const nmod_mpoly_ctx_t ctx);
1169
1170 void nmod_mpolyun_one(nmod_mpolyun_t A, const nmod_mpoly_ctx_t ctx);
1171
1172 ulong nmod_mpolyun_leadcoeff_last(nmod_mpolyun_t A, const nmod_mpoly_ctx_t ctx);
1173
1174 void nmod_mpolyn_set_mod(nmod_mpolyn_t FLINT_UNUSED(A), const nmod_t FLINT_UNUSED(mod));
1175
1176 void nmod_mpolyun_set_mod(nmod_mpolyun_t FLINT_UNUSED(A), const nmod_t FLINT_UNUSED(mod));
1177
1178 int nmod_mpolyn_is_nonzero_nmod(const nmod_mpolyn_t A, const nmod_mpoly_ctx_t ctx);
1179
1180 int nmod_mpolyun_is_nonzero_nmod(const nmod_mpolyun_t A, const nmod_mpoly_ctx_t ctx);
1181
1182 void nmod_mpolyn_scalar_mul_nmod(
1183     nmod_mpolyn_t A,
1184     ulong c,
1185     const nmod_mpoly_ctx_t ctx);
1186
1187 void nmod_mpolyun_scalar_mul_nmod(nmod_mpolyun_t A, ulong c,
1188                                                    const nmod_mpoly_ctx_t ctx);
1189
1190 void nmod_mpolyn_mul_last(nmod_mpolyn_t A, n_poly_t b, const nmod_mpoly_ctx_t ctx);
1191
1192 void nmod_mpolyun_mul_last(nmod_mpolyun_t A, n_poly_t b, const nmod_mpoly_ctx_t ctx);
1193
1194 int nmod_mpolyn_equal(
1195     const nmod_mpolyn_t A,
1196     const nmod_mpolyn_t B,
1197     const nmod_mpoly_ctx_t ctx);
1198
1199 int nmod_mpolyun_equal(const nmod_mpolyun_t A,
1200                            const nmod_mpolyun_t B, const nmod_mpoly_ctx_t ctx);
1201
1202 void nmod_mpolyu_cvtto_mpolyun(nmod_mpolyun_t A, const nmod_mpolyu_t B,
1203                                           slong k, const nmod_mpoly_ctx_t ctx);
1204
1205 void nmod_mpolyu_cvtfrom_mpolyun(nmod_mpolyu_t A, const nmod_mpolyun_t B,
1206                                         slong var, const nmod_mpoly_ctx_t ctx);
1207
1208 void nmod_mpolyun_mul_poly(nmod_mpolyun_t A, const nmod_mpolyun_t B,
1209                                  const n_poly_t c, const nmod_mpoly_ctx_t ctx);
1210
1211 void nmod_mpolyn_content_last(n_poly_t a, nmod_mpolyn_t B,
1212                                                    const nmod_mpoly_ctx_t ctx);
1213
1214 void nmod_mpolyun_content_last(n_poly_t a, nmod_mpolyun_t B,
1215                                                    const nmod_mpoly_ctx_t ctx);
1216
1217 void nmod_mpolyn_divexact_last(nmod_mpolyn_t A, n_poly_t b,
1218                                                     const nmod_mpoly_ctx_t ctx);
1219
1220 void nmod_mpolyun_divexact_last(nmod_mpolyun_t A, n_poly_t b,
1221                                                    const nmod_mpoly_ctx_t ctx);
1222
1223 int nmod_mpolyn_divides(nmod_mpolyn_t Q, const nmod_mpolyn_t A,
1224                             const nmod_mpolyn_t B, const nmod_mpoly_ctx_t ctx);
1225
1226 #if FLINT_KNOW_STRONG_ORDER
1227 #define nmod_mpolyn_divides_threaded_pool nmod_mpolyn_divides_threaded_pool
1228 int nmod_mpolyn_divides_threaded_pool(nmod_mpolyn_t Q,
1229     const nmod_mpolyn_t A, const nmod_mpolyn_t B, const nmod_mpoly_ctx_t ctx,
1230                         const thread_pool_handle * handles, slong num_handles);
1231 #endif
1232
1233 int nmod_mpolyun_divides(nmod_mpolyun_t Q, const nmod_mpolyun_t A,
1234         const nmod_mpolyun_t B, const nmod_mpoly_ctx_t ctx);
1235
1236 void nmod_mpoly_to_mpolyun_perm_deflate_threaded_pool(
1237         nmod_mpolyun_t A, const nmod_mpoly_ctx_t uctx,
1238         const nmod_mpoly_t B, const nmod_mpoly_ctx_t ctx,
1239         const slong * perm, const ulong * shift, const ulong * stride,
1240         const thread_pool_handle * handles, slong num_handles);
1241
1242 void nmod_mpoly_to_mpolyn_perm_deflate_threaded_pool(nmod_mpolyn_t A,
1243         const nmod_mpoly_ctx_t nctx, const nmod_mpoly_t B, const nmod_mpoly_ctx_t ctx,
1244         const slong * perm, const ulong * shift, const ulong * stride,
1245         const thread_pool_handle * FLINT_UNUSED(handles), slong FLINT_UNUSED(num_handles));
1246
1247 void nmod_mpoly_from_mpolyun_perm_inflate(nmod_mpoly_t A,
1248         flint_bitcnt_t Abits, const nmod_mpoly_ctx_t ctx, const nmod_mpolyun_t B,
1249         const nmod_mpoly_ctx_t uctx, const slong * perm, const ulong * shift,
1250         const ulong * stride);
1251
1252 void nmod_mpoly_from_mpolyn_perm_inflate(nmod_mpoly_t A,
1253         flint_bitcnt_t Abits, const nmod_mpoly_ctx_t ctx,
1254         const nmod_mpolyn_t B, const nmod_mpoly_ctx_t nctx,
1255         const slong * perm, const ulong * shift, const ulong * stride);
1256
1257 NMOD_MPOLY_INLINE
1258 ulong nmod_mpolyun_leadcoeff(nmod_mpolyun_t A, const nmod_mpoly_ctx_t ctx)
1259 {
1260     FLINT_ASSERT(A->length > 0);
1261     return nmod_mpolyn_leadcoeff(A->coeffs + 0, ctx);
1262 }
1263
1264 NMOD_MPOLY_INLINE n_poly_struct * nmod_mpolyun_leadcoeff_poly(
1265                                   nmod_mpolyun_t A, const nmod_mpoly_ctx_t ctx)
1266 {
1267     FLINT_ASSERT(A->length > 0);
1268     return nmod_mpolyn_leadcoeff_poly(A->coeffs + 0, ctx);
1269 }
1270
1271 /* GCD ***********************************************************************/
1272
1273 int mpoly_gcd_get_use_first(slong rGdeg, slong Adeg, slong Bdeg,
1274                                                                slong gammadeg);
1275
1276 int nmod_mpoly_gcd_get_use_new(slong rGdeg, slong Adeg, slong Bdeg,
1277         slong gammadeg, slong degxAB, slong degyAB, slong numABgamma,
1278         const n_polyun_t G, const n_polyun_t Abar, const n_polyun_t Bbar);
1279
1280 void nmod_mpolyu_setform_mpolyun(nmod_mpolyu_t A, nmod_mpolyun_t B,
1281         const nmod_mpoly_ctx_t ctx);
1282
1283 int nmod_mpolyn_gcd_brown_smprime_bivar(
1284         nmod_mpolyn_t G, nmod_mpolyn_t Abar, nmod_mpolyn_t Bbar,
1285         nmod_mpolyn_t A, nmod_mpolyn_t B, const nmod_mpoly_ctx_t ctx,
1286         nmod_poly_stack_t Sp);
1287
1288 int nmod_mpolyn_gcd_brown_smprime(nmod_mpolyn_t G,
1289         nmod_mpolyn_t Abar, nmod_mpolyn_t Bbar,
1290         nmod_mpolyn_t A, nmod_mpolyn_t B, slong var,
1291         const nmod_mpoly_ctx_t ctx, const mpoly_gcd_info_t Iv,
1292         nmod_poly_stack_t Sp);
1293
1294 int nmod_mpolyn_gcd_brown_smprime_threaded_pool(nmod_mpolyn_t G,
1295         nmod_mpolyn_t Abar, nmod_mpolyn_t Bbar,
1296         nmod_mpolyn_t A, nmod_mpolyn_t B, slong var,
1297         const nmod_mpoly_ctx_t ctx, const mpoly_gcd_info_t Iv,
1298         const thread_pool_handle * handles, slong num_workers);
1299
1300 int nmod_mpolyn_gcd_brown_lgprime(nmod_mpolyn_t G,
1301         nmod_mpolyn_t Abar, nmod_mpolyn_t Bbar,
1302         nmod_mpolyn_t A, nmod_mpolyn_t B, slong var,
1303         const nmod_mpoly_ctx_t ctx);
1304
1305 nmod_gcds_ret_t nmod_mpolyu_gcds_zippel(nmod_mpolyu_t G,
1306         nmod_mpolyu_t A, nmod_mpolyu_t B, nmod_mpolyu_t f,
1307         slong var, const nmod_mpoly_ctx_t ctx,
1308         flint_rand_t randstate, slong * degbound);
1309
1310 int nmod_mpolyu_gcdp_zippel(nmod_mpolyu_t G, nmod_mpolyu_t Abar,
1311         nmod_mpolyu_t Bbar, nmod_mpolyu_t A, nmod_mpolyu_t B, slong var,
1312         const nmod_mpoly_ctx_t ctx, flint_rand_t randstate);
1313
1314 void nmod_mpoly_to_mpolyl_perm_deflate(
1315     nmod_mpoly_t A,
1316     const nmod_mpoly_ctx_t lctx,
1317     const nmod_mpoly_t B,
1318     const nmod_mpoly_ctx_t ctx,
1319     const slong * perm,
1320     const ulong * shift,
1321     const ulong * stride);
1322
1323 void nmod_mpoly_from_mpolyl_perm_inflate(
1324     nmod_mpoly_t A,
1325     flint_bitcnt_t Abits,
1326     const nmod_mpoly_ctx_t ctx,
1327     const nmod_mpoly_t B,
1328     const nmod_mpoly_ctx_t lctx,
1329     const slong * perm,
1330     const ulong * shift,
1331     const ulong * stride);
1332
1333 int nmod_mpolyl_gcd_zippel_smprime(
1334     nmod_mpoly_t rG, const slong * rGdegs, /* guess at rG degrees, could be NULL */
1335     nmod_mpoly_t rAbar,
1336     nmod_mpoly_t rBbar,
1337     const nmod_mpoly_t A, const slong * Adegs,
1338     const nmod_mpoly_t B, const slong * Bdegs,
1339     const nmod_mpoly_t gamma, const slong * gammadegs,
1340     const nmod_mpoly_ctx_t ctx);
1341
1342 int nmod_mpolyl_gcd_zippel_lgprime(
1343     nmod_mpoly_t rG, const slong * rGdegs, /* guess at rG degrees, could be NULL */
1344     nmod_mpoly_t rAbar,
1345     nmod_mpoly_t rBbar,
1346     const nmod_mpoly_t A, const slong * Adegs,
1347     const nmod_mpoly_t B, const slong * Bdegs,
1348     const nmod_mpoly_t gamma, const slong * gammadegs,
1349     const nmod_mpoly_ctx_t ctx);
1350
1351 int nmod_mpolyl_gcd_hensel_smprime(
1352     nmod_mpoly_t G, slong Gdeg,
1353     nmod_mpoly_t Abar,
1354     nmod_mpoly_t Bbar,
1355     const nmod_mpoly_t A,
1356     const nmod_mpoly_t B,
1357     const nmod_mpoly_ctx_t ctx);
1358
1359 int nmod_mpolyl_gcd_hensel_medprime(
1360     nmod_mpoly_t G, slong Gdeg,
1361     nmod_mpoly_t Abar,
1362     nmod_mpoly_t Bbar,
1363     const nmod_mpoly_t smA,
1364     const nmod_mpoly_t smB,
1365     const nmod_mpoly_ctx_t smctx);
1366
1367 void _nmod_mpoly_monomial_evals_cache(n_poly_t E,
1368         const ulong * Aexps, flint_bitcnt_t Abits, slong Alen,
1369         const ulong * betas, slong start, slong stop,
1370         const mpoly_ctx_t mctx, nmod_t mod);
1371
1372 void _nmod_mpoly_monomial_evals2_cache(n_polyun_t E,
1373         const ulong * Aexps, flint_bitcnt_t Abits, slong Alen,
1374         const ulong * betas, slong m, const mpoly_ctx_t ctx, nmod_t mod);
1375
1376 /* interp ********************************************************************/
1377
1378 void _nmod_poly_eval2_pow(ulong * vp, ulong * vm,
1379                                    n_poly_t P, n_poly_t alphapow, nmod_t fctx);
1380
1381 void nmod_mpolyn_interp_reduce_2sm_poly(n_poly_t E,
1382                          n_poly_t F, const nmod_mpolyn_t A, n_poly_t alphapow,
1383                                                    const nmod_mpoly_ctx_t ctx);
1384
1385 void nmod_mpolyn_interp_lift_2sm_poly(slong * lastdeg_,
1386                        nmod_mpolyn_t F, const n_poly_t A, const n_poly_t B,
1387                                   ulong alpha, const nmod_mpoly_ctx_t ctx);
1388
1389 int nmod_mpolyn_interp_crt_2sm_poly(slong * lastdeg_,
1390                      nmod_mpolyn_t F, nmod_mpolyn_t T, const n_poly_t A,
1391                              const n_poly_t B, const n_poly_t modulus,
1392                                n_poly_t alphapow,  const nmod_mpoly_ctx_t ctx);
1393
1394 void nmod_mpolyn_interp_lift_sm_bpoly(nmod_mpolyn_t F,
1395                                       n_bpoly_t A, const nmod_mpoly_ctx_t ctx);
1396
1397 int nmod_mpolyn_interp_crt_sm_bpoly(slong * lastdeg,
1398             nmod_mpolyn_t F, nmod_mpolyn_t T, n_bpoly_t A, n_poly_t modulus,
1399                                 n_poly_t alphapow, const nmod_mpoly_ctx_t ctx);
1400
1401 void nmod_mpolyn_interp_reduce_2sm_mpolyn(nmod_mpolyn_t E,
1402                             nmod_mpolyn_t F, nmod_mpolyn_t A, slong var,
1403                                 n_poly_t alphapow, const nmod_mpoly_ctx_t ctx);
1404
1405 void nmod_mpolyn_interp_lift_2sm_mpolyn(slong * lastdeg,
1406                       nmod_mpolyn_t T, nmod_mpolyn_t A, nmod_mpolyn_t B,
1407                        slong var, ulong alpha, const nmod_mpoly_ctx_t ctx);
1408
1409 int nmod_mpolyn_interp_crt_2sm_mpolyn(slong * lastdeg,
1410                         nmod_mpolyn_t F, nmod_mpolyn_t T, nmod_mpolyn_t A,
1411                         nmod_mpolyn_t B, slong var, n_poly_t modulus,
1412                                n_poly_t alphapow, const nmod_mpoly_ctx_t ctx);
1413
1414 void nmod_mpolyun_interp_reduce_sm_mpolyu(nmod_mpolyu_t B,
1415                nmod_mpolyun_t A, ulong alpha, const nmod_mpoly_ctx_t ctx);
1416
1417 void nmod_mpolyn_interp_lift_sm_mpoly(nmod_mpolyn_t A,
1418                             const nmod_mpoly_t B, const nmod_mpoly_ctx_t ctx);
1419
1420 void nmod_mpolyun_interp_lift_sm_mpolyu(nmod_mpolyun_t A,
1421                            const nmod_mpolyu_t B, const nmod_mpoly_ctx_t ctx);
1422
1423 int nmod_mpolyn_interp_crt_sm_mpoly(slong * lastdeg, nmod_mpolyn_t F,
1424                             nmod_mpolyn_t T, nmod_mpoly_t A, n_poly_t modulus,
1425                                   ulong alpha, const nmod_mpoly_ctx_t ctx);
1426
1427 int nmod_mpolyun_interp_crt_sm_mpolyu(slong * lastdeg,
1428              nmod_mpolyun_t F, nmod_mpolyun_t T, nmod_mpolyu_t A,
1429                 n_poly_t modulus, ulong alpha, const nmod_mpoly_ctx_t ctx);
1430
1431 int nmod_mpolyn_interp_mcrt_sm_mpoly(slong * lastdeg_,
1432                 nmod_mpolyn_t F, const nmod_mpoly_t A, const n_poly_t modulus,
1433                                 n_poly_t alphapow, const nmod_mpoly_ctx_t ctx);
1434
1435 /* geobuckets ****************************************************************/
1436
1437 typedef struct nmod_mpoly_geobucket
1438 {
1439     nmod_mpoly_struct polys[FLINT_BITS/2];
1440     nmod_mpoly_struct temps[FLINT_BITS/2];
1441     slong length;
1442 } nmod_mpoly_geobucket_struct;
1443
1444 typedef nmod_mpoly_geobucket_struct nmod_mpoly_geobucket_t[1];
1445
1446 void nmod_mpoly_geobucket_init(nmod_mpoly_geobucket_t B, const nmod_mpoly_ctx_t ctx);
1447 void nmod_mpoly_geobucket_clear(nmod_mpoly_geobucket_t B, const nmod_mpoly_ctx_t ctx);
1448
1449 void nmod_mpoly_geobucket_empty(nmod_mpoly_t p, nmod_mpoly_geobucket_t B, const nmod_mpoly_ctx_t ctx);
1450
1451 void nmod_mpoly_geobucket_fit_length(nmod_mpoly_geobucket_t B, slong i, const nmod_mpoly_ctx_t ctx);
1452
1453 void nmod_mpoly_geobucket_set(nmod_mpoly_geobucket_t B, nmod_mpoly_t p, const nmod_mpoly_ctx_t ctx);
1454
1455 void nmod_mpoly_geobucket_add(nmod_mpoly_geobucket_t B, nmod_mpoly_t p, const nmod_mpoly_ctx_t ctx);
1456 void nmod_mpoly_geobucket_sub(nmod_mpoly_geobucket_t B, nmod_mpoly_t p, const nmod_mpoly_ctx_t ctx);
1457
1458 /******************************************************************************
1459
1460    Internal consistency checks
1461
1462 ******************************************************************************/
1463
1464 void nmod_mpoly_remainder_strongtest(const nmod_mpoly_t r, const nmod_mpoly_t g, const nmod_mpoly_ctx_t ctx);
1465
1466 #ifdef __cplusplus
1467 }
1468 #endif
1469
1470 #endif