include/flint/fq_nmod_mpoly.h

0001 /*
0002     Copyright (C) 2019 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 FQ_NMOD_MPOLY_H
0013 #define FQ_NMOD_MPOLY_H
0014
0015 #ifdef FQ_NMOD_MPOLY_INLINES_C
0016 #define FQ_NMOD_MPOLY_INLINE
0017 #else
0018 #define FQ_NMOD_MPOLY_INLINE static inline
0019 #endif
0020
0021 #include "fq_nmod_types.h"
0022 #include "mpoly_types.h"
0023
0024 #if FLINT_WANT_ASSERT
0025 # include "fq_nmod.h"
0026 # include "mpoly.h"
0027 #endif
0028
0029 #ifdef __cplusplus
0030  extern "C" {
0031 #endif
0032
0033 /* Internal type definitions *************************************************/
0034
0035 /*
0036     fq_nmod_mpoly_univar_t
0037     sparse univariates with multivariate coefficients
0038 */
0039 typedef struct
0040 {
0041    fq_nmod_mpoly_struct * coeffs; /* multivariate coefficients */
0042    fmpz * exps;
0043    slong alloc;
0044    slong length;
0045 } fq_nmod_mpoly_univar_struct;
0046
0047 typedef fq_nmod_mpoly_univar_struct fq_nmod_mpoly_univar_t[1];
0048
0049 /*
0050     fq_nmod_mpolyu_t
0051     sparse univariates with fq_nmod_mpoly_t coefficients
0052         with uniform bits and LEX ordering
0053 */
0054 typedef struct
0055 {
0056    fq_nmod_mpoly_struct * coeffs;
0057    ulong * exps;
0058    slong alloc;
0059    slong length;
0060    flint_bitcnt_t bits;    /* default bits to construct coeffs */
0061 } fq_nmod_mpolyu_struct;
0062
0063 typedef fq_nmod_mpolyu_struct fq_nmod_mpolyu_t[1];
0064
0065 /*
0066     fq_nmod_mpolyn_t
0067     multivariates with fq_nmod_poly_t coefficients
0068 */
0069 typedef struct
0070 {
0071    n_fq_poly_struct * coeffs;
0072    ulong * exps;
0073    slong alloc;
0074    slong length;
0075    slong bits;
0076 } fq_nmod_mpolyn_struct;
0077 typedef fq_nmod_mpolyn_struct fq_nmod_mpolyn_t[1];
0078
0079 /*
0080     fq_nmod_mpolyun_t
0081     sparse univariates with fq_nmod_mpolyn_t coefficients
0082         with uniform bits and LEX ordering
0083 */
0084 typedef struct
0085 {
0086     fq_nmod_mpolyn_struct * coeffs;
0087     ulong * exps;
0088     slong alloc;
0089     slong length;
0090     flint_bitcnt_t bits;   /* default bits to construct coeffs */
0091 } fq_nmod_mpolyun_struct;
0092
0093 typedef fq_nmod_mpolyun_struct fq_nmod_mpolyun_t[1];
0094
0095 /* Embeddings ****************************************************************/
0096
0097 /* see fq_nmod_mpoly/fq_nmod_embed.c for more info */
0098
0099 typedef struct bad_fq_nmod_embed
0100 {
0101     const fq_nmod_ctx_struct * smctx; /* modulus is f */
0102     fq_nmod_poly_t phi_sm;      /* phi as an element of F_p[theta][x] */
0103     fq_nmod_poly_t h;
0104     n_fq_poly_t h_as_n_fq_poly;
0105     const fq_nmod_ctx_struct * lgctx; /* modulus is g */
0106     fq_nmod_t theta_lg;         /* theta as an element of F_p[phi]/g(phi) */
0107     fq_nmod_t x_lg;             /* x as an element of F_p[phi]/g(phi) */
0108     nmod_mat_t lg_to_sm_mat;
0109     nmod_mat_t sm_to_lg_mat;
0110 } bad_fq_nmod_embed_struct;
0111
0112 typedef bad_fq_nmod_embed_struct bad_fq_nmod_embed_t[1];
0113
0114
0115 void bad_fq_nmod_embed_clear(bad_fq_nmod_embed_t emb);
0116
0117 void bad_fq_nmod_embed_array_init(bad_fq_nmod_embed_struct * emb,
0118                      const fq_nmod_ctx_t bigctx, const fq_nmod_ctx_t smallctx);
0119
0120 void bad_fq_nmod_embed_sm_to_lg(fq_nmod_t out,
0121                        const fq_nmod_poly_t in, const bad_fq_nmod_embed_t emb);
0122
0123 void bad_fq_nmod_embed_lg_to_sm(fq_nmod_poly_t out,
0124                             const fq_nmod_t in, const bad_fq_nmod_embed_t emb);
0125
0126 void bad_n_fq_embed_sm_to_lg(ulong * out_, const n_poly_t in_,
0127                                                 const bad_fq_nmod_embed_t emb);
0128
0129 void bad_fq_nmod_embed_n_fq_sm_to_fq_nmod_lg(fq_nmod_t out,
0130                             const n_poly_t in_, const bad_fq_nmod_embed_t emb);
0131
0132 void bad_n_fq_embed_lg_to_sm(n_poly_t out_, const ulong * in_,
0133                                                 const bad_fq_nmod_embed_t emb);
0134
0135 void bad_fq_nmod_embed_fq_nmod_lg_to_n_fq_sm(n_poly_t out_,
0136                             const fq_nmod_t in, const bad_fq_nmod_embed_t emb);
0137
0138 void bad_n_fq_embed_sm_elem_to_lg(ulong * out,
0139                           const ulong * in, const bad_fq_nmod_embed_t emb);
0140
0141 void bad_fq_nmod_embed_sm_elem_to_lg(fq_nmod_t out,
0142                             const fq_nmod_t in, const bad_fq_nmod_embed_t emb);
0143
0144 typedef struct bad_fq_nmod_mpoly_embed_chooser
0145 {
0146     bad_fq_nmod_embed_struct * embed;
0147     slong m; /* degree of the extension F_q / F_p */
0148     slong n; /* degree of the extension F_q^n / F_q */
0149     slong k; /* index of current in embed */
0150     ulong p;
0151 } bad_fq_nmod_mpoly_embed_chooser_struct;
0152
0153 typedef bad_fq_nmod_mpoly_embed_chooser_struct bad_fq_nmod_mpoly_embed_chooser_t[1];
0154
0155 bad_fq_nmod_embed_struct * bad_fq_nmod_mpoly_embed_chooser_init(
0156     bad_fq_nmod_mpoly_embed_chooser_t embc,
0157     fq_nmod_mpoly_ctx_t ectx,
0158     const fq_nmod_mpoly_ctx_t ctx,
0159     flint_rand_t randstate);
0160
0161 void bad_fq_nmod_mpoly_embed_chooser_clear(
0162     bad_fq_nmod_mpoly_embed_chooser_t embc,
0163     fq_nmod_mpoly_ctx_t ectx,
0164     const fq_nmod_mpoly_ctx_t FLINT_UNUSED(ctx),
0165     flint_rand_t FLINT_UNUSED(randstate));
0166
0167 bad_fq_nmod_embed_struct * bad_fq_nmod_mpoly_embed_chooser_next(
0168     bad_fq_nmod_mpoly_embed_chooser_t embc,
0169     fq_nmod_mpoly_ctx_t ectx,
0170     const fq_nmod_mpoly_ctx_t ctx,
0171     flint_rand_t randstate);
0172
0173
0174 /* Context object ************************************************************/
0175
0176 void fq_nmod_mpoly_ctx_init_deg(fq_nmod_mpoly_ctx_t ctx, slong nvars,
0177                                  const ordering_t ord, ulong p, slong deg);
0178
0179 void fq_nmod_mpoly_ctx_init(fq_nmod_mpoly_ctx_t ctx, slong nvars,
0180                               const ordering_t ord, const fq_nmod_ctx_t fqctx);
0181
0182 void fq_nmod_mpoly_ctx_init_rand(fq_nmod_mpoly_ctx_t ctx,
0183                                        flint_rand_t state, slong max_nvars,
0184                                           flint_bitcnt_t p_bits, slong deg_bound);
0185
0186 void fq_nmod_mpoly_ctx_clear(fq_nmod_mpoly_ctx_t ctx);
0187
0188 FQ_NMOD_MPOLY_INLINE
0189 slong fq_nmod_mpoly_ctx_nvars(const fq_nmod_mpoly_ctx_t ctx)
0190 {
0191     return ctx->minfo->nvars;
0192 }
0193
0194 FQ_NMOD_MPOLY_INLINE
0195 ordering_t fq_nmod_mpoly_ctx_ord(const fq_nmod_mpoly_ctx_t ctx)
0196 {
0197     return ctx->minfo->ord;
0198 }
0199
0200
0201 /*  Memory management ********************************************************/
0202
0203 FQ_NMOD_MPOLY_INLINE
0204 void fq_nmod_mpoly_init(fq_nmod_mpoly_t A, const fq_nmod_mpoly_ctx_t FLINT_UNUSED(ctx))
0205 {
0206     A->coeffs = NULL;
0207     A->exps = NULL;
0208     A->length = 0;
0209     A->bits = MPOLY_MIN_BITS;
0210     A->coeffs_alloc = 0;
0211     A->exps_alloc = 0;
0212 }
0213
0214 FQ_NMOD_MPOLY_INLINE
0215 void fq_nmod_mpoly_clear(fq_nmod_mpoly_t A, const fq_nmod_mpoly_ctx_t FLINT_UNUSED(ctx))
0216 {
0217     if (A->coeffs_alloc > 0)
0218         flint_free(A->coeffs);
0219
0220     if (A->exps_alloc > 0)
0221         flint_free(A->exps);
0222 }
0223
0224 void fq_nmod_mpoly_init2(fq_nmod_mpoly_t A, slong alloc,
0225                                                 const fq_nmod_mpoly_ctx_t ctx);
0226
0227 void fq_nmod_mpoly_init3(fq_nmod_mpoly_t A, slong alloc,
0228                            flint_bitcnt_t bits, const fq_nmod_mpoly_ctx_t ctx);
0229
0230 void fq_nmod_mpoly_realloc(fq_nmod_mpoly_t A,
0231                                    slong alloc, const fq_nmod_mpoly_ctx_t ctx);
0232
0233 void fq_nmod_mpoly_fit_length(fq_nmod_mpoly_t A, slong length,
0234                                                 const fq_nmod_mpoly_ctx_t ctx);
0235
0236 void fq_nmod_mpoly_fit_length_fit_bits(fq_nmod_mpoly_t A,
0237                 slong len, flint_bitcnt_t bits, const fq_nmod_mpoly_ctx_t ctx);
0238
0239 void fq_nmod_mpoly_fit_length_reset_bits(fq_nmod_mpoly_t A,
0240                 slong len, flint_bitcnt_t bits, const fq_nmod_mpoly_ctx_t ctx);
0241
0242 FQ_NMOD_MPOLY_INLINE
0243 void _fq_nmod_mpoly_fit_length(
0244     ulong ** coeffs,
0245     slong * coeffs_alloc,
0246     slong d,
0247     ulong ** exps,
0248     slong * exps_alloc,
0249     slong N,
0250     slong length)
0251 {
0252     if (d*length > *coeffs_alloc)
0253     {
0254         *coeffs_alloc = FLINT_MAX(d*length, *coeffs_alloc*2);
0255         *coeffs = (ulong *) flint_realloc(*coeffs,
0256                                               *coeffs_alloc*sizeof(ulong));
0257     }
0258
0259     if (N*length > *exps_alloc)
0260     {
0261         *exps_alloc = FLINT_MAX(N*length, *exps_alloc*2);
0262         *exps = (ulong *) flint_realloc(*exps, *exps_alloc*sizeof(ulong));
0263     }
0264 }
0265
0266 FQ_NMOD_MPOLY_INLINE
0267 void _fq_nmod_mpoly_set_length(fq_nmod_mpoly_t A, slong newlen,
0268                                                  const fq_nmod_mpoly_ctx_t FLINT_UNUSED(ctx))
0269 {
0270     FLINT_ASSERT(fq_nmod_ctx_degree(ctx->fqctx)*newlen <= A->coeffs_alloc);
0271     FLINT_ASSERT(mpoly_words_per_exp(A->bits, ctx->minfo)*newlen <= A->exps_alloc);
0272     A->length = newlen;
0273 }
0274
0275 FQ_NMOD_MPOLY_INLINE
0276 void fq_nmod_mpoly_truncate(fq_nmod_mpoly_t A, slong newlen,
0277                                                  const fq_nmod_mpoly_ctx_t FLINT_UNUSED(ctx))
0278 {
0279     if (A->length > newlen)
0280     {
0281         A->length = newlen;
0282     }
0283 }
0284
0285
0286 /* Input/output **************************************************************/
0287
0288 int fq_nmod_mpoly_set_str_pretty(fq_nmod_mpoly_t A, const char * str,
0289                                const char ** x, const fq_nmod_mpoly_ctx_t ctx);
0290
0291 char * fq_nmod_mpoly_get_str_pretty(const fq_nmod_mpoly_t A,
0292                                const char ** x, const fq_nmod_mpoly_ctx_t ctx);
0293
0294 #ifdef FLINT_HAVE_FILE
0295 int fq_nmod_mpoly_fprint_pretty(FILE * file, const fq_nmod_mpoly_t A, const char ** x, const fq_nmod_mpoly_ctx_t ctx);
0296 #endif
0297
0298 int fq_nmod_mpoly_print_pretty(const fq_nmod_mpoly_t A, const char ** x, const fq_nmod_mpoly_ctx_t ctx);
0299
0300 /*  Basic manipulation *******************************************************/
0301
0302 void fq_nmod_mpoly_gen(fq_nmod_mpoly_t A, slong var,
0303                                                 const fq_nmod_mpoly_ctx_t ctx);
0304
0305 int fq_nmod_mpoly_is_gen(const fq_nmod_mpoly_t A,
0306                                      slong var, const fq_nmod_mpoly_ctx_t ctx);
0307
0308 void fq_nmod_mpoly_set(fq_nmod_mpoly_t A, const fq_nmod_mpoly_t B,
0309                                                 const fq_nmod_mpoly_ctx_t ctx);
0310
0311 int fq_nmod_mpoly_equal(const fq_nmod_mpoly_t A, const fq_nmod_mpoly_t B,
0312                                                 const fq_nmod_mpoly_ctx_t ctx);
0313
0314 FQ_NMOD_MPOLY_INLINE
0315 void fq_nmod_mpoly_swap(fq_nmod_mpoly_t A, fq_nmod_mpoly_t B,
0316                                                  const fq_nmod_mpoly_ctx_t FLINT_UNUSED(ctx))
0317 {
0318     FLINT_SWAP(fq_nmod_mpoly_struct, *A, *B);
0319 }
0320
0321
0322 /* Constants *****************************************************************/
0323
0324 FQ_NMOD_MPOLY_INLINE
0325 ulong * fq_nmod_mpoly_get_nonzero_n_fq(const fq_nmod_mpoly_t A,
0326                                                  const fq_nmod_mpoly_ctx_t FLINT_UNUSED(ctx))
0327 {
0328     FLINT_ASSERT(A->length == 1);
0329     FLINT_ASSERT(mpoly_monomial_is_zero(A->exps,
0330                                     mpoly_words_per_exp(A->bits, ctx->minfo)));
0331     return A->coeffs;
0332 }
0333
0334 int fq_nmod_mpoly_is_fq_nmod(const fq_nmod_mpoly_t A,
0335                                                 const fq_nmod_mpoly_ctx_t ctx);
0336
0337 void fq_nmod_mpoly_get_fq_nmod(fq_nmod_t c, const fq_nmod_mpoly_t A,
0338                                                 const fq_nmod_mpoly_ctx_t ctx);
0339
0340 void fq_nmod_mpoly_set_fq_nmod(fq_nmod_mpoly_t A,
0341                              const fq_nmod_t c, const fq_nmod_mpoly_ctx_t ctx);
0342
0343 void fq_nmod_mpoly_set_n_fq(fq_nmod_mpoly_t A,
0344                            const ulong * c, const fq_nmod_mpoly_ctx_t ctx);
0345
0346 void fq_nmod_mpoly_set_ui(fq_nmod_mpoly_t A, ulong c,
0347                                                 const fq_nmod_mpoly_ctx_t ctx);
0348
0349 void fq_nmod_mpoly_set_fmpz(fq_nmod_mpoly_t A, const fmpz_t c,
0350                                                 const fq_nmod_mpoly_ctx_t ctx);
0351
0352 void fq_nmod_mpoly_set_fq_nmod_gen(fq_nmod_mpoly_t A,
0353                                                 const fq_nmod_mpoly_ctx_t ctx);
0354
0355 int fq_nmod_mpoly_equal_fq_nmod(const fq_nmod_mpoly_t A,
0356                              const fq_nmod_t c, const fq_nmod_mpoly_ctx_t ctx);
0357
0358 FQ_NMOD_MPOLY_INLINE
0359 void fq_nmod_mpoly_zero(fq_nmod_mpoly_t A, const fq_nmod_mpoly_ctx_t ctx)
0360 {
0361    _fq_nmod_mpoly_set_length(A, 0, ctx);
0362 }
0363
0364 void fq_nmod_mpoly_one(fq_nmod_mpoly_t A,
0365                                                 const fq_nmod_mpoly_ctx_t ctx);
0366
0367 FQ_NMOD_MPOLY_INLINE
0368 int fq_nmod_mpoly_is_zero(const fq_nmod_mpoly_t A, const fq_nmod_mpoly_ctx_t FLINT_UNUSED(ctx))
0369 {
0370    return A->length == 0;
0371 }
0372
0373 int fq_nmod_mpoly_is_one(const fq_nmod_mpoly_t A,
0374                                                 const fq_nmod_mpoly_ctx_t ctx);
0375
0376
0377 /* Degrees *******************************************************************/
0378
0379 int fq_nmod_mpoly_degrees_fit_si(const fq_nmod_mpoly_t A, const fq_nmod_mpoly_ctx_t ctx);
0380
0381 void fq_nmod_mpoly_degrees_fmpz(fmpz ** degs, const fq_nmod_mpoly_t A, const fq_nmod_mpoly_ctx_t ctx);
0382 void fq_nmod_mpoly_degrees_si(slong * degs, const fq_nmod_mpoly_t A, const fq_nmod_mpoly_ctx_t ctx);
0383
0384 void fq_nmod_mpoly_degree_fmpz(fmpz_t deg, const fq_nmod_mpoly_t A, slong var, const fq_nmod_mpoly_ctx_t ctx);
0385 slong fq_nmod_mpoly_degree_si(const fq_nmod_mpoly_t A, slong var, const fq_nmod_mpoly_ctx_t ctx);
0386
0387 int fq_nmod_mpoly_total_degree_fits_si(const fq_nmod_mpoly_t A, const fq_nmod_mpoly_ctx_t ctx);
0388
0389 void fq_nmod_mpoly_total_degree_fmpz(fmpz_t td, const fq_nmod_mpoly_t A, const fq_nmod_mpoly_ctx_t ctx);
0390 slong fq_nmod_mpoly_total_degree_si(const fq_nmod_mpoly_t A, const fq_nmod_mpoly_ctx_t ctx);
0391
0392 void fq_nmod_mpoly_used_vars(int * used, const fq_nmod_mpoly_t A, const fq_nmod_mpoly_ctx_t ctx);
0393
0394 /* Coefficients **************************************************************/
0395
0396 void fq_nmod_mpoly_get_coeff_fq_nmod_monomial(fq_nmod_t c,
0397                           const fq_nmod_mpoly_t A, const fq_nmod_mpoly_t M,
0398                                                 const fq_nmod_mpoly_ctx_t ctx);
0399
0400 void fq_nmod_mpoly_set_coeff_fq_nmod_monomial(fq_nmod_mpoly_t A,
0401                                   const fq_nmod_t c, const fq_nmod_mpoly_t M,
0402                                                 const fq_nmod_mpoly_ctx_t ctx);
0403
0404 void fq_nmod_mpoly_get_coeff_fq_nmod_fmpz(fq_nmod_t c,
0405                              const fq_nmod_mpoly_t A, fmpz * const * exp,
0406                                                 const fq_nmod_mpoly_ctx_t ctx);
0407
0408 void fq_nmod_mpoly_get_coeff_fq_nmod_ui(fq_nmod_t c,
0409                                 const fq_nmod_mpoly_t A, const ulong * exp,
0410                                                const fq_nmod_mpoly_ctx_t ctx);
0411
0412 void _fq_nmod_mpoly_set_coeff_fq_nmod_fmpz(fq_nmod_mpoly_t A,
0413                                        const fq_nmod_t c, const fmpz * exp,
0414                                                 const fq_nmod_mpoly_ctx_t ctx);
0415
0416 void fq_nmod_mpoly_set_coeff_fq_nmod_fmpz(fq_nmod_mpoly_t A,
0417                                      const fq_nmod_t c, fmpz * const * exp,
0418                                                 const fq_nmod_mpoly_ctx_t ctx);
0419
0420 void fq_nmod_mpoly_set_coeff_fq_nmod_ui(fq_nmod_mpoly_t A,
0421                                       const fq_nmod_t c, const ulong * exp,
0422                                                 const fq_nmod_mpoly_ctx_t ctx);
0423
0424 void fq_nmod_mpoly_get_coeff_vars_ui(fq_nmod_mpoly_t C,
0425               const fq_nmod_mpoly_t A, const slong * vars, const ulong * exps,
0426                                   slong length, const fq_nmod_mpoly_ctx_t ctx);
0427
0428 FQ_NMOD_MPOLY_INLINE ulong * _fq_nmod_mpoly_leadcoeff(
0429                         const fq_nmod_mpoly_t A, const fq_nmod_mpoly_ctx_t FLINT_UNUSED(ctx))
0430 {
0431     FLINT_ASSERT(A->length > 0);
0432     return A->coeffs + 0;
0433 }
0434
0435 int fq_nmod_mpoly_is_monic(const fq_nmod_mpoly_t A, const fq_nmod_mpoly_ctx_t ctx);
0436
0437 /* conversion ****************************************************************/
0438
0439 int fq_nmod_mpoly_is_fq_nmod_poly(const fq_nmod_mpoly_t A,
0440                                      slong var, const fq_nmod_mpoly_ctx_t ctx);
0441
0442 int fq_nmod_mpoly_get_fq_nmod_poly(fq_nmod_poly_t A,
0443             const fq_nmod_mpoly_t B, slong var, const fq_nmod_mpoly_ctx_t ctx);
0444
0445 void _fq_nmod_mpoly_set_fq_nmod_poly(fq_nmod_mpoly_t A,
0446                          flint_bitcnt_t Abits, const fq_nmod_struct * Bcoeffs,
0447                          slong Blen, slong var, const fq_nmod_mpoly_ctx_t ctx);
0448
0449 void fq_nmod_mpoly_set_fq_nmod_poly(fq_nmod_mpoly_t A,
0450              const fq_nmod_poly_t B, slong var, const fq_nmod_mpoly_ctx_t ctx);
0451
0452 /* comparison ****************************************************************/
0453
0454 int fq_nmod_mpoly_cmp(const fq_nmod_mpoly_t A, const fq_nmod_mpoly_t B,
0455                                                 const fq_nmod_mpoly_ctx_t ctx);
0456
0457
0458 /* container operations ******************************************************/
0459
0460 int fq_nmod_mpoly_is_canonical(const fq_nmod_mpoly_t A,
0461                                                 const fq_nmod_mpoly_ctx_t ctx);
0462
0463 FQ_NMOD_MPOLY_INLINE
0464 slong fq_nmod_mpoly_length(const fq_nmod_mpoly_t A, const fq_nmod_mpoly_ctx_t FLINT_UNUSED(ctx))
0465 {
0466     return A->length;
0467 }
0468
0469 void fq_nmod_mpoly_resize(fq_nmod_mpoly_t A, slong new_length,
0470                                                 const fq_nmod_mpoly_ctx_t ctx);
0471
0472 void fq_nmod_mpoly_get_term_coeff_fq_nmod(fq_nmod_t c,
0473               const fq_nmod_mpoly_t A, slong i, const fq_nmod_mpoly_ctx_t ctx);
0474
0475 void fq_nmod_mpoly_set_term_coeff_fq_nmod(fq_nmod_mpoly_t A,
0476                     slong i, const fq_nmod_t c, const fq_nmod_mpoly_ctx_t ctx);
0477
0478 int fq_nmod_mpoly_term_exp_fits_ui(const fq_nmod_mpoly_t A, slong i, const fq_nmod_mpoly_ctx_t ctx);
0479 int fq_nmod_mpoly_term_exp_fits_si(const fq_nmod_mpoly_t A, slong i, const fq_nmod_mpoly_ctx_t ctx);
0480
0481 void fq_nmod_mpoly_get_term_exp_fmpz(fmpz ** exp,
0482               const fq_nmod_mpoly_t A, slong i, const fq_nmod_mpoly_ctx_t ctx);
0483
0484 void fq_nmod_mpoly_get_term_exp_ui(ulong * exp,
0485               const fq_nmod_mpoly_t A, slong i, const fq_nmod_mpoly_ctx_t ctx);
0486
0487 void fq_nmod_mpoly_get_term_exp_si(slong * exp,
0488               const fq_nmod_mpoly_t A, slong i, const fq_nmod_mpoly_ctx_t ctx);
0489
0490 ulong fq_nmod_mpoly_get_term_var_exp_ui(const fq_nmod_mpoly_t A,
0491                             slong i, slong var, const fq_nmod_mpoly_ctx_t ctx);
0492
0493 slong fq_nmod_mpoly_get_term_var_exp_si(const fq_nmod_mpoly_t A,
0494                             slong i, slong var, const fq_nmod_mpoly_ctx_t ctx);
0495
0496 void fq_nmod_mpoly_set_term_exp_fmpz(fq_nmod_mpoly_t A,
0497                    slong i, fmpz * const * exp, const fq_nmod_mpoly_ctx_t ctx);
0498
0499 void fq_nmod_mpoly_set_term_exp_ui(fq_nmod_mpoly_t A,
0500                     slong i, const ulong * exp, const fq_nmod_mpoly_ctx_t ctx);
0501
0502 void fq_nmod_mpoly_get_term(fq_nmod_mpoly_t M, const fq_nmod_mpoly_t A,
0503                                        slong i, const fq_nmod_mpoly_ctx_t ctx);
0504
0505 void fq_nmod_mpoly_get_term_monomial(fq_nmod_mpoly_t M,
0506               const fq_nmod_mpoly_t A, slong i, const fq_nmod_mpoly_ctx_t ctx);
0507
0508 void fq_nmod_mpoly_push_term_fq_nmod_fmpz(fq_nmod_mpoly_t A,
0509          const fq_nmod_t c, fmpz * const * exp, const fq_nmod_mpoly_ctx_t ctx);
0510
0511 void fq_nmod_mpoly_push_term_fq_nmod_ffmpz(fq_nmod_mpoly_t A,
0512          const fq_nmod_t c, const fmpz * exp, const fq_nmod_mpoly_ctx_t ctx);
0513
0514 void fq_nmod_mpoly_push_term_fq_nmod_ui(fq_nmod_mpoly_t A,
0515           const fq_nmod_t c, const ulong * exp, const fq_nmod_mpoly_ctx_t ctx);
0516
0517 void fq_nmod_mpoly_sort_terms(fq_nmod_mpoly_t A,
0518                                                 const fq_nmod_mpoly_ctx_t ctx);
0519
0520 void fq_nmod_mpoly_combine_like_terms(fq_nmod_mpoly_t A,
0521                                                 const fq_nmod_mpoly_ctx_t ctx);
0522
0523 void fq_nmod_mpoly_reverse(fq_nmod_mpoly_t A, const fq_nmod_mpoly_t B,
0524                                                 const fq_nmod_mpoly_ctx_t ctx);
0525
0526 void fq_nmod_mpoly_assert_canonical(const fq_nmod_mpoly_t A,
0527                                                 const fq_nmod_mpoly_ctx_t ctx);
0528
0529 void _fq_nmod_mpoly_radix_sort1(fq_nmod_mpoly_t A, slong left,
0530      slong right, flint_bitcnt_t pos, ulong cmpmask, ulong totalmask, slong d);
0531
0532 void _fq_nmod_mpoly_radix_sort(fq_nmod_mpoly_t A, slong left,
0533            slong right, flint_bitcnt_t pos, slong N, ulong * cmpmask, slong d);
0534
0535 void _fq_nmod_mpoly_push_exp_ffmpz(fq_nmod_mpoly_t A,
0536                               const fmpz * exp, const fq_nmod_mpoly_ctx_t ctx);
0537
0538 void _fq_nmod_mpoly_push_exp_pfmpz(fq_nmod_mpoly_t A,
0539                             fmpz * const * exp, const fq_nmod_mpoly_ctx_t ctx);
0540
0541 void _fq_nmod_mpoly_push_exp_ui(fq_nmod_mpoly_t A,
0542                              const ulong * exp, const fq_nmod_mpoly_ctx_t ctx);
0543
0544
0545 /* Random generation *********************************************************/
0546
0547 void fq_nmod_mpoly_randtest_bound(fq_nmod_mpoly_t A, flint_rand_t state,
0548                  slong length, ulong exp_bound, const fq_nmod_mpoly_ctx_t ctx);
0549
0550 void fq_nmod_mpoly_randtest_bounds(fq_nmod_mpoly_t A, flint_rand_t state,
0551               slong length, ulong * exp_bounds, const fq_nmod_mpoly_ctx_t ctx);
0552
0553 void fq_nmod_mpoly_randtest_bits(fq_nmod_mpoly_t A, flint_rand_t state,
0554             slong length, flint_bitcnt_t exp_bits, const fq_nmod_mpoly_ctx_t ctx);
0555
0556
0557 /* Addition/Subtraction ******************************************************/
0558
0559 slong _fq_nmod_mpoly_add(
0560                          ulong * coeff1,       ulong * exp1,
0561                          ulong * coeff2, const ulong * exp2, slong len2,
0562                          ulong * coeff3, const ulong * exp3, slong len3,
0563                    slong N, const ulong * cmpmask, const fq_nmod_ctx_t fqctx);
0564
0565 void fq_nmod_mpoly_add_fq_nmod(fq_nmod_mpoly_t A,
0566                             const fq_nmod_mpoly_t B, const fq_nmod_t c,
0567                                                 const fq_nmod_mpoly_ctx_t ctx);
0568
0569 void fq_nmod_mpoly_add_n_fq(fq_nmod_mpoly_t A,
0570                             const fq_nmod_mpoly_t B, const ulong * c,
0571                                                 const fq_nmod_mpoly_ctx_t ctx);
0572
0573 void fq_nmod_mpoly_sub_fq_nmod(fq_nmod_mpoly_t A,
0574                             const fq_nmod_mpoly_t B, const fq_nmod_t C,
0575                                                 const fq_nmod_mpoly_ctx_t ctx);
0576
0577 void fq_nmod_mpoly_add(fq_nmod_mpoly_t A,
0578                             const fq_nmod_mpoly_t B, const fq_nmod_mpoly_t C,
0579                                                 const fq_nmod_mpoly_ctx_t ctx);
0580
0581 void fq_nmod_mpoly_sub(fq_nmod_mpoly_t A,
0582                             const fq_nmod_mpoly_t B, const fq_nmod_mpoly_t C,
0583                                                 const fq_nmod_mpoly_ctx_t ctx);
0584
0585
0586 /* Scalar operations *********************************************************/
0587
0588 void fq_nmod_mpoly_neg(fq_nmod_mpoly_t A,
0589                        const fq_nmod_mpoly_t B, const fq_nmod_mpoly_ctx_t ctx);
0590
0591 void fq_nmod_mpoly_scalar_mul_fq_nmod(fq_nmod_mpoly_t A,
0592     const fq_nmod_mpoly_t B, const fq_nmod_t c, const fq_nmod_mpoly_ctx_t ctx);
0593
0594 void fq_nmod_mpoly_scalar_mul_n_fq(fq_nmod_mpoly_t A,
0595   const fq_nmod_mpoly_t B, const ulong * c, const fq_nmod_mpoly_ctx_t ctx);
0596
0597 void fq_nmod_mpoly_make_monic(fq_nmod_mpoly_t A,
0598                        const fq_nmod_mpoly_t B, const fq_nmod_mpoly_ctx_t ctx);
0599
0600 void fq_nmod_mpoly_scalar_addmul_fq_nmod(fq_nmod_mpoly_t A,
0601         const fq_nmod_mpoly_t B, const fq_nmod_mpoly_t C, const fq_nmod_t e,
0602                                                 const fq_nmod_mpoly_ctx_t ctx);
0603
0604 /* Differentiation **********************************************************/
0605
0606 void fq_nmod_mpoly_derivative(fq_nmod_mpoly_t A,
0607             const fq_nmod_mpoly_t B, slong var, const fq_nmod_mpoly_ctx_t ctx);
0608
0609
0610 /* Evaluation ****************************************************************/
0611
0612 void fq_nmod_mpoly_evaluate_one_fq_nmod(fq_nmod_mpoly_t A,
0613                     const fq_nmod_mpoly_t B, slong var, const fq_nmod_t val,
0614                                                 const fq_nmod_mpoly_ctx_t ctx);
0615
0616 void _fq_nmod_mpoly_eval_all_fq_nmod(fq_nmod_t ev,
0617                   const ulong * Acoeffs, const ulong * Aexps, slong Alen,
0618                        flint_bitcnt_t Abits, fq_nmod_struct * const * alphas,
0619                             const mpoly_ctx_t mctx, const fq_nmod_ctx_t fqctx);
0620
0621 void fq_nmod_mpoly_evaluate_all_fq_nmod(fq_nmod_t ev, const fq_nmod_mpoly_t A,
0622                  fq_nmod_struct * const * vals, const fq_nmod_mpoly_ctx_t ctx);
0623
0624 int fq_nmod_mpoly_compose_fq_nmod_poly(fq_nmod_poly_t A,
0625                      const fq_nmod_mpoly_t B, fq_nmod_poly_struct * const * C,
0626                                                 const fq_nmod_mpoly_ctx_t ctx);
0627
0628 void _fq_nmod_mpoly_compose_mat(fq_nmod_mpoly_t A,
0629                             const fq_nmod_mpoly_t B, const fmpz_mat_t M,
0630               const fq_nmod_mpoly_ctx_t ctxB, const fq_nmod_mpoly_ctx_t ctxAC);
0631
0632 int fq_nmod_mpoly_compose_fq_nmod_mpoly_geobucket(fq_nmod_mpoly_t A,
0633               const fq_nmod_mpoly_t B, fq_nmod_mpoly_struct * const * C,
0634               const fq_nmod_mpoly_ctx_t ctxB, const fq_nmod_mpoly_ctx_t ctxAC);
0635
0636 int fq_nmod_mpoly_compose_fq_nmod_mpoly_horner(fq_nmod_mpoly_t A,
0637               const fq_nmod_mpoly_t B, fq_nmod_mpoly_struct * const * C,
0638               const fq_nmod_mpoly_ctx_t ctxB, const fq_nmod_mpoly_ctx_t ctxAC);
0639
0640 int fq_nmod_mpoly_compose_fq_nmod_mpoly(fq_nmod_mpoly_t A,
0641               const fq_nmod_mpoly_t B, fq_nmod_mpoly_struct * const * C,
0642               const fq_nmod_mpoly_ctx_t ctxB, const fq_nmod_mpoly_ctx_t ctxAC);
0643
0644 void fq_nmod_mpoly_compose_fq_nmod_mpoly_gen(fq_nmod_mpoly_t A,
0645                              const fq_nmod_mpoly_t B, const slong * c,
0646               const fq_nmod_mpoly_ctx_t ctxB, const fq_nmod_mpoly_ctx_t ctxAC);
0647
0648
0649 /* Multiplication ************************************************************/
0650
0651 void fq_nmod_mpoly_mul(fq_nmod_mpoly_t A, const fq_nmod_mpoly_t B,
0652                        const fq_nmod_mpoly_t C, const fq_nmod_mpoly_ctx_t ctx);
0653
0654 void fq_nmod_mpoly_mul_johnson(fq_nmod_mpoly_t poly1,
0655                     const fq_nmod_mpoly_t poly2, const fq_nmod_mpoly_t poly3,
0656                                                 const fq_nmod_mpoly_ctx_t ctx);
0657
0658 void _fq_nmod_mpoly_mul_johnson(
0659     fq_nmod_mpoly_t A,
0660     const ulong * Bcoeffs,
0661     const ulong * Bexps,
0662     slong Blen,
0663     const ulong * Ccoeffs,
0664     const ulong * Cexps,
0665     slong Clen,
0666     flint_bitcnt_t bits,
0667     slong N,
0668     const ulong * cmpmask,
0669     const fq_nmod_ctx_t ctx);
0670
0671
0672 /* Powering ******************************************************************/
0673
0674 int fq_nmod_mpoly_pow_fmpz(fq_nmod_mpoly_t A, const fq_nmod_mpoly_t B,
0675                                 const fmpz_t k, const fq_nmod_mpoly_ctx_t ctx);
0676
0677 int fq_nmod_mpoly_pow_ui(fq_nmod_mpoly_t A, const fq_nmod_mpoly_t B,
0678                                        ulong k, const fq_nmod_mpoly_ctx_t ctx);
0679
0680
0681 /* Division ******************************************************************/
0682
0683 int fq_nmod_mpoly_divides(fq_nmod_mpoly_t Q,
0684                          const fq_nmod_mpoly_t A, const fq_nmod_mpoly_t B,
0685                                                 const fq_nmod_mpoly_ctx_t ctx);
0686
0687 void fq_nmod_mpoly_div(fq_nmod_mpoly_t Q,
0688                             const fq_nmod_mpoly_t A, const fq_nmod_mpoly_t B,
0689                                                 const fq_nmod_mpoly_ctx_t ctx);
0690
0691 void fq_nmod_mpoly_divrem(fq_nmod_mpoly_t Q, fq_nmod_mpoly_t R,
0692                             const fq_nmod_mpoly_t A, const fq_nmod_mpoly_t B,
0693                                                 const fq_nmod_mpoly_ctx_t ctx);
0694
0695 void fq_nmod_mpoly_divrem_ideal(fq_nmod_mpoly_struct ** Q,
0696                                   fq_nmod_mpoly_t R, const fq_nmod_mpoly_t A,
0697                                   fq_nmod_mpoly_struct * const * B, slong len,
0698                                                 const fq_nmod_mpoly_ctx_t ctx);
0699
0700 FQ_NMOD_MPOLY_INLINE
0701 void fq_nmod_mpoly_divexact(fq_nmod_mpoly_t Q, const fq_nmod_mpoly_t A,
0702                         const fq_nmod_mpoly_t B, const fq_nmod_mpoly_ctx_t ctx)
0703 {
0704     if (fq_nmod_mpoly_divides(Q, A, B, ctx))
0705         return;
0706
0707     flint_throw(FLINT_ERROR, "fq_nmod_mpoly_divexact: nonexact division");
0708 }
0709
0710
0711 int fq_nmod_mpoly_divides_monagan_pearce(fq_nmod_mpoly_t poly1,
0712                   const fq_nmod_mpoly_t poly2, const fq_nmod_mpoly_t poly3,
0713                                                 const fq_nmod_mpoly_ctx_t ctx);
0714
0715 void fq_nmod_mpoly_div_monagan_pearce(fq_nmod_mpoly_t q,
0716                       const fq_nmod_mpoly_t poly2, const fq_nmod_mpoly_t poly3,
0717                                                 const fq_nmod_mpoly_ctx_t ctx);
0718
0719 void fq_nmod_mpoly_divrem_monagan_pearce(fq_nmod_mpoly_t q, fq_nmod_mpoly_t r,
0720                       const fq_nmod_mpoly_t poly2, const fq_nmod_mpoly_t poly3,
0721                                                 const fq_nmod_mpoly_ctx_t ctx);
0722
0723 void fq_nmod_mpoly_divrem_ideal_monagan_pearce(
0724                         fq_nmod_mpoly_struct ** q, fq_nmod_mpoly_t r,
0725             const fq_nmod_mpoly_t poly2, fq_nmod_mpoly_struct * const * poly3,
0726                                       slong len, const fq_nmod_mpoly_ctx_t ctx);
0727
0728 int _fq_nmod_mpoly_divides_monagan_pearce(fq_nmod_mpoly_t A,
0729              const ulong * coeff2, const ulong * exp2, slong len2,
0730              const ulong * coeff3, const ulong * exp3, slong len3,
0731   flint_bitcnt_t bits, slong N, const ulong * cmpmask, const fq_nmod_ctx_t fqctx);
0732
0733
0734 /* Square root ***************************************************************/
0735
0736 int fq_nmod_mpoly_sqrt_heap(fq_nmod_mpoly_t Q,
0737                        const fq_nmod_mpoly_t A, const fq_nmod_mpoly_ctx_t ctx);
0738
0739 FQ_NMOD_MPOLY_INLINE
0740 int fq_nmod_mpoly_sqrt(fq_nmod_mpoly_t Q, const fq_nmod_mpoly_t A,
0741                                                  const fq_nmod_mpoly_ctx_t ctx)
0742 {
0743     return fq_nmod_mpoly_sqrt_heap(Q, A, ctx);
0744 }
0745
0746 FQ_NMOD_MPOLY_INLINE
0747 int fq_nmod_mpoly_is_square(const fq_nmod_mpoly_t A,
0748                                                  const fq_nmod_mpoly_ctx_t ctx)
0749 {
0750     int res;
0751     fq_nmod_mpoly_t Q;
0752     fq_nmod_mpoly_init(Q, ctx);
0753     res = fq_nmod_mpoly_sqrt_heap(Q, A, ctx);
0754     fq_nmod_mpoly_clear(Q, ctx);
0755     return res;
0756 }
0757
0758 int fq_nmod_mpoly_quadratic_root(fq_nmod_mpoly_t Q,
0759                             const fq_nmod_mpoly_t A, const fq_nmod_mpoly_t B,
0760                                                 const fq_nmod_mpoly_ctx_t ctx);
0761
0762 /* GCD ***********************************************************************/
0763
0764 void fq_nmod_mpoly_term_content(fq_nmod_mpoly_t M,
0765                        const fq_nmod_mpoly_t A, const fq_nmod_mpoly_ctx_t ctx);
0766
0767 int fq_nmod_mpoly_content_vars(fq_nmod_mpoly_t g,
0768                      const fq_nmod_mpoly_t A, slong * vars, slong vars_length,
0769                                                 const fq_nmod_mpoly_ctx_t ctx);
0770
0771 int fq_nmod_mpoly_gcd(fq_nmod_mpoly_t G, const fq_nmod_mpoly_t A,
0772                        const fq_nmod_mpoly_t B, const fq_nmod_mpoly_ctx_t ctx);
0773
0774 int _fq_nmod_mpoly_gcd_algo(fq_nmod_mpoly_t G, fq_nmod_mpoly_t Abar,
0775         fq_nmod_mpoly_t Bbar, const fq_nmod_mpoly_t A, const fq_nmod_mpoly_t B,
0776                              const fq_nmod_mpoly_ctx_t ctx, unsigned int algo);
0777
0778 int fq_nmod_mpoly_gcd_cofactors(fq_nmod_mpoly_t G,
0779           fq_nmod_mpoly_t Abar, fq_nmod_mpoly_t Bbar, const fq_nmod_mpoly_t A,
0780                        const fq_nmod_mpoly_t B, const fq_nmod_mpoly_ctx_t ctx);
0781
0782 int fq_nmod_mpoly_gcd_brown(fq_nmod_mpoly_t G, const fq_nmod_mpoly_t A,
0783                        const fq_nmod_mpoly_t B, const fq_nmod_mpoly_ctx_t ctx);
0784
0785 int fq_nmod_mpoly_gcd_hensel(fq_nmod_mpoly_t G, const fq_nmod_mpoly_t A,
0786                        const fq_nmod_mpoly_t B, const fq_nmod_mpoly_ctx_t ctx);
0787
0788 int fq_nmod_mpoly_gcd_zippel(fq_nmod_mpoly_t G, const fq_nmod_mpoly_t A,
0789                        const fq_nmod_mpoly_t B, const fq_nmod_mpoly_ctx_t ctx);
0790
0791 int fq_nmod_mpoly_gcd_zippel2(fq_nmod_mpoly_t G, const fq_nmod_mpoly_t A,
0792                        const fq_nmod_mpoly_t B, const fq_nmod_mpoly_ctx_t ctx);
0793
0794 void fq_nmod_mpoly_deflation(fmpz * shift, fmpz * stride,
0795                        const fq_nmod_mpoly_t A, const fq_nmod_mpoly_ctx_t ctx);
0796
0797 void fq_nmod_mpoly_deflate(fq_nmod_mpoly_t A, const fq_nmod_mpoly_t B,
0798           const fmpz * shift, const fmpz * stride, const fq_nmod_mpoly_ctx_t ctx);
0799
0800 void fq_nmod_mpoly_inflate(fq_nmod_mpoly_t A, const fq_nmod_mpoly_t B,
0801        const fmpz * shift, const fmpz * stride, const fq_nmod_mpoly_ctx_t ctx);
0802
0803
0804 /******************************************************************************
0805
0806    Internal functions (guaranteed to change without notice)
0807
0808 ******************************************************************************/
0809
0810 void mpoly_void_ring_init_fq_nmod_mpoly_ctx(mpoly_void_ring_t R,
0811                                                 const fq_nmod_mpoly_ctx_t ctx);
0812
0813 void fq_nmod_mpolyl_lead_coeff(fq_nmod_mpoly_t c,
0814                                      const fq_nmod_mpoly_t A, slong num_vars,
0815                                                 const fq_nmod_mpoly_ctx_t ctx);
0816
0817 void fq_nmod_mpoly_to_mpolyl_perm_deflate(
0818     fq_nmod_mpoly_t A,
0819     const fq_nmod_mpoly_ctx_t lctx,
0820     const fq_nmod_mpoly_t B,
0821     const fq_nmod_mpoly_ctx_t ctx,
0822     const slong * perm,
0823     const ulong * shift,
0824     const ulong * stride);
0825
0826 void fq_nmod_mpoly_from_mpolyl_perm_inflate(
0827     fq_nmod_mpoly_t A,
0828     flint_bitcnt_t Abits,
0829     const fq_nmod_mpoly_ctx_t ctx,
0830     const fq_nmod_mpoly_t B,
0831     const fq_nmod_mpoly_ctx_t lctx,
0832     const slong * perm,
0833     const ulong * shift,
0834     const ulong * stride);
0835
0836 int fq_nmod_mpolyl_gcd_zippel_smprime(
0837     fq_nmod_mpoly_t rG, const slong * rGdegs,
0838     fq_nmod_mpoly_t rAbar,
0839     fq_nmod_mpoly_t rBbar,
0840     const fq_nmod_mpoly_t A, const slong * Adegs,
0841     const fq_nmod_mpoly_t B, const slong * Bdegs,
0842     const fq_nmod_mpoly_t gamma, const slong * gammadegs,
0843     const fq_nmod_mpoly_ctx_t ctx);
0844
0845 int fq_nmod_mpolyl_gcd_zippel_lgprime(
0846     fq_nmod_mpoly_t rG, const slong * rGdegs,
0847     fq_nmod_mpoly_t rAbar,
0848     fq_nmod_mpoly_t rBbar,
0849     const fq_nmod_mpoly_t A, const slong * Adegs,
0850     const fq_nmod_mpoly_t B, const slong * Bdegs,
0851     const fq_nmod_mpoly_t gamma, const slong * gammadegs,
0852     const fq_nmod_mpoly_ctx_t ctx);
0853
0854 int fq_nmod_mpolyl_gcd_hensel_smprime(
0855     fq_nmod_mpoly_t G, slong Gdeg,
0856     fq_nmod_mpoly_t Abar,
0857     fq_nmod_mpoly_t Bbar,
0858     const fq_nmod_mpoly_t A,
0859     const fq_nmod_mpoly_t B,
0860     const fq_nmod_mpoly_ctx_t ctx);
0861
0862 int fq_nmod_mpolyl_content(fq_nmod_mpoly_t g,
0863                                     const fq_nmod_mpoly_t A, slong num_vars,
0864                                                 const fq_nmod_mpoly_ctx_t ctx);
0865
0866 void fq_nmod_mpoly_pow_rmul(fq_nmod_mpoly_t A, const fq_nmod_mpoly_t B,
0867                                        ulong k, const fq_nmod_mpoly_ctx_t ctx);
0868
0869 void _fq_nmod_mpoly_to_fq_nmod_poly_deflate(fq_nmod_poly_t A,
0870                    const fq_nmod_mpoly_t B, slong var, const ulong * Bshift,
0871                          const ulong * Bstride, const fq_nmod_mpoly_ctx_t ctx);
0872
0873 void _fq_nmod_mpoly_from_fq_nmod_poly_inflate(fq_nmod_mpoly_t A,
0874     flint_bitcnt_t Abits, const fq_nmod_poly_t B, slong var, const ulong * Ashift,
0875                          const ulong * Astride, const fq_nmod_mpoly_ctx_t ctx);
0876
0877
0878 int fq_nmod_mpoly_repack_bits(fq_nmod_mpoly_t A, const fq_nmod_mpoly_t B,
0879                           flint_bitcnt_t Abits, const fq_nmod_mpoly_ctx_t ctx);
0880
0881 int fq_nmod_mpoly_repack_bits_inplace(fq_nmod_mpoly_t A,
0882                          flint_bitcnt_t Abits, const fq_nmod_mpoly_ctx_t ctx);
0883
0884
0885 void fq_nmod_mpoly_ctx_change_modulus(fq_nmod_mpoly_ctx_t ctx,
0886                                                                     slong deg);
0887
0888
0889 /* Univariates ***************************************************************/
0890
0891 void fq_nmod_mpoly_univar_init(fq_nmod_mpoly_univar_t A,
0892                                                 const fq_nmod_mpoly_ctx_t FLINT_UNUSED(ctx));
0893
0894 void fq_nmod_mpoly_univar_clear(fq_nmod_mpoly_univar_t A,
0895                                                 const fq_nmod_mpoly_ctx_t ctx);
0896
0897 void fq_nmod_mpoly_univar_fit_length(fq_nmod_mpoly_univar_t A,
0898                                   slong length, const fq_nmod_mpoly_ctx_t ctx);
0899
0900 void fq_nmod_mpoly_univar_print_pretty(const fq_nmod_mpoly_univar_t A,
0901                                const char ** x, const fq_nmod_mpoly_ctx_t ctx);
0902
0903 void fq_nmod_mpoly_univar_assert_canonical(fq_nmod_mpoly_univar_t A,
0904                                                 const fq_nmod_mpoly_ctx_t ctx);
0905
0906 FQ_NMOD_MPOLY_INLINE
0907 void fq_nmod_mpoly_univar_zero(fq_nmod_mpoly_univar_t A,
0908                                                  const fq_nmod_mpoly_ctx_t FLINT_UNUSED(ctx))
0909 {
0910     A->length = 0;
0911 }
0912
0913 void fq_nmod_mpoly_univar_set_coeff_ui(fq_nmod_mpoly_univar_t A,
0914               ulong e, const fq_nmod_mpoly_t c, const fq_nmod_mpoly_ctx_t ctx);
0915
0916 void fq_nmod_mpoly_to_univar(fq_nmod_mpoly_univar_t A,
0917             const fq_nmod_mpoly_t B, slong var, const fq_nmod_mpoly_ctx_t ctx);
0918
0919 void _fq_nmod_mpoly_from_univar(fq_nmod_mpoly_t A, flint_bitcnt_t Abits,
0920      const fq_nmod_mpoly_univar_t B, slong var, const fq_nmod_mpoly_ctx_t ctx);
0921
0922 void fq_nmod_mpoly_from_univar(fq_nmod_mpoly_t A,
0923      const fq_nmod_mpoly_univar_t B, slong var, const fq_nmod_mpoly_ctx_t ctx);
0924
0925 FQ_NMOD_MPOLY_INLINE
0926 void fq_nmod_mpoly_univar_swap(fq_nmod_mpoly_univar_t A,
0927                        fq_nmod_mpoly_univar_t B, const fq_nmod_mpoly_ctx_t FLINT_UNUSED(ctx))
0928 {
0929     FLINT_SWAP(fq_nmod_mpoly_univar_struct, *A, *B);
0930 }
0931
0932 int fq_nmod_mpoly_univar_degree_fits_si(const fq_nmod_mpoly_univar_t A, const fq_nmod_mpoly_ctx_t FLINT_UNUSED(ctx));
0933
0934 FQ_NMOD_MPOLY_INLINE
0935 slong fq_nmod_mpoly_univar_length(const fq_nmod_mpoly_univar_t A,
0936                                                  const fq_nmod_mpoly_ctx_t FLINT_UNUSED(ctx))
0937 {
0938     return A->length;
0939 }
0940
0941 slong fq_nmod_mpoly_univar_get_term_exp_si(fq_nmod_mpoly_univar_t A, slong i, const fq_nmod_mpoly_ctx_t FLINT_UNUSED(ctx));
0942
0943 FQ_NMOD_MPOLY_INLINE
0944 void fq_nmod_mpoly_univar_get_term_coeff(fq_nmod_mpoly_t c,
0945         const fq_nmod_mpoly_univar_t A, slong i, const fq_nmod_mpoly_ctx_t ctx)
0946 {
0947     FLINT_ASSERT(i < (ulong)A->length);
0948     fq_nmod_mpoly_set(c, A->coeffs + i, ctx);
0949 }
0950
0951 FQ_NMOD_MPOLY_INLINE
0952 void fq_nmod_mpoly_univar_swap_term_coeff(fq_nmod_mpoly_t c,
0953               fq_nmod_mpoly_univar_t A, slong i, const fq_nmod_mpoly_ctx_t ctx)
0954 {
0955     FLINT_ASSERT(i < (ulong)A->length);
0956     fq_nmod_mpoly_swap(c, A->coeffs + i, ctx);
0957 }
0958
0959 int fq_nmod_mpoly_univar_pseudo_gcd(fq_nmod_mpoly_univar_t Gx,
0960         const fq_nmod_mpoly_univar_t Ax, const fq_nmod_mpoly_univar_t Bx,
0961                                                const fq_nmod_mpoly_ctx_t ctx);
0962
0963 int fq_nmod_mpoly_univar_resultant(fq_nmod_mpoly_t R,
0964         const fq_nmod_mpoly_univar_t Ax, const fq_nmod_mpoly_univar_t Bx,
0965                                                const fq_nmod_mpoly_ctx_t ctx);
0966
0967 int fq_nmod_mpoly_univar_discriminant(fq_nmod_mpoly_t D,
0968              const fq_nmod_mpoly_univar_t Fx, const fq_nmod_mpoly_ctx_t ctx);
0969
0970 int fq_nmod_mpoly_resultant(fq_nmod_mpoly_t R,
0971                         const fq_nmod_mpoly_t A, const fq_nmod_mpoly_t B,
0972                                     slong var, const fq_nmod_mpoly_ctx_t ctx);
0973
0974 int fq_nmod_mpoly_discriminant(fq_nmod_mpoly_t R,
0975           const fq_nmod_mpoly_t A, slong var, const fq_nmod_mpoly_ctx_t ctx);
0976
0977 /* mpolyu ********************************************************************/
0978
0979 int fq_nmod_mpolyu_is_canonical(const fq_nmod_mpolyu_t poly,
0980                                                 const fq_nmod_mpoly_ctx_t ctx);
0981
0982 void fq_nmod_mpolyu_init(fq_nmod_mpolyu_t A, flint_bitcnt_t bits,
0983                                                 const fq_nmod_mpoly_ctx_t FLINT_UNUSED(ctx));
0984
0985 void fq_nmod_mpolyu_clear(fq_nmod_mpolyu_t A,
0986                                                const fq_nmod_mpoly_ctx_t uctx);
0987
0988 FQ_NMOD_MPOLY_INLINE
0989 void fq_nmod_mpolyu_swap(fq_nmod_mpolyu_t A, fq_nmod_mpolyu_t B,
0990                                                const fq_nmod_mpoly_ctx_t FLINT_UNUSED(uctx))
0991 {
0992     fq_nmod_mpolyu_struct t = *B;
0993     *B = *A;
0994     *A = t;
0995 }
0996
0997 void fq_nmod_mpolyu_zero(fq_nmod_mpolyu_t A,
0998                                                const fq_nmod_mpoly_ctx_t uctx);
0999
1000 int fq_nmod_mpolyu_is_one(fq_nmod_mpolyu_t A,
1001                                                const fq_nmod_mpoly_ctx_t uctx);
1002
1003 void fq_nmod_mpolyu_print_pretty(const fq_nmod_mpolyu_t poly,
1004                                const char ** x, const fq_nmod_mpoly_ctx_t ctx);
1005
1006 void fq_nmod_mpolyu_fit_length(fq_nmod_mpolyu_t A, slong length,
1007                                                const fq_nmod_mpoly_ctx_t uctx);
1008
1009 void fq_nmod_mpolyu_one(fq_nmod_mpolyu_t A,
1010                                                const fq_nmod_mpoly_ctx_t uctx);
1011
1012 void fq_nmod_mpolyu_degrees_si(
1013     slong * degs,
1014     const fq_nmod_mpolyu_t A,
1015     const fq_nmod_mpoly_ctx_t ctx);
1016
1017 void fq_nmod_mpolyu_repack_bits_inplace(
1018     fq_nmod_mpolyu_t A,
1019     flint_bitcnt_t bits,
1020     const fq_nmod_mpoly_ctx_t ctx);
1021
1022 void fq_nmod_mpolyu_shift_right(fq_nmod_mpolyu_t A, ulong s);
1023
1024 void fq_nmod_mpolyu_shift_left(fq_nmod_mpolyu_t A, ulong s);
1025
1026 int fq_nmod_mpolyu_content_mpoly(fq_nmod_mpoly_t g,
1027                       const fq_nmod_mpolyu_t A, const fq_nmod_mpoly_ctx_t ctx);
1028
1029 void fq_nmod_mpolyu_scalar_mul_fq_nmod(fq_nmod_mpolyu_t A,
1030                                    fq_nmod_t c, const fq_nmod_mpoly_ctx_t ctx);
1031
1032 void fq_nmod_mpolyu_set(fq_nmod_mpolyu_t A, const fq_nmod_mpolyu_t B,
1033                                                const fq_nmod_mpoly_ctx_t uctx);
1034
1035 void fq_nmod_mpolyu_evaluate_one_fq_nmod(fq_nmod_mpolyu_t E,
1036                         fq_nmod_mpolyu_t A, slong var, const fq_nmod_t alpha,
1037                                                 const fq_nmod_mpoly_ctx_t ctx);
1038
1039 void fq_nmod_mpolyu_setform(fq_nmod_mpolyu_t A, fq_nmod_mpolyu_t B,
1040                                                 const fq_nmod_mpoly_ctx_t ctx);
1041
1042 fq_nmod_mpoly_struct * _fq_nmod_mpolyu_get_coeff(fq_nmod_mpolyu_t A,
1043                                     ulong pow, const fq_nmod_mpoly_ctx_t uctx);
1044
1045 void fq_nmod_mpoly_to_mpolyu_perm_deflate(
1046                          fq_nmod_mpolyu_t A, const fq_nmod_mpoly_ctx_t uctx,
1047                  const fq_nmod_mpoly_t B, const fq_nmod_mpoly_ctx_t ctx,
1048                 const slong * perm, const ulong * shift, const ulong * stride);
1049
1050 void fq_nmod_mpoly_from_mpolyu_perm_inflate(
1051         fq_nmod_mpoly_t A, flint_bitcnt_t Abits, const fq_nmod_mpoly_ctx_t ctx,
1052           const fq_nmod_mpolyu_t B, const fq_nmod_mpoly_ctx_t uctx,
1053                 const slong * perm, const ulong * shift, const ulong * stride);
1054
1055 int fq_nmod_mpolyuu_divides(fq_nmod_mpolyu_t Q,
1056           const fq_nmod_mpolyu_t A, const fq_nmod_mpolyu_t B, slong nmainvars,
1057                                                 const fq_nmod_mpoly_ctx_t ctx);
1058
1059 void fq_nmod_mpolyu_divexact_mpoly_inplace(fq_nmod_mpolyu_t A,
1060                              fq_nmod_mpoly_t c, const fq_nmod_mpoly_ctx_t ctx);
1061
1062 void fq_nmod_mpolyu_mul_mpoly(fq_nmod_mpolyu_t A, fq_nmod_mpolyu_t B,
1063                              fq_nmod_mpoly_t c, const fq_nmod_mpoly_ctx_t ctx);
1064
1065 void fq_nmod_mpolyu_mul_mpoly_inplace(fq_nmod_mpolyu_t A,
1066                              fq_nmod_mpoly_t c, const fq_nmod_mpoly_ctx_t ctx);
1067
1068 int fq_nmod_mpolyu_gcdm_zippel(fq_nmod_mpolyu_t G,
1069              fq_nmod_mpolyu_t Abar, fq_nmod_mpolyu_t Bbar,  fq_nmod_mpolyu_t A,
1070           fq_nmod_mpolyu_t B, fq_nmod_mpoly_ctx_t ctx, flint_rand_t randstate);
1071
1072 FQ_NMOD_MPOLY_INLINE ulong * fq_nmod_mpolyu_leadcoeff(
1073                        const fq_nmod_mpolyu_t A, const fq_nmod_mpoly_ctx_t ctx)
1074 {
1075     FLINT_ASSERT(A->length > 0);
1076     return _fq_nmod_mpoly_leadcoeff(A->coeffs + 0, ctx);
1077 }
1078
1079 /* mpolyn ********************************************************************/
1080
1081 void fq_nmod_mpolyn_init(fq_nmod_mpolyn_t A, flint_bitcnt_t bits,
1082                                                 const fq_nmod_mpoly_ctx_t FLINT_UNUSED(ctx));
1083
1084 void fq_nmod_mpolyn_clear(fq_nmod_mpolyn_t A, const fq_nmod_mpoly_ctx_t FLINT_UNUSED(ctx));
1085
1086 void fq_nmod_mpolyn_swap(fq_nmod_mpolyn_t A, fq_nmod_mpolyn_t B);
1087
1088 int fq_nmod_mpolyn_is_canonical(const fq_nmod_mpolyn_t A,
1089                                                 const fq_nmod_mpoly_ctx_t ctx);
1090
1091 void fq_nmod_mpolyn_zero(fq_nmod_mpolyn_t A, const fq_nmod_mpoly_ctx_t FLINT_UNUSED(ctx));
1092
1093 void fq_nmod_mpolyn_one(fq_nmod_mpolyn_t A, const fq_nmod_mpoly_ctx_t ctx);
1094
1095 int fq_nmod_mpolyn_is_zero(fq_nmod_mpolyn_t A, const fq_nmod_mpoly_ctx_t FLINT_UNUSED(ctx));
1096
1097 void fq_nmod_mpolyn_print_pretty(const fq_nmod_mpolyn_t A,
1098                              const char ** x_in, const fq_nmod_mpoly_ctx_t ctx);
1099
1100 void fq_nmod_mpolyn_fit_length(fq_nmod_mpolyn_t A, slong length,
1101                                                 const fq_nmod_mpoly_ctx_t ctx);
1102
1103 void fq_nmod_mpolyn_fit_bits(fq_nmod_mpolyn_t A, slong bits,
1104                                                 const fq_nmod_mpoly_ctx_t ctx);
1105
1106 void fq_nmod_mpolyn_set(fq_nmod_mpolyn_t A, const fq_nmod_mpolyn_t B,
1107                                                 const fq_nmod_mpoly_ctx_t ctx);
1108
1109 FQ_NMOD_MPOLY_INLINE ulong * fq_nmod_mpolyn_leadcoeff(
1110                              fq_nmod_mpolyn_t A, const fq_nmod_mpoly_ctx_t ctx)
1111 {
1112     /* slong d = fq_nmod_ctx_degree(ctx->fqctx); */
1113     slong d = ctx->fqctx->modulus->length - 1;
1114     n_poly_struct * leadpoly;
1115     FLINT_ASSERT(A->length > 0);
1116     leadpoly = A->coeffs + 0;
1117     FLINT_ASSERT(leadpoly->length > 0);
1118     return leadpoly->coeffs + d*(leadpoly->length - 1);
1119 }
1120
1121 FQ_NMOD_MPOLY_INLINE n_poly_struct * fq_nmod_mpolyn_leadcoeff_poly(
1122                        const fq_nmod_mpolyn_t A, const fq_nmod_mpoly_ctx_t FLINT_UNUSED(ctx))
1123 {
1124     FLINT_ASSERT(A->length > 0);
1125     return A->coeffs + 0;
1126 }
1127
1128 /* mpolyun *******************************************************************/
1129
1130 void fq_nmod_mpoly_to_mpolyn_perm_deflate(fq_nmod_mpolyn_t A,
1131                 const fq_nmod_mpoly_ctx_t nctx,
1132                 const fq_nmod_mpoly_t B, const fq_nmod_mpoly_ctx_t ctx,
1133                 const slong * perm, const ulong * shift, const ulong * stride);
1134
1135 void fq_nmod_mpoly_from_mpolyn_perm_inflate(fq_nmod_mpoly_t A,
1136                 flint_bitcnt_t Abits, const fq_nmod_mpoly_ctx_t ctx,
1137                 const fq_nmod_mpolyn_t B, const fq_nmod_mpoly_ctx_t nctx,
1138                 const slong * perm, const ulong * shift, const ulong * stride);
1139
1140 void fq_nmod_mpolyun_init(fq_nmod_mpolyun_t A,
1141                            flint_bitcnt_t bits, const fq_nmod_mpoly_ctx_t FLINT_UNUSED(ctx));
1142
1143 void fq_nmod_mpolyun_clear(fq_nmod_mpolyun_t A,
1144                                                 const fq_nmod_mpoly_ctx_t ctx);
1145
1146 int fq_nmod_mpolyun_is_canonical(const fq_nmod_mpolyun_t A,
1147                                                 const fq_nmod_mpoly_ctx_t ctx);
1148
1149 void fq_nmod_mpolyun_print_pretty(const fq_nmod_mpolyun_t poly,
1150                                const char ** x, const fq_nmod_mpoly_ctx_t ctx);
1151
1152 void fq_nmod_mpolyun_swap(fq_nmod_mpolyun_t A, fq_nmod_mpolyun_t B);
1153
1154 void fq_nmod_mpolyun_zero(fq_nmod_mpolyun_t A,
1155                                                 const fq_nmod_mpoly_ctx_t ctx);
1156
1157 void fq_nmod_mpolyun_fit_length(fq_nmod_mpolyun_t A,
1158                                   slong length, const fq_nmod_mpoly_ctx_t ctx);
1159
1160 void fq_nmod_mpolyun_one(fq_nmod_mpolyun_t A,
1161                                                 const fq_nmod_mpoly_ctx_t ctx);
1162
1163 int fq_nmod_mpolyn_is_nonzero_fq_nmod(const fq_nmod_mpolyn_t A,
1164                                                 const fq_nmod_mpoly_ctx_t ctx);
1165
1166 int fq_nmod_mpolyun_is_nonzero_fq_nmod(const fq_nmod_mpolyun_t A,
1167                                                 const fq_nmod_mpoly_ctx_t ctx);
1168
1169 void fq_nmod_mpolyn_scalar_mul_fq_nmod(fq_nmod_mpolyn_t A,
1170                              const fq_nmod_t c, const fq_nmod_mpoly_ctx_t ctx);
1171
1172 void fq_nmod_mpolyun_scalar_mul_fq_nmod(fq_nmod_mpolyun_t A,
1173                              const fq_nmod_t c, const fq_nmod_mpoly_ctx_t ctx);
1174
1175 void fq_nmod_mpolyun_shift_right(fq_nmod_mpolyun_t A, ulong s);
1176
1177 void fq_nmod_mpolyun_shift_left(fq_nmod_mpolyun_t A, ulong s);
1178
1179 void fq_nmod_mpolyn_mul_poly(fq_nmod_mpolyn_t A,
1180         const fq_nmod_mpolyn_t B, const fq_nmod_poly_t c,
1181         const fq_nmod_mpoly_ctx_t ctx);
1182
1183 void fq_nmod_mpolyun_mul_poly(fq_nmod_mpolyun_t A,
1184                          const fq_nmod_mpolyun_t B, const fq_nmod_poly_t c,
1185                                                 const fq_nmod_mpoly_ctx_t ctx);
1186
1187 void fq_nmod_mpolyn_divexact_poly(fq_nmod_mpolyn_t A,
1188         const fq_nmod_mpolyn_t B, const fq_nmod_poly_t c,
1189         const fq_nmod_mpoly_ctx_t ctx);
1190
1191 void fq_nmod_mpolyun_divexact_poly(fq_nmod_mpolyun_t A,
1192                         const fq_nmod_mpolyun_t B, const fq_nmod_poly_t c,
1193                                                 const fq_nmod_mpoly_ctx_t ctx);
1194
1195 void fq_nmod_mpolyn_content_poly(fq_nmod_poly_t g,
1196                             fq_nmod_mpolyn_t B, const fq_nmod_mpoly_ctx_t ctx);
1197
1198 void fq_nmod_mpolyun_content_poly(fq_nmod_poly_t g,
1199                            fq_nmod_mpolyun_t B, const fq_nmod_mpoly_ctx_t ctx);
1200
1201 slong fq_nmod_mpolyn_lastdeg(fq_nmod_mpolyn_t A, const fq_nmod_mpoly_ctx_t FLINT_UNUSED(ctx));
1202
1203 slong fq_nmod_mpolyun_lastdeg(fq_nmod_mpolyun_t A, const fq_nmod_mpoly_ctx_t FLINT_UNUSED(ctx));
1204
1205 void fq_nmod_mpolyun_set(
1206     fq_nmod_mpolyun_t A,
1207     const fq_nmod_mpolyun_t B,
1208     const fq_nmod_mpoly_ctx_t ctx);
1209
1210 void fq_nmod_mpoly_cvtto_mpolyn(
1211     fq_nmod_mpolyn_t A,
1212     const fq_nmod_mpoly_t B,
1213     slong var,
1214     const fq_nmod_mpoly_ctx_t ctx);
1215
1216 void fq_nmod_mpolyu_cvtto_mpolyun(
1217     fq_nmod_mpolyun_t A,
1218     const fq_nmod_mpolyu_t B,
1219     slong k,
1220     const fq_nmod_mpoly_ctx_t ctx);
1221
1222 void fq_nmod_mpoly_cvtfrom_mpolyn(
1223     fq_nmod_mpoly_t A,
1224     fq_nmod_mpolyn_t B,
1225     slong var,
1226     const fq_nmod_mpoly_ctx_t ctx);
1227
1228 void fq_nmod_mpolyu_cvtfrom_mpolyun(
1229     fq_nmod_mpolyu_t A,
1230     fq_nmod_mpolyun_t B,
1231     slong var,
1232     const fq_nmod_mpoly_ctx_t ctx);
1233
1234 FQ_NMOD_MPOLY_INLINE n_poly_struct * fq_nmod_mpolyun_leadcoeff_poly(
1235                       const fq_nmod_mpolyun_t A, const fq_nmod_mpoly_ctx_t ctx)
1236 {
1237     FLINT_ASSERT(A->length > 0);
1238     return fq_nmod_mpolyn_leadcoeff_poly(A->coeffs + 0, ctx);
1239 }
1240
1241
1242 /*** gcd *********************************************************************/
1243
1244 int fq_nmod_next(fq_nmod_t alpha, const fq_nmod_ctx_t fqctx);
1245
1246 void fq_nmod_next_not_zero(fq_nmod_t alpha, const fq_nmod_ctx_t fqctx);
1247
1248 nmod_gcds_ret_t fq_nmod_mpolyu_gcds_zippel(fq_nmod_mpolyu_t G,
1249                 fq_nmod_mpolyu_t A, fq_nmod_mpolyu_t B, fq_nmod_mpolyu_t f,
1250                                     slong var, const fq_nmod_mpoly_ctx_t ctx,
1251                                      flint_rand_t randstate, slong * degbound);
1252
1253 int fq_nmod_mpolyu_gcdp_zippel_univar(fq_nmod_mpolyu_t G,
1254             fq_nmod_mpolyu_t Abar, fq_nmod_mpolyu_t Bbar, fq_nmod_mpolyu_t A,
1255                             fq_nmod_mpolyu_t B, const fq_nmod_mpoly_ctx_t ctx);
1256
1257 int fq_nmod_mpolyu_gcdp_zippel_univar_no_cofactors(fq_nmod_mpolyu_t G,
1258         fq_nmod_mpolyu_t A, fq_nmod_mpolyu_t B, const fq_nmod_mpoly_ctx_t ctx);
1259
1260 int fq_nmod_mpolyu_gcdp_zippel(fq_nmod_mpolyu_t G,
1261               fq_nmod_mpolyu_t Abar, fq_nmod_mpolyu_t Bbar, fq_nmod_mpolyu_t A,
1262                   fq_nmod_mpolyu_t B, slong var, const fq_nmod_mpoly_ctx_t ctx,
1263                                                        flint_rand_t randstate);
1264
1265 int fq_nmod_mpolyn_gcd_brown_smprime(fq_nmod_mpolyn_t G,
1266          fq_nmod_mpolyn_t Abar, fq_nmod_mpolyn_t Bbar, fq_nmod_mpolyn_t A,
1267                  fq_nmod_mpolyn_t B, slong var, const fq_nmod_mpoly_ctx_t ctx);
1268
1269 int fq_nmod_mpolyn_gcd_brown_lgprime(fq_nmod_mpolyn_t G,
1270          fq_nmod_mpolyn_t Abar, fq_nmod_mpolyn_t Bbar, fq_nmod_mpolyn_t A,
1271                  fq_nmod_mpolyn_t B, slong var, const fq_nmod_mpoly_ctx_t ctx);
1272
1273 void _fq_nmod_mpoly_monomial_evals2_cache(n_fq_polyun_t E,
1274         const ulong * Aexps, flint_bitcnt_t Abits, slong Alen,
1275         const fq_nmod_struct * betas, slong m, const fq_nmod_mpoly_ctx_t ctx);
1276
1277 void _fq_nmod_mpoly_monomial_evals_cache(n_fq_poly_t E,
1278                     const ulong * Aexps, flint_bitcnt_t Abits, slong Alen,
1279                     const fq_nmod_struct * betas, slong start, slong stop,
1280                                                 const fq_nmod_mpoly_ctx_t ctx);
1281
1282 void n_fq_bpoly_eval_step_sep(n_fq_bpoly_t E, n_fq_polyun_t cur,
1283                             const n_fq_polyun_t inc, const fq_nmod_mpoly_t A,
1284                                                       const fq_nmod_ctx_t ctx);
1285
1286 void n_fq_polyun_zip_start(n_fq_polyun_t Z, n_fq_polyun_t H,
1287                                     slong req_images, const fq_nmod_ctx_t ctx);
1288
1289 int n_fq_polyu2n_add_zip_must_match(n_fq_polyun_t Z,
1290               const n_fq_bpoly_t A, slong cur_length, const fq_nmod_ctx_t ctx);
1291
1292 int n_fq_polyun_zip_solve(fq_nmod_mpoly_t A, n_fq_polyun_t Z,
1293               n_fq_polyun_t H, n_fq_polyun_t M, const fq_nmod_mpoly_ctx_t ctx);
1294
1295 /* gcd_helper_eval_interp ****************************************************/
1296
1297 void nmod_mpolyn_interp_reduce_lg_poly(fq_nmod_poly_t E,
1298                             const fq_nmod_ctx_t fqctx, const nmod_mpolyn_t A,
1299                                                    const nmod_mpoly_ctx_t ctx);
1300
1301 void nmod_mpolyn_interp_lift_lg_poly(slong * lastdeg_,
1302                          nmod_mpolyn_t A, const nmod_mpoly_ctx_t ctx,
1303                             const fq_nmod_poly_t B, const fq_nmod_ctx_t fqctx);
1304
1305 int nmod_mpolyn_interp_crt_lg_poly(slong * lastdeg_,
1306      nmod_mpolyn_t F, nmod_mpolyn_t T, n_poly_t modulus,
1307      const nmod_mpoly_ctx_t ctx, fq_nmod_poly_t A,  const fq_nmod_ctx_t fqctx);
1308
1309 void nmod_mpolyn_interp_lift_lg_bpoly(slong * lastdeg_,
1310               nmod_mpolyn_t F, const nmod_mpoly_ctx_t smctx, n_fq_bpoly_t A,
1311                                               const fq_nmod_mpoly_ctx_t lgctx);
1312
1313 int nmod_mpolyn_interp_crt_lg_bpoly(slong * lastdeg, nmod_mpolyn_t F,
1314            nmod_mpolyn_t T, n_fq_poly_t modulus, const nmod_mpoly_ctx_t smctx,
1315                               n_fq_bpoly_t A, const fq_nmod_mpoly_ctx_t lgctx);
1316
1317 void nmod_mpolyn_interp_reduce_lg_mpolyn(fq_nmod_mpolyn_t E,
1318                       fq_nmod_mpoly_ctx_t ectx, nmod_mpolyn_t A, slong var,
1319                                                    const nmod_mpoly_ctx_t ctx);
1320
1321 void nmod_mpolyn_interp_lift_lg_mpolyn(slong * lastdeg,
1322                 nmod_mpolyn_t A, slong var, const nmod_mpoly_ctx_t ctx,
1323                            fq_nmod_mpolyn_t B, const fq_nmod_mpoly_ctx_t ectx);
1324
1325 int nmod_mpolyn_interp_crt_lg_mpolyn(slong * lastdeg_,
1326             nmod_mpolyn_t F, nmod_mpolyn_t T, n_poly_t modulus, slong var,
1327             const nmod_mpoly_ctx_t ctx, fq_nmod_mpolyn_t A,
1328                                                const fq_nmod_mpoly_ctx_t ectx);
1329
1330 void nmod_mpolyn_interp_reduce_lg_mpoly(fq_nmod_mpoly_t A,
1331                             nmod_mpolyn_t B, const fq_nmod_mpoly_ctx_t ffctx,
1332                                                    const nmod_mpoly_ctx_t ctx);
1333
1334 void nmod_mpolyun_interp_reduce_lg_mpolyu(fq_nmod_mpolyu_t A,
1335                           nmod_mpolyun_t B, const fq_nmod_mpoly_ctx_t ffctx,
1336                                                    const nmod_mpoly_ctx_t ctx);
1337
1338 void nmod_mpolyn_interp_lift_lg_mpoly(nmod_mpolyn_t A,
1339                               const nmod_mpoly_ctx_t ctx, fq_nmod_mpoly_t Ap,
1340                                                const fq_nmod_mpoly_ctx_t ctxp);
1341
1342 void nmod_mpolyun_interp_lift_lg_mpolyu(nmod_mpolyun_t A,
1343                             const nmod_mpoly_ctx_t ctx, fq_nmod_mpolyu_t Ap,
1344                                                const fq_nmod_mpoly_ctx_t ctxp);
1345
1346 int nmod_mpolyun_interp_crt_lg_mpolyu(slong * lastdeg,
1347                           nmod_mpolyun_t F, nmod_mpolyun_t T, n_poly_t m,
1348                           const nmod_mpoly_ctx_t ctx, fq_nmod_mpolyu_t A,
1349                                               const fq_nmod_mpoly_ctx_t ffctx);
1350
1351 int nmod_mpolyn_interp_mcrt_lg_mpoly(slong * lastdeg_,
1352             nmod_mpolyn_t H, const nmod_mpoly_ctx_t smctx, const n_poly_t m,
1353                               const ulong * inv_m_eval,fq_nmod_mpoly_t A,
1354                                               const fq_nmod_mpoly_ctx_t lgctx);
1355
1356 int nmod_mpolyun_interp_mcrt_lg_mpolyu(slong * lastdeg,
1357                nmod_mpolyun_t H, const nmod_mpoly_ctx_t ctx, n_poly_t m,
1358                            fq_nmod_mpolyu_t A, const fq_nmod_mpoly_ctx_t ctxp);
1359
1360 void fq_nmod_mpolyn_interp_reduce_sm_poly(fq_nmod_poly_t E,
1361                             const fq_nmod_mpolyn_t A, const fq_nmod_t alpha,
1362                                                 const fq_nmod_mpoly_ctx_t ctx);
1363
1364 void fq_nmod_mpolyn_interp_lift_sm_poly(fq_nmod_mpolyn_t A,
1365                         const fq_nmod_poly_t B, const fq_nmod_mpoly_ctx_t ctx);
1366
1367 int fq_nmod_mpolyn_interp_crt_sm_poly(slong * lastdeg_,
1368             fq_nmod_mpolyn_t F, fq_nmod_mpolyn_t T, const fq_nmod_poly_t A,
1369             const fq_nmod_poly_t modulus, const fq_nmod_t alpha,
1370                                                 const fq_nmod_mpoly_ctx_t ctx);
1371
1372 void fq_nmod_mpolyn_interp_lift_sm_bpoly(fq_nmod_mpolyn_t F,
1373                                 n_fq_bpoly_t A, const fq_nmod_mpoly_ctx_t ctx);
1374
1375 int fq_nmod_mpolyn_interp_crt_sm_bpoly(slong * lastdeg,
1376                 fq_nmod_mpolyn_t F, fq_nmod_mpolyn_t T, const n_fq_bpoly_t A,
1377                 const n_fq_poly_t modulus, n_fq_poly_t alphapow,
1378                                                 const fq_nmod_mpoly_ctx_t ctx);
1379
1380 void fq_nmod_mpolyn_interp_reduce_sm_mpolyn(fq_nmod_mpolyn_t E,
1381                              fq_nmod_mpolyn_t A, slong var, fq_nmod_t alpha,
1382                                                 const fq_nmod_mpoly_ctx_t ctx);
1383
1384 void fq_nmod_mpolyn_interp_lift_sm_mpolyn(fq_nmod_mpolyn_t A,
1385                  fq_nmod_mpolyn_t B, slong var, const fq_nmod_mpoly_ctx_t ctx);
1386
1387 int fq_nmod_mpolyn_interp_mcrt_sm_mpoly(slong * lastdeg_,
1388         fq_nmod_mpolyn_t F, fq_nmod_mpoly_t A, const n_fq_poly_t modulus,
1389                           n_fq_poly_t alphapow, const fq_nmod_mpoly_ctx_t ctx);
1390
1391 int fq_nmod_mpolyn_interp_crt_sm_mpolyn(slong * lastdeg_,
1392         fq_nmod_mpolyn_t F, fq_nmod_mpolyn_t T, fq_nmod_mpolyn_t A,  slong var,
1393         fq_nmod_poly_t modulus, const fq_nmod_t alpha,
1394                                                 const fq_nmod_mpoly_ctx_t ctx);
1395
1396 void fq_nmod_mpolyn_interp_reduce_lg_poly(fq_nmod_poly_t E,
1397                         const fq_nmod_mpoly_ctx_t ectx, fq_nmod_mpolyn_t A,
1398                     const fq_nmod_mpoly_ctx_t ctx, const bad_fq_nmod_embed_t emb);
1399
1400 void fq_nmod_mpolyn_interp_lift_lg_poly(slong * lastdeg_,
1401       fq_nmod_mpolyn_t A, const fq_nmod_mpoly_ctx_t ctx, fq_nmod_poly_t B,
1402                    const fq_nmod_mpoly_ctx_t ectx, const bad_fq_nmod_embed_t emb);
1403
1404 int fq_nmod_mpolyn_interp_crt_lg_poly(slong * lastdeg_,
1405             fq_nmod_mpolyn_t F, fq_nmod_mpolyn_t T, fq_nmod_poly_t modulus,
1406             const fq_nmod_mpoly_ctx_t ctx, fq_nmod_poly_t A,
1407                    const fq_nmod_mpoly_ctx_t ectx, const bad_fq_nmod_embed_t emb);
1408
1409 void fq_nmod_mpolyn_interp_lift_lg_bpoly(slong * lastdeg_,
1410          fq_nmod_mpolyn_t F, const fq_nmod_mpoly_ctx_t smctx, n_fq_bpoly_t A,
1411                const fq_nmod_mpoly_ctx_t lgctx, const bad_fq_nmod_embed_t emb);
1412
1413 int fq_nmod_mpolyn_interp_crt_lg_bpoly(slong * lastdeg,
1414                fq_nmod_mpolyn_t F, fq_nmod_mpolyn_t T, n_fq_poly_t modulus,
1415                const fq_nmod_mpoly_ctx_t smctx, n_fq_bpoly_t A,
1416                const fq_nmod_mpoly_ctx_t lgctx, const bad_fq_nmod_embed_t emb);
1417
1418 void fq_nmod_mpolyn_interp_reduce_lg_mpolyn(fq_nmod_mpolyn_t E,
1419                const fq_nmod_mpoly_ctx_t ectx, fq_nmod_mpolyn_t A, slong var,
1420                     const fq_nmod_mpoly_ctx_t ctx, const bad_fq_nmod_embed_t emb);
1421
1422 void fq_nmod_mpolyn_interp_lift_lg_mpolyn(slong * lastdeg_,
1423                          fq_nmod_mpolyn_t A, slong var,
1424                          const fq_nmod_mpoly_ctx_t ctx, fq_nmod_mpolyn_t B,
1425                    const fq_nmod_mpoly_ctx_t ectx, const bad_fq_nmod_embed_t emb);
1426
1427 int fq_nmod_mpolyn_interp_crt_lg_mpolyn(slong * lastdeg_,
1428     fq_nmod_mpolyn_t F, fq_nmod_mpolyn_t T, fq_nmod_poly_t modulus, slong var,
1429     const fq_nmod_mpoly_ctx_t ctx, fq_nmod_mpolyn_t A,
1430                   const fq_nmod_mpoly_ctx_t ectx, const bad_fq_nmod_embed_t emb);
1431
1432 void fq_nmod_mpolyun_interp_reduce_sm_mpolyu(fq_nmod_mpolyu_t B,
1433           fq_nmod_mpolyun_t A, fq_nmod_t alpha, const fq_nmod_mpoly_ctx_t ctx);
1434
1435 void fq_nmod_mpolyn_interp_lift_sm_mpoly(
1436     fq_nmod_mpolyn_t A,
1437     const fq_nmod_mpoly_t B,
1438     const fq_nmod_mpoly_ctx_t ctx);
1439
1440 void fq_nmod_mpolyun_interp_lift_sm_mpolyu(fq_nmod_mpolyun_t A,
1441                       const fq_nmod_mpolyu_t B, const fq_nmod_mpoly_ctx_t ctx);
1442
1443 int fq_nmod_mpolyun_interp_crt_sm_mpolyu(slong * lastdeg,
1444             fq_nmod_mpolyun_t F, fq_nmod_mpolyun_t T, fq_nmod_mpolyu_t A,
1445        fq_nmod_poly_t modulus, fq_nmod_t alpha, const fq_nmod_mpoly_ctx_t ctx);
1446
1447 void fq_nmod_mpolyn_interp_reduce_lg_mpoly(
1448     fq_nmod_mpoly_t A,
1449     fq_nmod_mpolyn_t B,
1450     const fq_nmod_mpoly_ctx_t ectx,
1451     const fq_nmod_mpoly_ctx_t ctx,
1452     const bad_fq_nmod_embed_t emb);
1453
1454 void fq_nmod_mpolyun_interp_reduce_lg_mpolyu(fq_nmod_mpolyu_t A,
1455                         fq_nmod_mpolyun_t B, const fq_nmod_mpoly_ctx_t ectx,
1456                     const fq_nmod_mpoly_ctx_t ctx, const bad_fq_nmod_embed_t emb);
1457
1458 void fq_nmod_mpolyn_interp_lift_lg_mpoly(fq_nmod_mpolyn_t A,
1459                             const fq_nmod_mpoly_ctx_t ctx,fq_nmod_mpoly_t B,
1460                 const fq_nmod_mpoly_ctx_t ectx, const bad_fq_nmod_embed_t emb);
1461
1462 void fq_nmod_mpolyun_interp_lift_lg_mpolyu(fq_nmod_mpolyun_t A,
1463                           const fq_nmod_mpoly_ctx_t ctx, fq_nmod_mpolyu_t B,
1464                    const fq_nmod_mpoly_ctx_t ectx, const bad_fq_nmod_embed_t emb);
1465
1466 int fq_nmod_mpolyun_interp_crt_lg_mpolyu(slong * lastdeg,
1467                 fq_nmod_mpolyun_t F, fq_nmod_mpolyun_t T, fq_nmod_poly_t m,
1468                 const fq_nmod_mpoly_ctx_t ctx, fq_nmod_mpolyu_t A,
1469                    const fq_nmod_mpoly_ctx_t ectx, const bad_fq_nmod_embed_t emb);
1470
1471 int fq_nmod_mpolyun_interp_mcrt_lg_mpolyu(slong * lastdeg,
1472                         fq_nmod_mpolyun_t H, const fq_nmod_mpoly_ctx_t ctx,
1473                         fq_nmod_poly_t m, fq_nmod_mpolyu_t A,
1474                          const fq_nmod_mpoly_ctx_t ectx, bad_fq_nmod_embed_t emb);
1475
1476 /* geobuckets ****************************************************************/
1477
1478 typedef struct fq_nmod_mpoly_geobucket
1479 {
1480     fq_nmod_mpoly_struct polys[FLINT_BITS/2];
1481     fq_nmod_mpoly_struct temps[FLINT_BITS/2];
1482     slong length;
1483 } fq_nmod_mpoly_geobucket_struct;
1484
1485 typedef fq_nmod_mpoly_geobucket_struct fq_nmod_mpoly_geobucket_t[1];
1486
1487 void fq_nmod_mpoly_geobucket_init(fq_nmod_mpoly_geobucket_t B,
1488                                                 const fq_nmod_mpoly_ctx_t ctx);
1489
1490 void fq_nmod_mpoly_geobucket_clear(fq_nmod_mpoly_geobucket_t B,
1491                                                 const fq_nmod_mpoly_ctx_t ctx);
1492
1493 void fq_nmod_mpoly_geobucket_empty(fq_nmod_mpoly_t p,
1494                    fq_nmod_mpoly_geobucket_t B, const fq_nmod_mpoly_ctx_t ctx);
1495
1496 void fq_nmod_mpoly_geobucket_fit_length(fq_nmod_mpoly_geobucket_t B,
1497                                        slong i, const fq_nmod_mpoly_ctx_t ctx);
1498
1499 void fq_nmod_mpoly_geobucket_set(fq_nmod_mpoly_geobucket_t B,
1500                              fq_nmod_mpoly_t p, const fq_nmod_mpoly_ctx_t ctx);
1501
1502 void fq_nmod_mpoly_geobucket_add(fq_nmod_mpoly_geobucket_t B,
1503                              fq_nmod_mpoly_t p, const fq_nmod_mpoly_ctx_t ctx);
1504
1505 void fq_nmod_mpoly_geobucket_sub(fq_nmod_mpoly_geobucket_t B,
1506                              fq_nmod_mpoly_t p, const fq_nmod_mpoly_ctx_t ctx);
1507
1508 /******************************************************************************
1509
1510    Internal consistency checks
1511
1512 ******************************************************************************/
1513
1514 void fq_nmod_mpoly_remainder_strongtest(const fq_nmod_mpoly_t r, const fq_nmod_mpoly_t g, const fq_nmod_mpoly_ctx_t ctx);
1515
1516 #ifdef __cplusplus
1517 }
1518 #endif
1519
1520 #endif