include/flint/fq_zech_mpoly_factor.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_FACTOR_H
0013 #define FQ_ZECH_MPOLY_FACTOR_H
0014
0015 #ifdef FQ_ZECH_MPOLY_FACTOR_INLINES_C
0016 #define FQ_ZECH_MPOLY_FACTOR_INLINE
0017 #else
0018 #define FQ_ZECH_MPOLY_FACTOR_INLINE static inline
0019 #endif
0020
0021 #include "fq_zech_mpoly.h"
0022
0023 #ifdef __cplusplus
0024  extern "C" {
0025 #endif
0026
0027 typedef struct
0028 {
0029     fq_zech_poly_struct * coeffs;
0030     slong alloc;
0031     slong length;
0032 } fq_zech_bpoly_struct;
0033
0034 typedef fq_zech_bpoly_struct fq_zech_bpoly_t[1];
0035
0036
0037 typedef struct
0038 {
0039     fq_zech_bpoly_struct * coeffs;
0040     slong alloc;
0041     slong length;
0042 } fq_zech_tpoly_struct;
0043
0044 typedef fq_zech_tpoly_struct fq_zech_tpoly_t[1];
0045
0046
0047 typedef struct
0048 {
0049     ulong * exps;
0050     fq_zech_struct * coeffs;
0051     slong length;
0052     slong alloc;
0053 } fq_zech_polyu_struct;
0054
0055 typedef fq_zech_polyu_struct fq_zech_polyu_t[1];
0056
0057
0058 typedef struct
0059 {
0060     fq_zech_poly_struct * coeffs;
0061     ulong * exps;
0062     slong length;
0063     slong alloc;
0064 } fq_zech_polyun_struct;
0065
0066 typedef fq_zech_polyun_struct fq_zech_polyun_t[1];
0067
0068
0069 /*****************************************************************************/
0070
0071 FQ_ZECH_MPOLY_FACTOR_INLINE
0072 void fq_zech_bpoly_init(fq_zech_bpoly_t A, const fq_zech_ctx_t FLINT_UNUSED(ctx))
0073 {
0074     A->coeffs = NULL;
0075     A->alloc = 0;
0076     A->length = 0;
0077 }
0078
0079 void fq_zech_bpoly_clear(fq_zech_bpoly_t A, const fq_zech_ctx_t ctx);
0080
0081 FQ_ZECH_MPOLY_FACTOR_INLINE
0082 void fq_zech_bpoly_swap(fq_zech_bpoly_t A, fq_zech_bpoly_t B, const fq_zech_ctx_t FLINT_UNUSED(ctx))
0083 {
0084     fq_zech_bpoly_struct t = *A;
0085     *A = *B;
0086     *B = t;
0087 }
0088
0089 void fq_zech_bpoly_normalise(fq_zech_bpoly_t A, const fq_zech_ctx_t ctx);
0090
0091 void fq_zech_bpoly_realloc(fq_zech_bpoly_t A, slong len, const fq_zech_ctx_t ctx);
0092
0093 FQ_ZECH_MPOLY_FACTOR_INLINE
0094 void fq_zech_bpoly_fit_length(fq_zech_bpoly_t A, slong len, const fq_zech_ctx_t ctx)
0095 {
0096     if (len > A->alloc)
0097         fq_zech_bpoly_realloc(A, len, ctx);
0098 }
0099
0100 FQ_ZECH_MPOLY_FACTOR_INLINE
0101 void fq_zech_bpoly_zero(fq_zech_bpoly_t A, const fq_zech_ctx_t FLINT_UNUSED(ctx))
0102 {
0103     A->length = 0;
0104 }
0105
0106 FQ_ZECH_MPOLY_FACTOR_INLINE
0107 int fq_zech_bpoly_is_zero(const fq_zech_bpoly_t A, const fq_zech_ctx_t FLINT_UNUSED(ctx))
0108 {
0109     return A->length == 0;
0110 }
0111
0112 int fq_zech_bpoly_equal(const fq_zech_bpoly_t A, const fq_zech_bpoly_t B, const fq_zech_ctx_t ctx);
0113
0114 void fq_zech_bpoly_get_coeff(fq_zech_t c, const fq_zech_bpoly_t A, slong e0, slong e1, const fq_zech_ctx_t ctx);
0115
0116 FQ_ZECH_MPOLY_FACTOR_INLINE
0117 slong fq_zech_bpoly_degree0(const fq_zech_bpoly_t A, const fq_zech_ctx_t FLINT_UNUSED(ctx))
0118 {
0119     return A->length - 1;
0120 }
0121
0122 slong fq_zech_bpoly_degree1(const fq_zech_bpoly_t A, const fq_zech_ctx_t FLINT_UNUSED(ctx));
0123
0124 void fq_zech_bpoly_set_poly_var1(fq_zech_bpoly_t A, const fq_zech_poly_t B, const fq_zech_ctx_t ctx);
0125
0126 void fq_zech_bpoly_set_poly_var0(fq_zech_bpoly_t A, const fq_zech_poly_t B, const fq_zech_ctx_t ctx);
0127
0128 void fq_zech_bpoly_print_pretty(const fq_zech_bpoly_t A,
0129                 const char * var0, const char * var1, const fq_zech_ctx_t ctx);
0130
0131 int fq_zech_bpoly_is_canonical(const fq_zech_bpoly_t A, const fq_zech_ctx_t ctx);
0132
0133 int fq_zech_bpoly_fq_equal(
0134     const fq_zech_bpoly_t A,
0135     const fq_zech_bpoly_t B,
0136     const fq_zech_ctx_t ctx);
0137
0138 void fq_zech_bpoly_set_coeff_fq_zech(
0139     fq_zech_bpoly_t A,
0140     slong xi,
0141     slong yi,
0142     const fq_zech_t c,
0143     const fq_zech_ctx_t ctx);
0144
0145 void fq_zech_bpoly_set_fq_zech_poly_var0(
0146     fq_zech_bpoly_t A,
0147     const fq_zech_poly_t B,
0148     const fq_zech_ctx_t ctx);
0149
0150 void fq_zech_bpoly_set_fq_zech_poly_var1(
0151     fq_zech_bpoly_t A,
0152     const fq_zech_poly_t B,
0153     const fq_zech_ctx_t ctx);
0154
0155 void fq_zech_bpoly_make_monic(
0156     fq_zech_bpoly_t A,
0157     slong order,
0158     const fq_zech_ctx_t ctx);
0159
0160 void fq_zech_bpoly_mul(
0161     fq_zech_bpoly_t A,
0162     const fq_zech_bpoly_t B,
0163     const fq_zech_bpoly_t C,
0164     const fq_zech_ctx_t ctx);
0165
0166 void fq_zech_bpoly_mul_series(
0167     fq_zech_bpoly_t A,
0168     const fq_zech_bpoly_t B,
0169     const fq_zech_bpoly_t C,
0170     slong order,
0171     const fq_zech_ctx_t ctx);
0172
0173 void fq_zech_bpoly_add(
0174     fq_zech_bpoly_t A,
0175     const fq_zech_bpoly_t B,
0176     const fq_zech_bpoly_t C,
0177     const fq_zech_ctx_t ctx);
0178
0179 void fq_zech_bpoly_one(
0180     fq_zech_bpoly_t A,
0181     const fq_zech_ctx_t ctx);
0182
0183 void fq_zech_bpoly_sub(
0184     fq_zech_bpoly_t A,
0185     const fq_zech_bpoly_t B,
0186     const fq_zech_bpoly_t C,
0187     const fq_zech_ctx_t ctx);
0188
0189 void fq_zech_bpoly_derivative(
0190     fq_zech_bpoly_t A,
0191     const fq_zech_bpoly_t B,
0192     const fq_zech_ctx_t ctx);
0193
0194 void fq_zech_bpoly_divrem_series(
0195     fq_zech_bpoly_t Q,
0196     fq_zech_bpoly_t R,
0197     const fq_zech_bpoly_t A,
0198     const fq_zech_bpoly_t B,
0199     slong order,
0200     const fq_zech_ctx_t ctx);
0201
0202 int fq_zech_bpoly_divides(
0203     fq_zech_bpoly_t Q,
0204     const fq_zech_bpoly_t A,
0205     const fq_zech_bpoly_t B,
0206     const fq_zech_ctx_t ctx);
0207
0208 void fq_zech_bpoly_set(
0209     fq_zech_bpoly_t A,
0210     const fq_zech_bpoly_t B,
0211     const fq_zech_ctx_t ctx);
0212
0213 void fq_zech_bpoly_make_primitive(
0214     fq_zech_poly_t g,
0215     fq_zech_bpoly_t A,
0216     const fq_zech_ctx_t ctx);
0217
0218 void fq_zech_bpoly_taylor_shift_var1(
0219     fq_zech_bpoly_t A,
0220     const fq_zech_bpoly_t B,
0221     const fq_zech_t c_,
0222     const fq_zech_ctx_t ctx);
0223
0224 void fq_zech_bpoly_taylor_shift_var0(
0225     fq_zech_bpoly_t A,
0226     const fq_zech_t alpha,
0227     const fq_zech_ctx_t ctx);
0228
0229 void fq_zech_mpoly_get_fq_zech_bpoly(
0230     fq_zech_bpoly_t A,
0231     const fq_zech_mpoly_t B,
0232     slong varx,
0233     slong vary,
0234     const fq_zech_mpoly_ctx_t ctx);
0235
0236 void fq_zech_mpoly_set_fq_zech_bpoly(
0237     fq_zech_mpoly_t A,
0238     flint_bitcnt_t Abits,
0239     const fq_zech_bpoly_t B,
0240     slong varx,
0241     slong vary,
0242     const fq_zech_mpoly_ctx_t ctx);
0243
0244
0245 int fq_zech_bpoly_factor_smprime(
0246     fq_zech_poly_t c,
0247     fq_zech_tpoly_t F,
0248     fq_zech_bpoly_t B,
0249     int allow_shift,
0250     const fq_zech_ctx_t ctx);
0251
0252 int fq_zech_bpoly_factor_lgprime(
0253     fq_zech_poly_t c,
0254     fq_zech_tpoly_t F,
0255     fq_zech_bpoly_t B,
0256     const fq_zech_ctx_t ctx,
0257     flint_rand_t state);
0258
0259 /*****************************************************************************/
0260
0261 FQ_ZECH_MPOLY_FACTOR_INLINE
0262 void fq_zech_tpoly_init(fq_zech_tpoly_t A, const fq_zech_ctx_t FLINT_UNUSED(ctx))
0263 {
0264     A->coeffs = NULL;
0265     A->alloc = 0;
0266     A->length = 0;
0267 }
0268
0269 FQ_ZECH_MPOLY_FACTOR_INLINE
0270 void fq_zech_tpoly_swap(fq_zech_tpoly_t A, fq_zech_tpoly_t B, const fq_zech_ctx_t FLINT_UNUSED(ctx))
0271 {
0272     fq_zech_tpoly_struct t = *A;
0273     *A = *B;
0274     *B = t;
0275 }
0276
0277 void fq_zech_tpoly_fit_length(fq_zech_tpoly_t A, slong len, const fq_zech_ctx_t ctx);
0278
0279 void fq_zech_tpoly_clear(fq_zech_tpoly_t A, const fq_zech_ctx_t ctx);
0280
0281
0282 /*****************************************************************************/
0283
0284 FQ_ZECH_MPOLY_FACTOR_INLINE
0285 void fq_zech_polyu_init(fq_zech_polyu_t A, const fq_zech_ctx_t FLINT_UNUSED(ctx))
0286 {
0287     A->coeffs = NULL;
0288     A->exps = NULL;
0289     A->length = 0;
0290     A->alloc = 0;
0291 }
0292
0293 void fq_zech_polyu_clear(fq_zech_polyu_t A, const fq_zech_ctx_t FLINT_UNUSED(ctx));
0294
0295 void fq_zech_polyu_realloc(fq_zech_polyu_t A, slong len, const fq_zech_ctx_t ctx);
0296
0297 FQ_ZECH_MPOLY_FACTOR_INLINE
0298 void fq_zech_polyu_fit_length(fq_zech_polyu_t A, slong len, const fq_zech_ctx_t ctx)
0299 {
0300     FLINT_ASSERT(A->alloc >= 0);
0301     if (len > A->alloc)
0302         fq_zech_polyu_realloc(A, len, ctx);
0303 }
0304
0305 FQ_ZECH_MPOLY_FACTOR_INLINE
0306 void fq_zech_polyu_swap(fq_zech_polyu_t A, fq_zech_polyu_t B, const fq_zech_ctx_t FLINT_UNUSED(ctx))
0307 {
0308     fq_zech_polyu_struct t = *B;
0309     *B = *A;
0310     *A = t;
0311 }
0312
0313 void fq_zech_polyu3_print_pretty(
0314     const fq_zech_polyu_t A,
0315     const char * var0,
0316     const char * var1,
0317     const char * var2,
0318     const fq_zech_ctx_t ctx);
0319
0320 void fq_zech_polyu3_degrees(
0321     slong * deg0,
0322     slong * deg1,
0323     slong * deg2,
0324     const fq_zech_polyu_t A);
0325
0326 int fq_zech_polyu_is_canonical(
0327     const fq_zech_polyu_t A,
0328     const fq_zech_ctx_t ctx);
0329
0330 /*****************************************************************************/
0331
0332 FQ_ZECH_MPOLY_FACTOR_INLINE
0333 void fq_zech_polyun_init(fq_zech_polyun_t A, const fq_zech_ctx_t FLINT_UNUSED(ctx))
0334 {
0335     A->coeffs = NULL;
0336     A->exps = NULL;
0337     A->length = 0;
0338     A->alloc = 0;
0339 }
0340
0341 void fq_zech_polyun_clear(fq_zech_polyun_t A, const fq_zech_ctx_t ctx);
0342
0343 void fq_zech_polyun_realloc(fq_zech_polyun_t A, slong len, const fq_zech_ctx_t ctx);
0344
0345 FQ_ZECH_MPOLY_FACTOR_INLINE
0346 void fq_zech_polyun_fit_length(fq_zech_polyun_t A, slong len, const fq_zech_ctx_t ctx)
0347 {
0348     if (len > A->alloc)
0349         fq_zech_polyun_realloc(A, len, ctx);
0350 }
0351
0352 FQ_ZECH_MPOLY_FACTOR_INLINE
0353 void fq_zech_polyun_swap(fq_zech_polyun_t A, fq_zech_polyun_t B, const fq_zech_ctx_t FLINT_UNUSED(ctx))
0354 {
0355     fq_zech_polyun_struct t = *B;
0356     *B = *A;
0357     *A = t;
0358 }
0359
0360 void fq_zech_polyu2n_print_pretty(
0361     const fq_zech_polyun_t A,
0362     const char * var0,
0363     const char * var1,
0364     const char * varlast,
0365     const fq_zech_ctx_t ctx);
0366
0367 void fq_zech_polyu3n_print_pretty(
0368     const fq_zech_polyun_t A,
0369     const char * var0,
0370     const char * var1,
0371     const char * var2,
0372     const char * varlast,
0373     const fq_zech_ctx_t ctx);
0374
0375 int fq_zech_polyun_is_canonical(
0376     const fq_zech_polyun_t A,
0377     const fq_zech_ctx_t ctx);
0378
0379 /*****************************************************************************/
0380
0381 int fq_zech_mpoly_is_fq_zech_poly(
0382     const fq_zech_mpoly_t A,
0383     slong var,
0384     const fq_zech_mpoly_ctx_t ctx);
0385
0386 int fq_zech_mpoly_get_fq_zech_poly(
0387     fq_zech_poly_t A,
0388     const fq_zech_mpoly_t B,
0389     slong var,
0390     const fq_zech_mpoly_ctx_t ctx);
0391
0392 void _fq_zech_mpoly_set_fq_zech_poly(
0393     fq_zech_mpoly_t A,
0394     flint_bitcnt_t Abits,
0395     const fq_zech_struct * Bcoeffs,
0396     slong Blen,
0397     slong var,
0398     const fq_zech_mpoly_ctx_t ctx);
0399
0400 void fq_zech_mpoly_set_fq_zech_poly(
0401     fq_zech_mpoly_t A,
0402     const fq_zech_poly_t B,
0403     slong var,
0404     const fq_zech_mpoly_ctx_t ctx);
0405
0406 /*****************************************************************************/
0407
0408 typedef struct {
0409     fq_zech_t constant;
0410     fq_zech_mpoly_struct * poly;
0411     fmpz * exp;
0412     slong num;
0413     slong alloc;
0414 } fq_zech_mpoly_factor_struct;
0415
0416 typedef fq_zech_mpoly_factor_struct fq_zech_mpoly_factor_t[1];
0417
0418 void fq_zech_mpoly_factor_init(fq_zech_mpoly_factor_t f,
0419                                                 const fq_zech_mpoly_ctx_t ctx);
0420
0421 void fq_zech_mpoly_factor_realloc(fq_zech_mpoly_factor_t f,
0422                                    slong alloc, const fq_zech_mpoly_ctx_t ctx);
0423
0424 void fq_zech_mpoly_factor_fit_length(fq_zech_mpoly_factor_t f,
0425                                      slong len, const fq_zech_mpoly_ctx_t ctx);
0426
0427 void fq_zech_mpoly_factor_clear(fq_zech_mpoly_factor_t f,
0428                                                 const fq_zech_mpoly_ctx_t ctx);
0429
0430 void fq_zech_mpoly_factor_set(fq_zech_mpoly_factor_t a,
0431                 const fq_zech_mpoly_factor_t b, const fq_zech_mpoly_ctx_t ctx);
0432
0433 void fq_zech_mpoly_factor_print_pretty(const fq_zech_mpoly_factor_t f,
0434                             const char ** vars, const fq_zech_mpoly_ctx_t ctx);
0435
0436 void fq_zech_mpoly_factor_append_ui(fq_zech_mpoly_factor_t f,
0437               const fq_zech_mpoly_t A, ulong e, const fq_zech_mpoly_ctx_t ctx);
0438
0439 void fq_zech_mpoly_factor_append_fmpz(fq_zech_mpoly_factor_t f,
0440        const fq_zech_mpoly_t A, const fmpz_t e, const fq_zech_mpoly_ctx_t ctx);
0441
0442 int fq_zech_mpoly_factor_squarefree(fq_zech_mpoly_factor_t f,
0443                        const fq_zech_mpoly_t A, const fq_zech_mpoly_ctx_t ctx);
0444
0445 int fq_zech_mpoly_factor(fq_zech_mpoly_factor_t f,
0446                        const fq_zech_mpoly_t A, const fq_zech_mpoly_ctx_t ctx);
0447
0448 FQ_ZECH_MPOLY_FACTOR_INLINE
0449 void fq_zech_mpoly_factor_swap(fq_zech_mpoly_factor_t A,
0450                        fq_zech_mpoly_factor_t B, const fq_zech_mpoly_ctx_t FLINT_UNUSED(ctx))
0451 {
0452    fq_zech_mpoly_factor_struct t = *A;
0453    *A = *B;
0454    *B = t;
0455 }
0456
0457 void fq_zech_mpoly_factor_one(fq_zech_mpoly_factor_t a, const fq_zech_mpoly_ctx_t ctx);
0458
0459 int fq_zech_mpoly_factor_expand(fq_zech_mpoly_t A,
0460                 const fq_zech_mpoly_factor_t f, const fq_zech_mpoly_ctx_t ctx);
0461
0462
0463 FQ_ZECH_MPOLY_FACTOR_INLINE
0464 int fq_zech_mpoly_factor_matches(const fq_zech_mpoly_t a, const fq_zech_mpoly_factor_t f, const fq_zech_mpoly_ctx_t ctx)
0465 {
0466     int matches;
0467     fq_zech_mpoly_t t;
0468     fq_zech_mpoly_init(t, ctx);
0469     fq_zech_mpoly_factor_expand(t, f, ctx);
0470     matches = fq_zech_mpoly_equal(t, a, ctx);
0471     fq_zech_mpoly_clear(t, ctx);
0472     return matches;
0473 }
0474
0475 void _fq_zech_mpoly_get_lead0(
0476     fq_zech_mpoly_t c,
0477     const fq_zech_mpoly_t A,
0478     const fq_zech_mpoly_ctx_t ctx);
0479
0480 void _fq_zech_mpoly_set_lead0(
0481     fq_zech_mpoly_t A,
0482     const fq_zech_mpoly_t B,
0483     const fq_zech_mpoly_t c,
0484     const fq_zech_mpoly_ctx_t ctx);
0485
0486 /*****************************************************************************/
0487
0488 typedef struct
0489 {
0490     fq_zech_mpoly_struct * coeffs;
0491     slong alloc;
0492     slong length;
0493 } fq_zech_mpolyv_struct;
0494
0495 typedef fq_zech_mpolyv_struct fq_zech_mpolyv_t[1];
0496
0497 FQ_ZECH_MPOLY_FACTOR_INLINE
0498 void fq_zech_mpolyv_init(fq_zech_mpolyv_t A, const fq_zech_mpoly_ctx_t FLINT_UNUSED(ctx))
0499 {
0500     A->coeffs = NULL;
0501     A->alloc = 0;
0502     A->length = 0;
0503 }
0504
0505 FQ_ZECH_MPOLY_FACTOR_INLINE
0506 void fq_zech_mpolyv_swap(fq_zech_mpolyv_t A, fq_zech_mpolyv_t B,
0507                                                  const fq_zech_mpoly_ctx_t FLINT_UNUSED(ctx))
0508 {
0509    fq_zech_mpolyv_struct t = *A;
0510    *A = *B;
0511    *B = t;
0512 }
0513
0514 void fq_zech_mpolyv_clear(fq_zech_mpolyv_t A,
0515                                                 const fq_zech_mpoly_ctx_t ctx);
0516
0517 void fq_zech_mpolyv_print_pretty(const fq_zech_mpolyv_t poly,
0518                                const char ** x, const fq_zech_mpoly_ctx_t ctx);
0519
0520 void fq_zech_mpolyv_fit_length(fq_zech_mpolyv_t A, slong length,
0521                                                 const fq_zech_mpoly_ctx_t ctx);
0522
0523 void fq_zech_mpolyv_set_coeff(
0524     fq_zech_mpolyv_t A,
0525     slong i,
0526     fq_zech_mpoly_t c,
0527     const fq_zech_mpoly_ctx_t ctx);
0528
0529 void fq_zech_mpoly_to_mpolyv(
0530     fq_zech_mpolyv_t A,
0531     const fq_zech_mpoly_t B,
0532     const fq_zech_mpoly_t xalpha,
0533     const fq_zech_mpoly_ctx_t ctx);
0534
0535 void fq_zech_mpoly_from_mpolyv(
0536     fq_zech_mpoly_t A,
0537     const fq_zech_mpolyv_t B,
0538     const fq_zech_mpoly_t xalpha,
0539     const fq_zech_mpoly_ctx_t ctx);
0540
0541 /*****************************************************************************/
0542
0543 int fq_zech_mpoly_univar_content_mpoly(
0544     fq_zech_mpoly_t g,
0545     const fq_zech_mpoly_univar_t A,
0546     const fq_zech_mpoly_ctx_t ctx);
0547
0548 void fq_zech_mpoly_univar_divexact_mpoly(
0549     fq_zech_mpoly_univar_t A,
0550     const fq_zech_mpoly_t b,
0551     const fq_zech_mpoly_ctx_t ctx);
0552
0553 /*****************************************************************************/
0554
0555 int fq_zech_mpoly_factor_lcc_wang(
0556     fq_zech_mpoly_struct * lc_divs,
0557     const fq_zech_mpoly_factor_t lcAfac,
0558     const fq_zech_poly_t Auc,
0559     const fq_zech_bpoly_struct * Auf,
0560     slong r,
0561     const fq_zech_poly_struct * alpha,
0562     const fq_zech_mpoly_ctx_t ctx);
0563
0564 int fq_zech_mpoly_factor_irred_smprime_zassenhaus(
0565     fq_zech_mpolyv_t fac,
0566     const fq_zech_mpoly_t A,
0567     const fq_zech_mpoly_ctx_t ctx,
0568     flint_rand_t state);
0569
0570 int fq_zech_mpoly_factor_irred_lgprime_zassenhaus(
0571     fq_zech_mpolyv_t fac,
0572     const fq_zech_mpoly_t A,
0573     const fq_zech_mpoly_ctx_t ctx,
0574     flint_rand_t state);
0575
0576 int fq_zech_mpoly_factor_irred_smprime_wang(
0577     fq_zech_mpolyv_t fac,
0578     const fq_zech_mpoly_t A,
0579     const fq_zech_mpoly_factor_t lcAfac,
0580     const fq_zech_mpoly_t lcA,
0581     const fq_zech_mpoly_ctx_t ctx,
0582     flint_rand_t state);
0583
0584 int fq_zech_mpoly_factor_irred_lgprime_wang(
0585     fq_zech_mpolyv_t Af,
0586     const fq_zech_mpoly_t A,
0587     const fq_zech_mpoly_factor_t lcAfac,
0588     const fq_zech_mpoly_t lcA,
0589     const fq_zech_mpoly_ctx_t ctx,
0590     flint_rand_t state);
0591
0592 int fq_zech_mpoly_factor_irred_smprime_zippel(
0593     fq_zech_mpolyv_t fac,
0594     const fq_zech_mpoly_t A,
0595     const fq_zech_mpoly_factor_t lcAfac,
0596     const fq_zech_mpoly_t lcA,
0597     const fq_zech_mpoly_ctx_t ctx,
0598     flint_rand_t state);
0599
0600 int fq_zech_mpoly_factor_irred_lgprime_zippel(
0601     fq_zech_mpolyv_t Af,
0602     const fq_zech_mpoly_t A,
0603     const fq_zech_mpoly_factor_t lcAfac,
0604     const fq_zech_mpoly_t lcA,
0605     const fq_zech_mpoly_ctx_t ctx,
0606     flint_rand_t state);
0607
0608 /*****************************************************************************/
0609
0610 typedef struct {
0611     flint_bitcnt_t bits;
0612     slong w;
0613     slong r;
0614     fq_zech_poly_struct * inv_prod_dbetas;
0615     fq_zech_mpoly_struct * inv_prod_dbetas_mvar;
0616     fq_zech_poly_struct * dbetas;
0617     fq_zech_mpoly_struct * dbetas_mvar;
0618     fq_zech_mpoly_struct * prod_mbetas;
0619     fq_zech_mpolyv_struct * prod_mbetas_coeffs;
0620     fq_zech_mpoly_struct * mbetas;
0621     fq_zech_mpoly_struct * deltas;
0622     fq_zech_mpoly_struct * xalpha;
0623     fq_zech_mpoly_struct * q;
0624     fq_zech_mpoly_struct * qt;
0625     fq_zech_mpoly_struct * newt;
0626     fq_zech_mpolyv_struct * delta_coeffs;
0627     fq_zech_mpoly_t T;
0628     fq_zech_mpoly_t Q;
0629     fq_zech_mpoly_t R;
0630 } fq_zech_mpoly_pfrac_struct;
0631
0632 typedef fq_zech_mpoly_pfrac_struct fq_zech_mpoly_pfrac_t[1];
0633
0634
0635 int fq_zech_mpoly_pfrac_init(
0636     fq_zech_mpoly_pfrac_t Iv,
0637     flint_bitcnt_t bits,
0638     slong l, slong r,
0639     const fq_zech_mpoly_struct * betas,
0640     const fq_zech_struct * alpha,
0641     const fq_zech_mpoly_ctx_t ctx);
0642
0643 void fq_zech_mpoly_pfrac_clear(
0644     fq_zech_mpoly_pfrac_t Iv,
0645     const fq_zech_mpoly_ctx_t ctx);
0646
0647 int fq_zech_mpoly_pfrac(
0648     slong r,
0649     fq_zech_mpoly_t t,
0650     const slong * deg,
0651     fq_zech_mpoly_pfrac_t Iv,
0652     const fq_zech_mpoly_ctx_t ctx);
0653
0654 int fq_zech_mpoly_hlift(
0655     slong m,
0656     fq_zech_mpoly_struct * f, /* length r */
0657     slong r,
0658     const fq_zech_struct * alpha,
0659     const fq_zech_mpoly_t A,
0660     const slong * degs,
0661     const fq_zech_mpoly_ctx_t ctx);
0662
0663 int fq_zech_bpoly_hlift2(
0664     fq_zech_bpoly_t A, /* clobbered (shifted by alpha) */
0665     fq_zech_bpoly_t B0,
0666     fq_zech_bpoly_t B1,
0667     const fq_zech_t alpha,
0668     slong degree_inner, /* required degree in x */
0669     const fq_zech_ctx_t ctx);
0670
0671 int fq_zech_bpoly_hlift(
0672     slong r,
0673     fq_zech_bpoly_t A, /* clobbered (shifted by alpha) */
0674     fq_zech_bpoly_struct * B,
0675     const fq_zech_t alpha,
0676     slong degree_inner, /* required degree in x */
0677     const fq_zech_ctx_t ctx);
0678
0679 int fq_zech_polyu3_hlift(
0680     slong r,
0681     fq_zech_polyun_struct * BB,
0682     fq_zech_polyu_t A,
0683     fq_zech_polyu_struct * B,
0684     const fq_zech_t beta,
0685     slong degree_inner, /* required degree in x */
0686     const fq_zech_ctx_t ctx);
0687
0688 int fq_zech_mpoly_factor_algo(fq_zech_mpoly_factor_t f,
0689     const fq_zech_mpoly_t A, const fq_zech_mpoly_ctx_t ctx, unsigned int algo);
0690
0691 int fq_zech_mpoly_factor_zassenhaus(fq_zech_mpoly_factor_t f,
0692                        const fq_zech_mpoly_t A, const fq_zech_mpoly_ctx_t ctx);
0693
0694 int fq_zech_mpoly_factor_wang(fq_zech_mpoly_factor_t f,
0695                        const fq_zech_mpoly_t A, const fq_zech_mpoly_ctx_t ctx);
0696
0697 int fq_zech_mpoly_factor_zippel(fq_zech_mpoly_factor_t f,
0698                        const fq_zech_mpoly_t A, const fq_zech_mpoly_ctx_t ctx);
0699
0700 void fq_zech_poly_product_roots_fq_zech(
0701     fq_zech_poly_t master,
0702     const fq_zech_struct * monomials,
0703     slong mlength,
0704     const fq_zech_ctx_t ctx);
0705
0706 void _fq_zech_mpoly_monomial_evals(
0707     fq_zech_struct * E,
0708     const ulong * Aexps,
0709     flint_bitcnt_t Abits,
0710     slong Alen,
0711     const fq_zech_struct * alpha,
0712     slong vstart,
0713     const fq_zech_mpoly_ctx_t ctx);
0714
0715 int _fq_zech_mpoly_eval_rest_fq_zech_poly(
0716     fq_zech_poly_struct * E,
0717     slong * starts,
0718     slong * ends,
0719     slong * stops,
0720     ulong * es,
0721     const fq_zech_struct * Acoeffs,
0722     const ulong * Aexps,
0723     slong Alen,
0724     slong var,
0725     const fq_zech_poly_struct * alphas,
0726     const slong * offsets,
0727     const slong * shifts,
0728     slong N,
0729     ulong mask,
0730     slong nvars,
0731     const fq_zech_ctx_t ctx);
0732
0733 void _fq_zech_mpoly_eval_to_bpoly(
0734     fq_zech_bpoly_t E,
0735     const fq_zech_mpoly_t A,
0736     const fq_zech_poly_struct * alphabetas,
0737     const fq_zech_mpoly_ctx_t ctx);
0738
0739 void _fq_zech_mpoly_set_fq_zech_bpoly_var1_zero(
0740     fq_zech_mpoly_t A,
0741     flint_bitcnt_t Abits,
0742     const fq_zech_bpoly_t B,
0743     slong var,
0744     const fq_zech_mpoly_ctx_t ctx);
0745
0746 /* misc **********************************************************************/
0747
0748 int fq_zech_next(fq_zech_t x, const fq_zech_ctx_t FLINT_UNUSED(ctx));
0749
0750 #ifdef __cplusplus
0751 }
0752 #endif
0753
0754 #endif