include/flint/fq_zech_mpoly.h

0001 /*
0002     Copyright (C) 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 FQ_ZECH_MPOLY_H
0013 #define FQ_ZECH_MPOLY_H
0014
0015 #ifdef FQ_ZECH_MPOLY_INLINES_C
0016 #define FQ_ZECH_MPOLY_INLINE
0017 #else
0018 #define FQ_ZECH_MPOLY_INLINE static inline
0019 #endif
0020
0021 #include "fq_zech_types.h"
0022 #include "fq_nmod_types.h"
0023 #include "mpoly_types.h"
0024
0025 #ifdef __cplusplus
0026  extern "C" {
0027 #endif
0028
0029 FQ_ZECH_MPOLY_INLINE
0030 nmod_t fq_zech_ctx_mod(const fq_zech_ctx_t ctx)
0031 {
0032     return ctx->fq_nmod_ctx->mod;
0033 }
0034
0035
0036 /*  Type definitions *********************************************************/
0037
0038 /*
0039     context object for fq_zech_mpoly
0040 */
0041 typedef struct
0042 {
0043     mpoly_ctx_t minfo;
0044     fq_zech_ctx_t fqctx;
0045 } fq_zech_mpoly_ctx_struct;
0046
0047 typedef fq_zech_mpoly_ctx_struct fq_zech_mpoly_ctx_t[1];
0048
0049 /*
0050     fq_zech_mpoly_t
0051     sparse multivariates with fq_zech coefficients
0052 */
0053 typedef struct
0054 {
0055     fq_zech_struct * coeffs;
0056     ulong * exps;
0057     slong alloc;
0058     slong length;
0059     flint_bitcnt_t bits;     /* number of bits per exponent */
0060 } fq_zech_mpoly_struct;
0061
0062 typedef fq_zech_mpoly_struct fq_zech_mpoly_t[1];
0063
0064 /* Internal type definitions *************************************************/
0065
0066 /*
0067     fq_zech_mpoly_univar_t
0068     sparse univariates with multivariate coefficients
0069 */
0070 typedef struct
0071 {
0072    fq_zech_mpoly_struct * coeffs; /* multivariate coefficients */
0073    fmpz * exps;
0074    slong alloc;
0075    slong length;
0076 } fq_zech_mpoly_univar_struct;
0077
0078 typedef fq_zech_mpoly_univar_struct fq_zech_mpoly_univar_t[1];
0079
0080 /*
0081     fq_zech_mpolyu_t
0082     sparse univariates with fq_zech_mpoly_t coefficients
0083         with uniform bits and LEX ordering
0084 */
0085 typedef struct
0086 {
0087    fq_zech_mpoly_struct * coeffs;
0088    ulong * exps;
0089    slong alloc;
0090    slong length;
0091    flint_bitcnt_t bits;    /* default bits to construct coeffs */
0092 } fq_zech_mpolyu_struct;
0093
0094 typedef fq_zech_mpolyu_struct fq_zech_mpolyu_t[1];
0095
0096 /*
0097     fq_zech_mpolyn_t
0098     multivariates with fq_zech_poly_t coefficients
0099 */
0100 typedef struct
0101 {
0102    fq_zech_poly_struct * coeffs;
0103    ulong * exps;
0104    slong alloc;
0105    slong length;
0106    slong bits;
0107 } fq_zech_mpolyn_struct;
0108 typedef fq_zech_mpolyn_struct fq_zech_mpolyn_t[1];
0109
0110 /*
0111     fq_zech_mpolyun_t
0112     sparse univariates with fq_zech_mpolyn_t coefficients
0113         with uniform bits and LEX ordering
0114 */
0115 typedef struct
0116 {
0117     fq_zech_mpolyn_struct * coeffs;
0118     ulong * exps;
0119     slong alloc;
0120     slong length;
0121     flint_bitcnt_t bits;   /* default bits to construct coeffs */
0122 } fq_zech_mpolyun_struct;
0123
0124 typedef fq_zech_mpolyun_struct fq_zech_mpolyun_t[1];
0125
0126 /*
0127     fq_zech_mpoly_geobucket_t
0128     power of 4 increment
0129 */
0130 typedef struct fq_zech_mpoly_geobucket
0131 {
0132     fq_zech_mpoly_struct polys[FLINT_BITS/2];
0133     slong length;
0134 } fq_zech_mpoly_geobucket_struct;
0135
0136 typedef fq_zech_mpoly_geobucket_struct fq_zech_mpoly_geobucket_t[1];
0137
0138
0139 /* Context object ************************************************************/
0140
0141 void fq_zech_mpoly_ctx_init_deg(fq_zech_mpoly_ctx_t ctx, slong nvars,
0142                                  const ordering_t ord, ulong p, slong deg);
0143
0144 void fq_zech_mpoly_ctx_clear(fq_zech_mpoly_ctx_t ctx);
0145
0146 FQ_ZECH_MPOLY_INLINE
0147 slong fq_zech_mpoly_ctx_nvars(const fq_zech_mpoly_ctx_t ctx)
0148 {
0149     return ctx->minfo->nvars;
0150 }
0151
0152 FQ_ZECH_MPOLY_INLINE
0153 ordering_t fq_zech_mpoly_ctx_ord(const fq_zech_mpoly_ctx_t ctx)
0154 {
0155     return ctx->minfo->ord;
0156 }
0157
0158
0159 /*  Memory management ********************************************************/
0160
0161 void fq_zech_mpoly_init(fq_zech_mpoly_t A,
0162                                                 const fq_zech_mpoly_ctx_t ctx);
0163
0164 void fq_zech_mpoly_init2(fq_zech_mpoly_t A, slong alloc,
0165                                                 const fq_zech_mpoly_ctx_t ctx);
0166
0167 void fq_zech_mpoly_init3(fq_zech_mpoly_t A, slong alloc,
0168                               flint_bitcnt_t bits, const fq_zech_mpoly_ctx_t ctx);
0169
0170 void fq_zech_mpoly_realloc(fq_zech_mpoly_t A,
0171                                    slong alloc, const fq_zech_mpoly_ctx_t ctx);
0172
0173 void fq_zech_mpoly_fit_length(fq_zech_mpoly_t A, slong length,
0174                                                 const fq_zech_mpoly_ctx_t ctx);
0175
0176 void _fq_zech_mpoly_fit_length(fq_zech_struct ** coeff,
0177                               ulong ** exps, slong * alloc, slong len, slong N,
0178                                                     const fq_zech_ctx_t fqctx);
0179
0180 void fq_zech_mpoly_fit_length_reset_bits(fq_zech_mpoly_t A,
0181                 slong len, flint_bitcnt_t bits, const fq_zech_mpoly_ctx_t ctx);
0182
0183 void fq_zech_mpoly_clear(fq_zech_mpoly_t A,
0184                                                 const fq_zech_mpoly_ctx_t ctx);
0185
0186 FQ_ZECH_MPOLY_INLINE
0187 void _fq_zech_mpoly_set_length(fq_zech_mpoly_t A, slong newlen,
0188                                                  const fq_zech_mpoly_ctx_t FLINT_UNUSED(ctx))
0189 {
0190     FLINT_ASSERT(newlen <= A->alloc);
0191     A->length = newlen;
0192 }
0193
0194 FQ_ZECH_MPOLY_INLINE
0195 void fq_zech_mpoly_truncate(fq_zech_mpoly_t A, slong newlen,
0196                                                  const fq_zech_mpoly_ctx_t FLINT_UNUSED(ctx))
0197 {
0198     if (A->length > newlen)
0199     {
0200         A->length = newlen;
0201     }
0202 }
0203
0204 void fq_zech_mpoly_fit_bits(fq_zech_mpoly_t A, slong bits, const fq_zech_mpoly_ctx_t ctx);
0205
0206 /* Input/output **************************************************************/
0207
0208 int fq_zech_mpoly_set_str_pretty(fq_zech_mpoly_t A, const char * str,
0209                                const char ** x, const fq_zech_mpoly_ctx_t ctx);
0210
0211 char * fq_zech_mpoly_get_str_pretty(const fq_zech_mpoly_t A,
0212                                const char ** x, const fq_zech_mpoly_ctx_t ctx);
0213
0214 #ifdef FLINT_HAVE_FILE
0215 int fq_zech_mpoly_fprint_pretty(FILE * file, const fq_zech_mpoly_t A, const char ** x, const fq_zech_mpoly_ctx_t ctx);
0216 #endif
0217
0218 int fq_zech_mpoly_print_pretty(const fq_zech_mpoly_t A, const char ** x, const fq_zech_mpoly_ctx_t ctx);
0219
0220 /*  Basic manipulation *******************************************************/
0221
0222 void fq_zech_mpoly_gen(fq_zech_mpoly_t A, slong var,
0223                                                 const fq_zech_mpoly_ctx_t ctx);
0224
0225 int fq_zech_mpoly_is_gen(const fq_zech_mpoly_t A,
0226                                      slong var, const fq_zech_mpoly_ctx_t ctx);
0227
0228 void fq_zech_mpoly_set(fq_zech_mpoly_t A, const fq_zech_mpoly_t B,
0229                                                 const fq_zech_mpoly_ctx_t ctx);
0230
0231 int fq_zech_mpoly_equal(const fq_zech_mpoly_t A, const fq_zech_mpoly_t B,
0232                                                 const fq_zech_mpoly_ctx_t ctx);
0233
0234 FQ_ZECH_MPOLY_INLINE
0235 void fq_zech_mpoly_swap(fq_zech_mpoly_t A, fq_zech_mpoly_t B,
0236                                                  const fq_zech_mpoly_ctx_t FLINT_UNUSED(ctx))
0237 {
0238     FLINT_SWAP(fq_zech_mpoly_struct, *A, *B);
0239 }
0240
0241
0242 /* Constants *****************************************************************/
0243
0244 int fq_zech_mpoly_is_fq_zech(const fq_zech_mpoly_t A,
0245                                                 const fq_zech_mpoly_ctx_t ctx);
0246
0247 void fq_zech_mpoly_get_fq_zech(fq_zech_t c, const fq_zech_mpoly_t A,
0248                                                 const fq_zech_mpoly_ctx_t ctx);
0249
0250 void fq_zech_mpoly_set_fq_zech(fq_zech_mpoly_t A,
0251                              const fq_zech_t c, const fq_zech_mpoly_ctx_t ctx);
0252
0253 void fq_zech_mpoly_set_ui(fq_zech_mpoly_t A, ulong c,
0254                                                 const fq_zech_mpoly_ctx_t ctx);
0255
0256 void fq_zech_mpoly_set_fq_zech_gen(fq_zech_mpoly_t A,
0257                                                 const fq_zech_mpoly_ctx_t ctx);
0258
0259 int fq_zech_mpoly_equal_fq_zech(const fq_zech_mpoly_t A,
0260                              const fq_zech_t c, const fq_zech_mpoly_ctx_t ctx);
0261
0262 FQ_ZECH_MPOLY_INLINE
0263 void fq_zech_mpoly_zero(fq_zech_mpoly_t A, const fq_zech_mpoly_ctx_t ctx)
0264 {
0265    _fq_zech_mpoly_set_length(A, 0, ctx);
0266 }
0267
0268 FQ_ZECH_MPOLY_INLINE
0269 void fq_zech_mpoly_one(fq_zech_mpoly_t A, const fq_zech_mpoly_ctx_t ctx)
0270 {
0271     fq_zech_mpoly_set_ui(A, 1, ctx);
0272 }
0273
0274 FQ_ZECH_MPOLY_INLINE
0275 int fq_zech_mpoly_is_zero(const fq_zech_mpoly_t A, const fq_zech_mpoly_ctx_t FLINT_UNUSED(ctx))
0276 {
0277    return A->length == 0;
0278 }
0279
0280 int fq_zech_mpoly_is_one(const fq_zech_mpoly_t A,
0281                                                 const fq_zech_mpoly_ctx_t ctx);
0282
0283
0284 /* Degrees *******************************************************************/
0285
0286 int fq_zech_mpoly_degrees_fit_si(const fq_zech_mpoly_t A, const fq_zech_mpoly_ctx_t ctx);
0287
0288 void fq_zech_mpoly_degrees_fmpz(fmpz ** degs, const fq_zech_mpoly_t A, const fq_zech_mpoly_ctx_t ctx);
0289 void fq_zech_mpoly_degrees_si(slong * degs, const fq_zech_mpoly_t A, const fq_zech_mpoly_ctx_t ctx);
0290
0291 void fq_zech_mpoly_degree_fmpz(fmpz_t deg, const fq_zech_mpoly_t A, slong var, const fq_zech_mpoly_ctx_t ctx);
0292 slong fq_zech_mpoly_degree_si(const fq_zech_mpoly_t A, slong var, const fq_zech_mpoly_ctx_t ctx);
0293
0294 int fq_zech_mpoly_total_degree_fits_si(const fq_zech_mpoly_t A, const fq_zech_mpoly_ctx_t ctx);
0295
0296 void fq_zech_mpoly_total_degree_fmpz(fmpz_t td, const fq_zech_mpoly_t A, const fq_zech_mpoly_ctx_t ctx);
0297 slong fq_zech_mpoly_total_degree_si(const fq_zech_mpoly_t A, const fq_zech_mpoly_ctx_t ctx);
0298
0299 /* Coefficients **************************************************************/
0300
0301 void fq_zech_mpoly_get_coeff_fq_zech_monomial(fq_zech_t c,
0302                           const fq_zech_mpoly_t A, const fq_zech_mpoly_t M,
0303                                                 const fq_zech_mpoly_ctx_t ctx);
0304
0305 void fq_zech_mpoly_set_coeff_fq_zech_monomial(fq_zech_mpoly_t A,
0306                                   const fq_zech_t c, const fq_zech_mpoly_t M,
0307                                                 const fq_zech_mpoly_ctx_t ctx);
0308
0309 void fq_zech_mpoly_get_coeff_fq_zech_fmpz(fq_zech_t c,
0310                              const fq_zech_mpoly_t A, fmpz * const * exp,
0311                                                 const fq_zech_mpoly_ctx_t ctx);
0312
0313 void fq_zech_mpoly_get_coeff_fq_zech_ui(fq_zech_t c,
0314                                 const fq_zech_mpoly_t A, const ulong * exp,
0315                                                const fq_zech_mpoly_ctx_t ctx);
0316
0317 void _fq_zech_mpoly_set_coeff_fq_zech_fmpz(fq_zech_mpoly_t A,
0318                                        const fq_zech_t c, const fmpz * exp,
0319                                                 const fq_zech_mpoly_ctx_t ctx);
0320
0321 void fq_zech_mpoly_set_coeff_fq_zech_fmpz(fq_zech_mpoly_t A,
0322                                      const fq_zech_t c, fmpz * const * exp,
0323                                                 const fq_zech_mpoly_ctx_t ctx);
0324
0325 void fq_zech_mpoly_set_coeff_fq_zech_ui(fq_zech_mpoly_t A,
0326                                       const fq_zech_t c, const ulong * exp,
0327                                                 const fq_zech_mpoly_ctx_t ctx);
0328
0329 void fq_zech_mpoly_get_coeff_vars_ui(fq_zech_mpoly_t C,
0330               const fq_zech_mpoly_t A, const slong * vars, const ulong * exps,
0331                                   slong length, const fq_zech_mpoly_ctx_t ctx);
0332
0333 FQ_ZECH_MPOLY_INLINE fq_zech_struct * fq_zech_mpoly_leadcoeff(
0334                         const fq_zech_mpoly_t A, const fq_zech_mpoly_ctx_t FLINT_UNUSED(ctx))
0335 {
0336     FLINT_ASSERT(A->length > 0);
0337     return A->coeffs + 0;
0338 }
0339
0340
0341 /* comparison ****************************************************************/
0342
0343 int fq_zech_mpoly_cmp(const fq_zech_mpoly_t A, const fq_zech_mpoly_t B,
0344                                                 const fq_zech_mpoly_ctx_t ctx);
0345
0346
0347 /* container operations ******************************************************/
0348
0349 int fq_zech_mpoly_is_canonical(const fq_zech_mpoly_t A,
0350                                                 const fq_zech_mpoly_ctx_t ctx);
0351
0352 FQ_ZECH_MPOLY_INLINE
0353 slong fq_zech_mpoly_length(const fq_zech_mpoly_t A, const fq_zech_mpoly_ctx_t FLINT_UNUSED(ctx))
0354 {
0355     return A->length;
0356 }
0357
0358 void fq_zech_mpoly_resize(fq_zech_mpoly_t A, slong new_length,
0359                                                 const fq_zech_mpoly_ctx_t ctx);
0360
0361 void fq_zech_mpoly_get_term_coeff_fq_zech(fq_zech_t c,
0362               const fq_zech_mpoly_t A, slong i, const fq_zech_mpoly_ctx_t ctx);
0363
0364 void fq_zech_mpoly_set_term_coeff_fq_zech(fq_zech_mpoly_t A,
0365                     slong i, const fq_zech_t c, const fq_zech_mpoly_ctx_t ctx);
0366
0367 int fq_zech_mpoly_term_exp_fits_ui(const fq_zech_mpoly_t A, slong i, const fq_zech_mpoly_ctx_t ctx);
0368 int fq_zech_mpoly_term_exp_fits_si(const fq_zech_mpoly_t A, slong i, const fq_zech_mpoly_ctx_t ctx);
0369
0370 void fq_zech_mpoly_get_term_exp_fmpz(fmpz ** exp,
0371               const fq_zech_mpoly_t A, slong i, const fq_zech_mpoly_ctx_t ctx);
0372
0373 void fq_zech_mpoly_get_term_exp_ui(ulong * exp,
0374               const fq_zech_mpoly_t A, slong i, const fq_zech_mpoly_ctx_t ctx);
0375
0376 void fq_zech_mpoly_get_term_exp_si(slong * exp,
0377               const fq_zech_mpoly_t A, slong i, const fq_zech_mpoly_ctx_t ctx);
0378
0379 ulong fq_zech_mpoly_get_term_var_exp_ui(const fq_zech_mpoly_t A,
0380                             slong i, slong var, const fq_zech_mpoly_ctx_t ctx);
0381
0382 slong fq_zech_mpoly_get_term_var_exp_si(const fq_zech_mpoly_t A,
0383                             slong i, slong var, const fq_zech_mpoly_ctx_t ctx);
0384
0385 void fq_zech_mpoly_set_term_exp_fmpz(fq_zech_mpoly_t A,
0386                    slong i, fmpz * const * exp, const fq_zech_mpoly_ctx_t ctx);
0387
0388 void fq_zech_mpoly_set_term_exp_ui(fq_zech_mpoly_t A,
0389                     slong i, const ulong * exp, const fq_zech_mpoly_ctx_t ctx);
0390
0391 void fq_zech_mpoly_get_term(fq_zech_mpoly_t M, const fq_zech_mpoly_t A,
0392                                        slong i, const fq_zech_mpoly_ctx_t ctx);
0393
0394 void fq_zech_mpoly_get_term_monomial(fq_zech_mpoly_t M,
0395               const fq_zech_mpoly_t A, slong i, const fq_zech_mpoly_ctx_t ctx);
0396
0397 void fq_zech_mpoly_push_term_fq_zech_fmpz(fq_zech_mpoly_t A,
0398          const fq_zech_t c, fmpz * const * exp, const fq_zech_mpoly_ctx_t ctx);
0399
0400 void fq_zech_mpoly_push_term_fq_zech_ui(fq_zech_mpoly_t A,
0401           const fq_zech_t c, const ulong * exp, const fq_zech_mpoly_ctx_t ctx);
0402
0403 void fq_zech_mpoly_sort_terms(fq_zech_mpoly_t A,
0404                                                 const fq_zech_mpoly_ctx_t ctx);
0405
0406 void fq_zech_mpoly_combine_like_terms(fq_zech_mpoly_t A,
0407                                                 const fq_zech_mpoly_ctx_t ctx);
0408
0409 void fq_zech_mpoly_reverse(fq_zech_mpoly_t A, const fq_zech_mpoly_t B,
0410                                                 const fq_zech_mpoly_ctx_t ctx);
0411
0412 void fq_zech_mpoly_assert_canonical(const fq_zech_mpoly_t A,
0413                                                 const fq_zech_mpoly_ctx_t ctx);
0414
0415 void _fq_zech_mpoly_radix_sort1(fq_zech_mpoly_t A, slong left,
0416                  slong right, flint_bitcnt_t pos, ulong cmpmask, ulong totalmask);
0417
0418 void _fq_zech_mpoly_radix_sort(fq_zech_mpoly_t A, slong left,
0419                        slong right, flint_bitcnt_t pos, slong N, ulong * cmpmask);
0420
0421 void _fq_zech_mpoly_push_exp_ffmpz(fq_zech_mpoly_t A,
0422                               const fmpz * exp, const fq_zech_mpoly_ctx_t ctx);
0423
0424 void _fq_zech_mpoly_push_exp_pfmpz(fq_zech_mpoly_t A,
0425                             fmpz * const * exp, const fq_zech_mpoly_ctx_t ctx);
0426
0427 void _fq_zech_mpoly_push_exp_ui(fq_zech_mpoly_t A,
0428                              const ulong * exp, const fq_zech_mpoly_ctx_t ctx);
0429
0430
0431 /* Random generation *********************************************************/
0432
0433 void fq_zech_mpoly_randtest_bound(fq_zech_mpoly_t A, flint_rand_t state,
0434                  slong length, ulong exp_bound, const fq_zech_mpoly_ctx_t ctx);
0435
0436 void fq_zech_mpoly_randtest_bounds(fq_zech_mpoly_t A, flint_rand_t state,
0437               slong length, ulong * exp_bounds, const fq_zech_mpoly_ctx_t ctx);
0438
0439 void fq_zech_mpoly_randtest_bits(fq_zech_mpoly_t A, flint_rand_t state,
0440             slong length, flint_bitcnt_t exp_bits, const fq_zech_mpoly_ctx_t ctx);
0441
0442
0443 /* Addition/Subtraction ******************************************************/
0444
0445 slong _fq_zech_mpoly_add(
0446                          fq_zech_struct * coeff1,       ulong * exp1,
0447                          fq_zech_struct * coeff2, const ulong * exp2, slong len2,
0448                          fq_zech_struct * coeff3, const ulong * exp3, slong len3,
0449                    slong N, const ulong * cmpmask, const fq_zech_ctx_t fqctx);
0450
0451 void fq_zech_mpoly_add_fq_zech(fq_zech_mpoly_t A,
0452                             const fq_zech_mpoly_t B, const fq_zech_t C,
0453                                                 const fq_zech_mpoly_ctx_t ctx);
0454
0455 void fq_zech_mpoly_sub_fq_zech(fq_zech_mpoly_t A,
0456                             const fq_zech_mpoly_t B, const fq_zech_t C,
0457                                                 const fq_zech_mpoly_ctx_t ctx);
0458
0459 void fq_zech_mpoly_add(fq_zech_mpoly_t A,
0460                             const fq_zech_mpoly_t B, const fq_zech_mpoly_t C,
0461                                                 const fq_zech_mpoly_ctx_t ctx);
0462
0463 void fq_zech_mpoly_sub(fq_zech_mpoly_t A,
0464                             const fq_zech_mpoly_t B, const fq_zech_mpoly_t C,
0465                                                 const fq_zech_mpoly_ctx_t ctx);
0466
0467
0468 /* Scalar operations *********************************************************/
0469
0470 void fq_zech_mpoly_neg(fq_zech_mpoly_t A,
0471                        const fq_zech_mpoly_t B, const fq_zech_mpoly_ctx_t ctx);
0472
0473 void fq_zech_mpoly_scalar_mul_fq_zech(fq_zech_mpoly_t A,
0474     const fq_zech_mpoly_t B, const fq_zech_t c, const fq_zech_mpoly_ctx_t ctx);
0475
0476 void fq_zech_mpoly_make_monic(fq_zech_mpoly_t A,
0477                        const fq_zech_mpoly_t B, const fq_zech_mpoly_ctx_t ctx);
0478
0479 void fq_zech_mpoly_scalar_addmul_fq_zech(fq_zech_mpoly_t A,
0480          const fq_zech_mpoly_t B, const fq_zech_mpoly_t C, const fq_zech_t d,
0481                                                 const fq_zech_mpoly_ctx_t ctx);
0482
0483 /* Differentiation **********************************************************/
0484
0485 void fq_zech_mpoly_derivative(fq_zech_mpoly_t A,
0486             const fq_zech_mpoly_t B, slong var, const fq_zech_mpoly_ctx_t ctx);
0487
0488
0489 /* Evaluation ****************************************************************/
0490
0491 void fq_zech_mpoly_evaluate_one_fq_zech(fq_zech_mpoly_t A,
0492                     const fq_zech_mpoly_t B, slong var, const fq_zech_t val,
0493                                                 const fq_zech_mpoly_ctx_t ctx);
0494
0495 void _fq_zech_mpoly_eval_all_fq_zech(fq_zech_t eval,
0496                const fq_zech_struct * Acoeffs, const ulong * Aexps, slong Alen,
0497                     flint_bitcnt_t Abits, fq_zech_struct * const * alphas,
0498                             const mpoly_ctx_t mctx, const fq_zech_ctx_t fqctx);
0499
0500 void fq_zech_mpoly_evaluate_all_fq_zech(fq_zech_t ev, const fq_zech_mpoly_t A,
0501                  fq_zech_struct * const * vals, const fq_zech_mpoly_ctx_t ctx);
0502
0503 int fq_zech_mpoly_compose_fq_zech_poly(fq_zech_poly_t A,
0504                      const fq_zech_mpoly_t B, fq_zech_poly_struct * const * C,
0505                                                 const fq_zech_mpoly_ctx_t ctx);
0506
0507 void _fq_zech_mpoly_compose_mat(fq_zech_mpoly_t A,
0508                             const fq_zech_mpoly_t B, const fmpz_mat_t M,
0509               const fq_zech_mpoly_ctx_t ctxB, const fq_zech_mpoly_ctx_t ctxAC);
0510
0511 int fq_zech_mpoly_compose_fq_zech_mpoly_geobucket(fq_zech_mpoly_t A,
0512               const fq_zech_mpoly_t B, fq_zech_mpoly_struct * const * C,
0513               const fq_zech_mpoly_ctx_t ctxB, const fq_zech_mpoly_ctx_t ctxAC);
0514
0515 int fq_zech_mpoly_compose_fq_zech_mpoly_horner(fq_zech_mpoly_t A,
0516               const fq_zech_mpoly_t B, fq_zech_mpoly_struct * const * C,
0517               const fq_zech_mpoly_ctx_t ctxB, const fq_zech_mpoly_ctx_t ctxAC);
0518
0519 int fq_zech_mpoly_compose_fq_zech_mpoly(fq_zech_mpoly_t A,
0520               const fq_zech_mpoly_t B, fq_zech_mpoly_struct * const * C,
0521               const fq_zech_mpoly_ctx_t ctxB, const fq_zech_mpoly_ctx_t ctxAC);
0522
0523 void fq_zech_mpoly_compose_fq_zech_mpoly_gen(fq_zech_mpoly_t A,
0524                              const fq_zech_mpoly_t B, const slong * c,
0525               const fq_zech_mpoly_ctx_t ctxB, const fq_zech_mpoly_ctx_t ctxAC);
0526
0527
0528 /* Multiplication ************************************************************/
0529
0530 void fq_zech_mpoly_mul(fq_zech_mpoly_t A, const fq_zech_mpoly_t B,
0531                        const fq_zech_mpoly_t C, const fq_zech_mpoly_ctx_t ctx);
0532
0533 void fq_zech_mpoly_mul_johnson(fq_zech_mpoly_t poly1,
0534                     const fq_zech_mpoly_t poly2, const fq_zech_mpoly_t poly3,
0535                                                 const fq_zech_mpoly_ctx_t ctx);
0536
0537 slong _fq_zech_mpoly_mul_johnson(
0538                     fq_zech_struct ** coeff1, ulong ** exp1, slong * alloc,
0539              const fq_zech_struct * coeff2, const ulong * exp2, slong len2,
0540              const fq_zech_struct * coeff3, const ulong * exp3, slong len3,
0541   flint_bitcnt_t bits, slong N, const ulong * cmpmask, const fq_zech_ctx_t fqctx);
0542
0543
0544 /* Powering ******************************************************************/
0545
0546 int fq_zech_mpoly_pow_fmpz(fq_zech_mpoly_t A, const fq_zech_mpoly_t B,
0547                                 const fmpz_t k, const fq_zech_mpoly_ctx_t ctx);
0548
0549 int fq_zech_mpoly_pow_ui(fq_zech_mpoly_t A, const fq_zech_mpoly_t B,
0550                                        ulong k, const fq_zech_mpoly_ctx_t ctx);
0551
0552
0553 /* Division ******************************************************************/
0554
0555 int fq_zech_mpoly_divides(fq_zech_mpoly_t Q,
0556                          const fq_zech_mpoly_t A, const fq_zech_mpoly_t B,
0557                                                 const fq_zech_mpoly_ctx_t ctx);
0558
0559 void fq_zech_mpoly_div(fq_zech_mpoly_t Q,
0560                             const fq_zech_mpoly_t A, const fq_zech_mpoly_t B,
0561                                                 const fq_zech_mpoly_ctx_t ctx);
0562
0563 void fq_zech_mpoly_divrem(fq_zech_mpoly_t Q, fq_zech_mpoly_t R,
0564                             const fq_zech_mpoly_t A, const fq_zech_mpoly_t B,
0565                                                 const fq_zech_mpoly_ctx_t ctx);
0566
0567 void fq_zech_mpoly_divrem_ideal(fq_zech_mpoly_struct ** Q,
0568                                   fq_zech_mpoly_t R, const fq_zech_mpoly_t A,
0569                                   fq_zech_mpoly_struct * const * B, slong len,
0570                                                 const fq_zech_mpoly_ctx_t ctx);
0571
0572 int fq_zech_mpoly_divides_monagan_pearce(fq_zech_mpoly_t poly1,
0573                   const fq_zech_mpoly_t poly2, const fq_zech_mpoly_t poly3,
0574                                                 const fq_zech_mpoly_ctx_t ctx);
0575
0576 void fq_zech_mpoly_div_monagan_pearce(fq_zech_mpoly_t q,
0577                       const fq_zech_mpoly_t poly2, const fq_zech_mpoly_t poly3,
0578                                                 const fq_zech_mpoly_ctx_t ctx);
0579
0580 void fq_zech_mpoly_divrem_monagan_pearce(fq_zech_mpoly_t q, fq_zech_mpoly_t r,
0581                       const fq_zech_mpoly_t poly2, const fq_zech_mpoly_t poly3,
0582                                                 const fq_zech_mpoly_ctx_t ctx);
0583
0584 void fq_zech_mpoly_divrem_ideal_monagan_pearce(
0585                         fq_zech_mpoly_struct ** q, fq_zech_mpoly_t r,
0586             const fq_zech_mpoly_t poly2, fq_zech_mpoly_struct * const * poly3,
0587                                       slong len, const fq_zech_mpoly_ctx_t ctx);
0588
0589 /* GCD ***********************************************************************/
0590
0591 int fq_zech_mpoly_gcd(fq_zech_mpoly_t G, const fq_zech_mpoly_t A,
0592                        const fq_zech_mpoly_t B, const fq_zech_mpoly_ctx_t ctx);
0593
0594 int _fq_zech_mpoly_gcd(fq_zech_mpoly_t G, flint_bitcnt_t Gbits,
0595                             const fq_zech_mpoly_t A, const fq_zech_mpoly_t B,
0596                                                 const fq_zech_mpoly_ctx_t ctx);
0597
0598 int fq_zech_mpoly_gcd_cofactors(fq_zech_mpoly_t G,
0599           fq_zech_mpoly_t Abar, fq_zech_mpoly_t Bbar, const fq_zech_mpoly_t A,
0600                        const fq_zech_mpoly_t B, const fq_zech_mpoly_ctx_t ctx);
0601
0602 int _fq_zech_mpoly_gcd_cofactors(
0603                                 fq_zech_mpoly_t G, flint_bitcnt_t Gbits,
0604                                 fq_zech_mpoly_t Abar, flint_bitcnt_t Abarbits,
0605                                 fq_zech_mpoly_t Bbar, flint_bitcnt_t Bbarbits,
0606                              const fq_zech_mpoly_t A, const fq_zech_mpoly_t B,
0607                                                 const fq_zech_mpoly_ctx_t ctx);
0608
0609 int fq_zech_mpoly_gcd_brown(fq_zech_mpoly_t G,
0610                             const fq_zech_mpoly_t A, const fq_zech_mpoly_t B,
0611                                                 const fq_zech_mpoly_ctx_t ctx);
0612
0613 int fq_zech_mpoly_gcd_zippel(fq_zech_mpoly_t G, const fq_zech_mpoly_t A,
0614                        const fq_zech_mpoly_t B, const fq_zech_mpoly_ctx_t ctx);
0615
0616 void fq_zech_mpoly_deflation(fmpz * shift, fmpz * stride,
0617                        const fq_zech_mpoly_t A, const fq_zech_mpoly_ctx_t ctx);
0618
0619 void fq_zech_mpoly_deflate(fq_zech_mpoly_t A, const fq_zech_mpoly_t B,
0620           const fmpz * shift, const fmpz * stride, const fq_zech_mpoly_ctx_t ctx);
0621
0622 void fq_zech_mpoly_inflate(fq_zech_mpoly_t A, const fq_zech_mpoly_t B,
0623        const fmpz * shift, const fmpz * stride, const fq_zech_mpoly_ctx_t ctx);
0624
0625
0626 /* Univariates ***************************************************************/
0627
0628 void fq_zech_mpoly_univar_init(fq_zech_mpoly_univar_t A,
0629                                                 const fq_zech_mpoly_ctx_t FLINT_UNUSED(ctx));
0630
0631 void fq_zech_mpoly_univar_clear(fq_zech_mpoly_univar_t A,
0632                                                 const fq_zech_mpoly_ctx_t ctx);
0633
0634 void fq_zech_mpoly_univar_fit_length(fq_zech_mpoly_univar_t A,
0635                                   slong length, const fq_zech_mpoly_ctx_t ctx);
0636
0637 void fq_zech_mpoly_univar_print_pretty(const fq_zech_mpoly_univar_t A,
0638                                const char ** x, const fq_zech_mpoly_ctx_t ctx);
0639
0640 void fq_zech_mpoly_univar_assert_canonical(fq_zech_mpoly_univar_t A,
0641                                                 const fq_zech_mpoly_ctx_t ctx);
0642
0643 void fq_zech_mpoly_to_univar(fq_zech_mpoly_univar_t A,
0644             const fq_zech_mpoly_t B, slong var, const fq_zech_mpoly_ctx_t ctx);
0645
0646 void fq_zech_mpoly_from_univar_bits(fq_zech_mpoly_t A, flint_bitcnt_t Abits,
0647      const fq_zech_mpoly_univar_t B, slong var, const fq_zech_mpoly_ctx_t ctx);
0648
0649 void fq_zech_mpoly_from_univar(fq_zech_mpoly_t A,
0650      const fq_zech_mpoly_univar_t B, slong var, const fq_zech_mpoly_ctx_t ctx);
0651
0652 FQ_ZECH_MPOLY_INLINE
0653 void fq_zech_mpoly_univar_swap(fq_zech_mpoly_univar_t A,
0654                        fq_zech_mpoly_univar_t B, const fq_zech_mpoly_ctx_t FLINT_UNUSED(ctx))
0655 {
0656     FLINT_SWAP(fq_zech_mpoly_univar_struct, *A, *B);
0657 }
0658
0659 int fq_zech_mpoly_univar_degree_fits_si(const fq_zech_mpoly_univar_t A, const fq_zech_mpoly_ctx_t FLINT_UNUSED(ctx));
0660
0661 FQ_ZECH_MPOLY_INLINE
0662 slong fq_zech_mpoly_univar_length(const fq_zech_mpoly_univar_t A,
0663                                                  const fq_zech_mpoly_ctx_t FLINT_UNUSED(ctx))
0664 {
0665     return A->length;
0666 }
0667
0668 slong fq_zech_mpoly_univar_get_term_exp_si(fq_zech_mpoly_univar_t A, slong i, const fq_zech_mpoly_ctx_t FLINT_UNUSED(ctx));
0669
0670 FQ_ZECH_MPOLY_INLINE
0671 void fq_zech_mpoly_univar_get_term_coeff(fq_zech_mpoly_t c,
0672         const fq_zech_mpoly_univar_t A, slong i, const fq_zech_mpoly_ctx_t ctx)
0673 {
0674     FLINT_ASSERT((ulong)i < (ulong)A->length);
0675     fq_zech_mpoly_set(c, A->coeffs + i, ctx);
0676 }
0677
0678 FQ_ZECH_MPOLY_INLINE
0679 void fq_zech_mpoly_univar_swap_term_coeff(fq_zech_mpoly_t c,
0680               fq_zech_mpoly_univar_t A, slong i, const fq_zech_mpoly_ctx_t ctx)
0681 {
0682     FLINT_ASSERT((ulong)i < (ulong)A->length);
0683     fq_zech_mpoly_swap(c, A->coeffs + i, ctx);
0684 }
0685
0686
0687 /******************************************************************************
0688
0689    Internal functions (guaranteed to change without notice)
0690
0691 ******************************************************************************/
0692
0693
0694 int _fq_zech_mpoly_get_nmod_mpoly(
0695     nmod_mpoly_t s,
0696     const nmod_mpoly_ctx_t sctx,
0697     const fq_zech_mpoly_t t,
0698     const fq_zech_mpoly_ctx_t tctx);
0699
0700 void _fq_zech_mpoly_set_nmod_mpoly(
0701     fq_zech_mpoly_t A,
0702     const fq_zech_mpoly_ctx_t Actx,
0703     const nmod_mpoly_t B,
0704     const nmod_mpoly_ctx_t Bctx);
0705
0706 void fq_zech_mpolyl_lead_coeff(
0707     fq_zech_mpoly_t c,
0708     const fq_zech_mpoly_t A,
0709     slong num_vars,
0710     const fq_zech_mpoly_ctx_t ctx);
0711
0712 void fq_zech_mpoly_pow_rmul(fq_zech_mpoly_t A, const fq_zech_mpoly_t B,
0713                                        ulong k, const fq_zech_mpoly_ctx_t ctx);
0714
0715 int fq_zech_mpoly_repack_bits_inplace(fq_zech_mpoly_t A,
0716                          flint_bitcnt_t Abits, const fq_zech_mpoly_ctx_t ctx);
0717
0718
0719 void fq_zech_mpoly_ctx_change_modulus(fq_zech_mpoly_ctx_t ctx,
0720                                                                     slong deg);
0721
0722 void _fq_zech_mpoly_get_fq_nmod_mpoly(
0723     fq_nmod_mpoly_t A,
0724     const fq_nmod_mpoly_ctx_t ctxA,
0725     const fq_zech_mpoly_t B,
0726     const fq_zech_mpoly_ctx_t ctxB);
0727
0728 void _fq_zech_mpoly_set_fq_nmod_mpoly(
0729     fq_zech_mpoly_t A,
0730     const fq_zech_mpoly_ctx_t ctxA,
0731     const fq_nmod_mpoly_t B,
0732     const fq_nmod_mpoly_ctx_t ctxB);
0733
0734
0735 /* mpolyu ********************************************************************/
0736
0737 int fq_zech_mpolyu_is_canonical(const fq_zech_mpolyu_t poly,
0738                                                 const fq_zech_mpoly_ctx_t ctx);
0739
0740 void fq_zech_mpolyu_init(fq_zech_mpolyu_t A, flint_bitcnt_t bits,
0741                                                 const fq_zech_mpoly_ctx_t FLINT_UNUSED(ctx));
0742
0743 void fq_zech_mpolyu_clear(fq_zech_mpolyu_t A,
0744                                                const fq_zech_mpoly_ctx_t uctx);
0745
0746 void fq_zech_mpolyu_swap(fq_zech_mpolyu_t A, fq_zech_mpolyu_t B);
0747
0748 void fq_zech_mpolyu_zero(fq_zech_mpolyu_t A,
0749                                                const fq_zech_mpoly_ctx_t uctx);
0750
0751 int fq_zech_mpolyu_is_one(fq_zech_mpolyu_t A,
0752                                                const fq_zech_mpoly_ctx_t uctx);
0753
0754 void fq_zech_mpolyu_print_pretty(const fq_zech_mpolyu_t poly,
0755                                const char ** x, const fq_zech_mpoly_ctx_t ctx);
0756
0757 void fq_zech_mpolyu_fit_length(fq_zech_mpolyu_t A, slong length,
0758                                                const fq_zech_mpoly_ctx_t uctx);
0759
0760 void fq_zech_mpolyu_one(fq_zech_mpolyu_t A,
0761                                                const fq_zech_mpoly_ctx_t uctx);
0762
0763 #ifdef __cplusplus
0764 }
0765 #endif
0766
0767 #endif