Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2026-11-07 10:15:30 

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 N_POLY_H
0013 #define N_POLY_H
0014 
0015 #include "nmod_types.h"
0016 #include "nmod_vec.h"
0017 #include "nmod_poly.h"
0018 #include "fq_nmod_types.h"
0019 #include "n_poly_types.h"
0020 
0021 #ifdef __cplusplus
0022 extern "C" {
0023 #endif
0024 
0025 #if !defined(FQ_NMOD_H)
0026 # define fq_nmod_ctx_degree(ctx) ((ctx)->modulus->length - 1)
0027 #endif
0028 
0029 typedef struct
0030 {
0031     n_polyun_struct ** array;
0032     slong alloc;
0033     slong top;
0034 } n_polyun_stack_struct;
0035 
0036 typedef n_polyun_stack_struct n_polyun_stack_t[1];
0037 
0038 typedef struct {
0039     n_poly_stack_t poly_stack;
0040     n_polyun_stack_t polyun_stack;
0041 } n_poly_polyun_stack_struct;
0042 
0043 typedef n_poly_polyun_stack_struct n_poly_polyun_stack_t[1];
0044 
0045 /* n_poly ********************************************************************/
0046 
0047 FLINT_FORCE_INLINE
0048 void n_poly_init(n_poly_t A)
0049 {
0050     A->length = 0;
0051     A->alloc = 0;
0052     A->coeffs = NULL;
0053 }
0054 FLINT_FORCE_INLINE
0055 void n_poly_init2(n_poly_t A, slong alloc)
0056 {
0057     A->length = 0;
0058     A->alloc = alloc;
0059     A->coeffs = NULL;
0060     if (alloc > 0)
0061         A->coeffs = (ulong *) flint_malloc(alloc*sizeof(ulong));
0062 }
0063 FLINT_FORCE_INLINE
0064 void n_poly_clear(n_poly_t A)
0065 {
0066     FLINT_ASSERT(A->alloc != 0 || A->coeffs == NULL);
0067     if (A->alloc > 0)
0068         flint_free(A->coeffs);
0069 }
0070 void n_poly_realloc(n_poly_t A, slong len);
0071 int n_poly_is_canonical(const n_poly_t A);
0072 
0073 FLINT_FORCE_INLINE
0074 void n_poly_swap(n_poly_t A, n_poly_t B)
0075 {
0076     FLINT_SWAP(n_poly_struct, *A, *B);
0077 }
0078 
0079 FLINT_FORCE_INLINE
0080 slong n_poly_degree(const n_poly_t A)
0081 {
0082     FLINT_ASSERT(A->length >= 0);
0083     return A->length - 1;
0084 }
0085 
0086 FLINT_FORCE_INLINE
0087 void n_poly_fit_length(n_poly_t A, slong len)
0088 {
0089     if (len > A->alloc)
0090         n_poly_realloc(A, len);
0091 }
0092 
0093 FLINT_FORCE_INLINE
0094 void _n_poly_normalise(n_poly_t A)
0095 {
0096     while (A->length > 0 && A->coeffs[A->length - 1] == 0)
0097         A->length--;
0098 }
0099 
0100 FLINT_FORCE_INLINE
0101 void n_poly_truncate(n_poly_t poly, slong len)
0102 {
0103     if (poly->length > len)
0104     {
0105         poly->length = len;
0106         _n_poly_normalise(poly);
0107     }
0108 }
0109 
0110 void n_poly_reverse(n_poly_t output, const n_poly_t input, slong m);
0111 
0112 FLINT_FORCE_INLINE
0113 ulong n_poly_lead(const n_poly_t A)
0114 {
0115     FLINT_ASSERT(A->length > 0);
0116     return A->coeffs[A->length - 1];
0117 }
0118 
0119 FLINT_FORCE_INLINE void n_poly_zero(n_poly_t res) { res->length = 0; }
0120 FLINT_FORCE_INLINE
0121 void n_poly_one(n_poly_t A)
0122 {
0123     n_poly_fit_length(A, 1);
0124     A->length = 1;
0125     A->coeffs[0] = 1;
0126 }
0127 
0128 FLINT_FORCE_INLINE
0129 void n_poly_set_ui(n_poly_t A, ulong c)
0130 {
0131     n_poly_fit_length(A, 1);
0132     A->coeffs[0] = c;
0133     A->length = (c != 0);
0134 }
0135 FLINT_FORCE_INLINE
0136 void n_poly_set(n_poly_t A, const n_poly_t B)
0137 {
0138     n_poly_fit_length(A, B->length);
0139     _nmod_vec_set(A->coeffs, B->coeffs, B->length);
0140     A->length = B->length;
0141 }
0142 
0143 FLINT_FORCE_INLINE
0144 int n_poly_is_zero(const n_poly_t poly) { return poly->length == 0; }
0145 FLINT_FORCE_INLINE
0146 int n_poly_is_one(const n_poly_t A) { return A->length == 1 && A->coeffs[0] == 1; }
0147 FLINT_FORCE_INLINE
0148 int n_poly_equal(const n_poly_t a, const n_poly_t b)
0149 {
0150     if (a->length != b->length)
0151         return 0;
0152     if (a != b && !_nmod_vec_equal(a->coeffs, b->coeffs, a->length))
0153         return 0;
0154     return 1;
0155 }
0156 
0157 FLINT_FORCE_INLINE
0158 void nmod_poly_mock(nmod_poly_t a, const n_poly_t b, nmod_t mod)
0159 {
0160     a->coeffs = b->coeffs;
0161     a->length = b->length;
0162     a->alloc = b->alloc;
0163     a->mod = mod;
0164 }
0165 
0166 FLINT_FORCE_INLINE
0167 void n_poly_mock(n_poly_t a, const nmod_poly_t b)
0168 {
0169     a->coeffs = b->coeffs;
0170     a->length = b->length;
0171     a->alloc = b->alloc;
0172 }
0173 
0174 FLINT_FORCE_INLINE
0175 ulong n_poly_get_coeff(const n_poly_t poly, slong j)
0176 {
0177     return (j >= poly->length) ? 0 : poly->coeffs[j];
0178 }
0179 
0180 FLINT_FORCE_INLINE
0181 void n_poly_set_coeff_nonzero(n_poly_t A, slong j, ulong c)
0182 {
0183     FLINT_ASSERT(c != 0);
0184     if (j >= A->length)
0185     {
0186         n_poly_fit_length(A, j + 1);
0187         _nmod_vec_zero(A->coeffs + A->length, j - A->length);
0188         A->length = j + 1;
0189     }
0190     A->coeffs[j] = c;
0191 }
0192 
0193 void n_poly_set_coeff(n_poly_t A, slong e, ulong c);
0194 
0195 FLINT_FORCE_INLINE
0196 void n_poly_set_nmod_poly(n_poly_t a, const nmod_poly_t b)
0197 {
0198     n_poly_fit_length(a, b->length);
0199     _nmod_vec_set(a->coeffs, b->coeffs, b->length);
0200     a->length = b->length;
0201 }
0202 
0203 FLINT_FORCE_INLINE
0204 void nmod_poly_set_n_poly(nmod_poly_t a, const n_poly_t b)
0205 {
0206     nmod_poly_fit_length(a, b->length);
0207     _nmod_vec_set(a->coeffs, b->coeffs, b->length);
0208     a->length = b->length;
0209 }
0210 
0211 FLINT_FORCE_INLINE
0212 void n_poly_shift_left(n_poly_t A, const n_poly_t B, slong k)
0213 {
0214     n_poly_fit_length(A, B->length + k);
0215     _nmod_poly_shift_left(A->coeffs, B->coeffs, B->length, k);
0216     A->length = B->length + k;
0217 }
0218 FLINT_FORCE_INLINE
0219 void n_poly_shift_right(n_poly_t res, const n_poly_t poly, slong k)
0220 {
0221     if (k >= poly->length)
0222         res->length = 0;
0223     else
0224     {
0225         const slong len = poly->length - k;
0226         n_poly_fit_length(res, len);
0227         _nmod_poly_shift_right(res->coeffs, poly->coeffs, len, k);
0228         res->length = len;
0229     }
0230 }
0231 
0232 ulong _n_poly_eval_pow(n_poly_t P, n_poly_t alphapow, dot_params_t params, nmod_t ctx);
0233 
0234 void n_poly_print_pretty(const n_poly_t A, const char * x);
0235 
0236 /* n_poly modular arithmetic *************************************************/
0237 
0238 int n_poly_mod_is_canonical(const n_poly_t A, nmod_t mod);
0239 
0240 void n_poly_mod_set_coeff_ui(n_poly_t A, slong j, ulong c, nmod_t mod);
0241 
0242 FLINT_FORCE_INLINE
0243 void n_poly_mod_make_monic(n_poly_t A, const n_poly_t B, nmod_t mod)
0244 {
0245     FLINT_ASSERT(B->length > 0);
0246     n_poly_fit_length(A, B->length);
0247     A->length = B->length;
0248     _nmod_poly_make_monic(A->coeffs, B->coeffs, B->length, mod);
0249 }
0250 
0251 FLINT_FORCE_INLINE
0252 void n_poly_mod_taylor_shift(n_poly_t g, ulong c, nmod_t mod)
0253 {
0254     _nmod_poly_taylor_shift(g->coeffs, c, g->length, mod);
0255 }
0256 
0257 FLINT_FORCE_INLINE
0258 void _n_poly_mod_scalar_mul_nmod(n_poly_t A, const n_poly_t B, ulong c, nmod_t mod)
0259 {
0260     FLINT_ASSERT(B->length <= B->alloc);
0261     n_poly_fit_length(A, B->length);
0262     _nmod_vec_scalar_mul_nmod(A->coeffs, B->coeffs, B->length, c, mod);
0263     A->length = B->length;
0264 }
0265 
0266 FLINT_FORCE_INLINE
0267 void _n_poly_mod_scalar_mul_nmod_inplace(n_poly_t A, ulong c, nmod_t mod)
0268 {
0269     _nmod_vec_scalar_mul_nmod(A->coeffs, A->coeffs, A->length, c, mod);
0270 }
0271 
0272 void n_poly_mod_scalar_mul_ui(n_poly_t A, const n_poly_t B, ulong c, nmod_t ctx);
0273 
0274 ulong n_poly_mod_eval_step2(n_poly_t Acur, const n_poly_t Ainc, nmod_t mod);
0275 
0276 FLINT_FORCE_INLINE
0277 ulong n_poly_mod_evaluate_nmod(const n_poly_t A, ulong c, nmod_t mod)
0278 {
0279     return _nmod_poly_evaluate_nmod(A->coeffs, A->length, c, mod);
0280 }
0281 
0282 FLINT_FORCE_INLINE
0283 void n_poly_mod_neg(n_poly_t A, const n_poly_t B, nmod_t mod)
0284 {
0285     n_poly_fit_length(A, B->length);
0286     _nmod_vec_neg(A->coeffs, B->coeffs, B->length, mod);
0287     A->length = B->length;
0288 }
0289 
0290 void n_poly_mod_add_ui(n_poly_t res, const n_poly_t poly, ulong c, nmod_t ctx);
0291 FLINT_FORCE_INLINE
0292 void n_poly_mod_add(n_poly_t A, const n_poly_t B, const n_poly_t C, nmod_t mod)
0293 {
0294     slong Alen = FLINT_MAX(B->length, C->length);
0295     n_poly_fit_length(A, Alen);
0296     _nmod_poly_add(A->coeffs, B->coeffs, B->length, C->coeffs, C->length, mod);
0297     A->length = Alen;
0298     _n_poly_normalise(A);
0299 }
0300 
0301 FLINT_FORCE_INLINE
0302 void n_poly_mod_sub(n_poly_t A, const n_poly_t B, const n_poly_t C, nmod_t mod)
0303 {
0304     slong Alen = FLINT_MAX(B->length, C->length);
0305     n_poly_fit_length(A, Alen);
0306     _nmod_poly_sub(A->coeffs, B->coeffs, B->length, C->coeffs, C->length, mod);
0307     A->length = Alen;
0308     _n_poly_normalise(A);
0309 }
0310 
0311 FLINT_FORCE_INLINE
0312 void n_poly_mod_product_roots_nmod_vec(n_poly_t A, nn_srcptr r, slong n, nmod_t mod)
0313 {
0314     n_poly_fit_length(A, n + 1);
0315     A->length = n + 1;
0316     _nmod_poly_product_roots_nmod_vec(A->coeffs, r, n, mod);
0317 }
0318 
0319 void n_poly_mod_shift_left_scalar_addmul(n_poly_t A, slong k, ulong c, nmod_t mod);
0320 
0321 void n_poly_mod_addmul_linear(n_poly_t A, const n_poly_t B, const n_poly_t C, ulong d1, ulong d0, nmod_t mod);
0322 
0323 void n_poly_mod_scalar_addmul_nmod(n_poly_t A, const n_poly_t B, const n_poly_t C, ulong d0, nmod_t ctx);
0324 
0325 ulong n_poly_mod_eval_pow(n_poly_t P, n_poly_t alphapow, nmod_t ctx);
0326 void n_poly_mod_eval2_pow(ulong * vp, ulong * vm, const n_poly_t P, n_poly_t alphapow, nmod_t ctx);
0327 
0328 ulong n_poly_mod_div_root(n_poly_t Q, const n_poly_t A, ulong c, nmod_t ctx);
0329 
0330 FLINT_FORCE_INLINE
0331 void _n_poly_mod_mul(n_poly_t A, const n_poly_t B, const n_poly_t C, nmod_t ctx)
0332 {
0333     slong Blen = B->length;
0334     slong Clen = C->length;
0335     slong Alen = Blen + Clen - 1;
0336 
0337     FLINT_ASSERT(A != B);
0338     FLINT_ASSERT(A != C);
0339 
0340     if (Clen < 1 || Blen < 1)
0341     {
0342         A->length = 0;
0343         return;
0344     }
0345 
0346     n_poly_fit_length(A, Alen);
0347     A->length = Alen;
0348 
0349     if (Blen >= Clen)
0350         _nmod_poly_mul(A->coeffs, B->coeffs, Blen, C->coeffs, Clen, ctx);
0351     else
0352         _nmod_poly_mul(A->coeffs, C->coeffs, Clen, B->coeffs, Blen, ctx);
0353 }
0354 void n_poly_mod_mul(n_poly_t A, const n_poly_t B, const n_poly_t C, nmod_t mod);
0355 void n_poly_mod_mullow(n_poly_t A, const n_poly_t B, const n_poly_t C, slong n, nmod_t mod);
0356 FLINT_FORCE_INLINE
0357 void _n_poly_mod_div(n_poly_t Q, const n_poly_t A, const n_poly_t B, nmod_t mod)
0358 {
0359     const slong lenA = A->length, lenB = B->length;
0360     FLINT_ASSERT(lenB > 0);
0361     FLINT_ASSERT(Q != A && Q != B);
0362     if (lenA < lenB)
0363     {
0364         n_poly_zero(Q);
0365         return;
0366     }
0367     n_poly_fit_length(Q, lenA - lenB + 1);
0368     _nmod_poly_div(Q->coeffs, A->coeffs, lenA, B->coeffs, lenB, mod);
0369     Q->length = lenA - lenB + 1;
0370 }
0371 void n_poly_mod_div(n_poly_t Q, const n_poly_t A, const n_poly_t B, nmod_t mod);
0372 FLINT_FORCE_INLINE
0373 void _n_poly_mod_rem(n_poly_t R, const n_poly_t A, const n_poly_t B, nmod_t mod)
0374 {
0375     const slong lenA = A->length, lenB = B->length;
0376     FLINT_ASSERT(R != A && R != B);
0377     FLINT_ASSERT(lenB > 0);
0378     if (lenA < lenB)
0379     {
0380         n_poly_set(R, A);
0381         return;
0382     }
0383     n_poly_fit_length(R, lenB - 1);
0384     _nmod_poly_rem(R->coeffs, A->coeffs, lenA, B->coeffs, lenB, mod);
0385     R->length = lenB - 1;
0386     _n_poly_normalise(R);
0387 }
0388 void n_poly_mod_rem(n_poly_t R, const n_poly_t A, const n_poly_t B, nmod_t mod);
0389 FLINT_FORCE_INLINE
0390 void _n_poly_mod_divrem(n_poly_t Q, n_poly_t R, const n_poly_t A, const n_poly_t B, nmod_t mod)
0391 {
0392     const slong lenA = A->length, lenB = B->length;
0393 
0394     FLINT_ASSERT(lenB > 0);
0395     FLINT_ASSERT(Q != A && Q != B);
0396     FLINT_ASSERT(R != A && R != B);
0397 
0398     if (lenA < lenB)
0399     {
0400         n_poly_set(R, A);
0401         n_poly_zero(Q);
0402         return;
0403     }
0404 
0405     n_poly_fit_length(Q, lenA - lenB + 1);
0406     n_poly_fit_length(R, lenB - 1);
0407     _nmod_poly_divrem(Q->coeffs, R->coeffs, A->coeffs, lenA, B->coeffs, lenB, mod);
0408     Q->length = lenA - lenB + 1;
0409     R->length = lenB - 1;
0410     _n_poly_normalise(R);
0411 }
0412 void n_poly_mod_divrem(n_poly_t Q, n_poly_t R, const n_poly_t A, const n_poly_t B, nmod_t mod);
0413 FLINT_FORCE_INLINE
0414 void _n_poly_mod_divexact(n_poly_t Q, const n_poly_t A, const n_poly_t B, nmod_t mod)
0415 {
0416     const slong lenA = A->length, lenB = B->length;
0417     FLINT_ASSERT(lenB > 0);
0418     FLINT_ASSERT(Q != A && Q != B);
0419     if (lenA < lenB)
0420     {
0421         n_poly_zero(Q);
0422         return;
0423     }
0424     n_poly_fit_length(Q, lenA - lenB + 1);
0425     _nmod_poly_divexact(Q->coeffs, A->coeffs, lenA, B->coeffs, lenB, mod);
0426     Q->length = lenA - lenB + 1;
0427 }
0428 void n_poly_mod_divexact(n_poly_t Q, const n_poly_t A, const n_poly_t B, nmod_t mod);
0429 
0430 void n_poly_mod_pow(n_poly_t res, const n_poly_t poly, ulong e, nmod_t ctx);
0431 
0432 ulong n_poly_mod_remove(n_poly_t f, const n_poly_t p, nmod_t ctx);
0433 
0434 void n_poly_mod_mulmod_preinv(n_poly_t A, const n_poly_t B, const n_poly_t C, const n_poly_t M, const n_poly_t Minv, nmod_t ctx);
0435 void n_poly_mod_mulmod(n_poly_t res, const n_poly_t poly1, const n_poly_t poly2, const n_poly_t f, nmod_t mod);
0436 int n_poly_mod_invmod(n_poly_t A, const n_poly_t B, const n_poly_t P, nmod_t mod);
0437 
0438 void n_poly_mod_gcd(n_poly_t G, const n_poly_t A, const n_poly_t B, nmod_t mod);
0439 void n_poly_mod_xgcd(n_poly_t G, n_poly_t S, n_poly_t T, const n_poly_t A, const n_poly_t B, nmod_t mod);
0440 
0441 void n_poly_mod_inv_series(n_poly_t Qinv, const n_poly_t Q, slong n, nmod_t mod);
0442 void n_poly_mod_div_series(n_poly_t Q, const n_poly_t A, const n_poly_t B, slong order, nmod_t ctx);
0443 
0444 /* n_fq **********************************************************************/
0445 
0446 FLINT_FORCE_INLINE
0447 nmod_t fq_nmod_ctx_mod(const fq_nmod_ctx_t ctx)
0448 {
0449     return ctx->modulus->mod;
0450 }
0451 
0452 FLINT_FORCE_INLINE
0453 int _n_fq_is_zero(const ulong * a, slong d)
0454 {
0455     do {
0456         if (a[--d] != 0)
0457             return 0;
0458     } while (d > 0);
0459     return 1;
0460 }
0461 
0462 FLINT_FORCE_INLINE
0463 void _n_fq_zero(ulong * a, slong d)
0464 {
0465     slong i;
0466     for (i = 0; i < d; i++)
0467         a[i] = 0;
0468 }
0469 
0470 FLINT_FORCE_INLINE
0471 int _n_fq_is_one(const ulong * a, slong d)
0472 {
0473     slong i;
0474     if (a[0] != 1)
0475         return 0;
0476     for (i = 1; i < d; i++)
0477         if (a[i] != 0)
0478             return 0;
0479     return 1;
0480 }
0481 
0482 FLINT_FORCE_INLINE
0483 int _n_fq_is_ui(const ulong * a, slong d)
0484 {
0485     slong i;
0486     for (i = 1; i < d; i++)
0487         if (a[i] != 0)
0488             return 0;
0489     return 1;
0490 }
0491 
0492 FLINT_FORCE_INLINE
0493 int n_fq_is_one(const ulong * a, const fq_nmod_ctx_t ctx)
0494 {
0495     return _n_fq_is_one(a, fq_nmod_ctx_degree(ctx));
0496 }
0497 
0498 FLINT_FORCE_INLINE
0499 void _n_fq_one(ulong * a, slong d)
0500 {
0501     slong i;
0502     a[0] = 1;
0503     for (i = 1; i < d; i++)
0504         a[i] = 0;
0505 }
0506 
0507 FLINT_FORCE_INLINE
0508 void _n_fq_set_nmod(ulong * a, ulong b, slong d)
0509 {
0510     slong i;
0511     a[0] = b;
0512     for (i = 1; i < d; i++)
0513         a[i] = 0;
0514 }
0515 
0516 void n_fq_gen(ulong * a, const fq_nmod_ctx_t ctx);
0517 
0518 FLINT_FORCE_INLINE
0519 void _n_fq_set(
0520     ulong * a,
0521     const ulong * b,
0522     slong d)
0523 {
0524     slong i = 0;
0525     do a[i] = b[i]; while (++i < d);
0526 }
0527 
0528 FLINT_FORCE_INLINE
0529 void _n_fq_swap(ulong * a, ulong * b, slong d)
0530 {
0531     slong i = 0;
0532     do FLINT_SWAP(ulong, a[i], b[i]); while (++i < d);
0533 }
0534 
0535 FLINT_FORCE_INLINE
0536 int _n_fq_equal(ulong * a, const ulong * b, slong d)
0537 {
0538     slong i = 0;
0539     do
0540         if (a[i] != b[i]) return 0;
0541     while (++i < d);
0542     return 1;
0543 }
0544 
0545 int n_fq_equal_fq_nmod(const ulong * a, const fq_nmod_t b, const fq_nmod_ctx_t ctx);
0546 
0547 int n_fq_is_canonical(const ulong * a, const fq_nmod_ctx_t ctx);
0548 
0549 void n_fq_randtest_not_zero(ulong * a, flint_rand_t state, const fq_nmod_ctx_t ctx);
0550 
0551 char * n_fq_get_str_pretty(const ulong * a, const fq_nmod_ctx_t ctx);
0552 
0553 #ifdef FLINT_HAVE_FILE
0554 int n_fq_fprint_pretty(FILE * file, const ulong * a, const fq_nmod_ctx_t ctx);
0555 #endif
0556 void n_fq_print_pretty(const ulong * a, const fq_nmod_ctx_t ctx);
0557 
0558 void n_fq_get_n_poly(n_poly_t a, const ulong * b, const fq_nmod_ctx_t ctx);
0559 void n_fq_get_fq_nmod(fq_nmod_t a, const ulong * b, const fq_nmod_ctx_t ctx);
0560 
0561 void _n_fq_set_n_poly(ulong * a, const ulong * bcoeffs, slong blen, const fq_nmod_ctx_t ctx);
0562 void n_fq_set_fq_nmod(ulong * a, const fq_nmod_t b, const fq_nmod_ctx_t ctx);
0563 
0564 FLINT_FORCE_INLINE
0565 void _n_fq_neg(ulong * a, const ulong * b, slong d, nmod_t mod)
0566 {
0567     FLINT_ASSERT(d > 0);
0568     _nmod_vec_neg(a, b, d, mod);
0569 }
0570 FLINT_FORCE_INLINE
0571 void _n_fq_add(ulong * a, const ulong * b, const ulong * c, slong d, nmod_t mod)
0572 {
0573     FLINT_ASSERT(d > 0);
0574     _nmod_vec_add(a, b, c, d, mod);
0575 }
0576 void n_fq_add_si(ulong * a, const ulong * b, slong c, const fq_nmod_ctx_t ctx);
0577 void n_fq_add_fq_nmod(ulong * a, const ulong * b, const fq_nmod_t c, const fq_nmod_ctx_t ctx);
0578 FLINT_FORCE_INLINE
0579 void n_fq_add(ulong * a, const ulong * b, const ulong * c, const fq_nmod_ctx_t ctx)
0580 {
0581     slong d = fq_nmod_ctx_degree(ctx);
0582     FLINT_ASSERT(d > 0);
0583     _nmod_vec_add(a, b, c, d, ctx->modulus->mod);
0584 }
0585 FLINT_FORCE_INLINE
0586 void _n_fq_sub(ulong * a, const ulong * b, const ulong * c, slong d, nmod_t mod)
0587 {
0588     FLINT_ASSERT(d > 0);
0589     _nmod_vec_sub(a, b, c, d, mod);
0590 }
0591 void n_fq_sub_fq_nmod(ulong * a, const ulong * b, const fq_nmod_t c, const fq_nmod_ctx_t ctx);
0592 FLINT_FORCE_INLINE
0593 void n_fq_sub(ulong * a, const ulong * b, const ulong * c, const fq_nmod_ctx_t ctx)
0594 {
0595     slong d = fq_nmod_ctx_degree(ctx);
0596     FLINT_ASSERT(d > 0);
0597     _nmod_vec_sub(a, b, c, d, ctx->modulus->mod);
0598 }
0599 
0600 // FIXME
0601 void _n_fq_mul_ui(
0602     ulong * a,          /* length d */
0603     const ulong * b,    /* length d */
0604     ulong c,
0605     slong d,
0606     nmod_t mod);
0607 
0608 void _n_fq_madd2(
0609     ulong * a,          /* length 2d-1 */
0610     const ulong * b,    /* length d */
0611     const ulong * c,    /* length d */
0612     const fq_nmod_ctx_t ctx,
0613     ulong * t);         /* length 2d */
0614 
0615 void _n_fq_mul2(
0616     ulong * t,          /* length 2d-1 */
0617     const ulong * b,    /* length d */
0618     const ulong * c,    /* length d */
0619     const fq_nmod_ctx_t ctx);
0620 
0621 #define N_FQ_REDUCE_ITCH 2
0622 void _n_fq_reduce(ulong * a, ulong * b, slong blen, const fq_nmod_ctx_t ctx, ulong * t);
0623 /* len(a) = d, len(b) = 2d - 1, len(t) = d */
0624 FLINT_FORCE_INLINE
0625 void _n_fq_reduce2(ulong * a, ulong * b, const fq_nmod_ctx_t ctx, ulong * t)
0626 {
0627     slong blen = 2*fq_nmod_ctx_degree(ctx) - 1;
0628     FLINT_ASSERT(a != b);
0629     while (blen > 0 && b[blen - 1] == 0)
0630         blen--;
0631     _n_fq_reduce(a, b, blen, ctx, t);
0632 }
0633 
0634 /* len(a) = len(b) = len(c) = len(e) = d, len(t) = 4d */
0635 #define N_FQ_MUL_ITCH 4
0636 FLINT_FORCE_INLINE
0637 void _n_fq_mul(ulong * a, const ulong * b, const ulong * c, const fq_nmod_ctx_t ctx, ulong * t)
0638 {
0639     slong d = fq_nmod_ctx_degree(ctx);
0640     _n_fq_mul2(t, b, c, ctx);
0641     _n_fq_reduce2(a, t, ctx, t + 2*d);
0642 }
0643 FLINT_FORCE_INLINE
0644 void _n_fq_addmul(ulong * a, const ulong * b, const ulong * c, const ulong * e, const fq_nmod_ctx_t ctx, ulong * t)
0645 {
0646     slong d = fq_nmod_ctx_degree(ctx);
0647     _n_fq_mul2(t, c, e, ctx);
0648     _nmod_vec_add(t, t, b, d, ctx->mod);
0649     _n_fq_reduce2(a, t, ctx, t + 2*d);
0650 }
0651 
0652 #define N_FQ_LAZY_ITCH 6
0653 int _n_fq_dot_lazy_size(slong len, const fq_nmod_ctx_t ctx);
0654 
0655 /* len(a) = 6d (2d used), len(b) = len(c) = d */
0656 void _n_fq_madd2_lazy1(ulong * a, const ulong * b, const ulong * c, slong d);
0657 void _n_fq_mul2_lazy1(ulong * a, const ulong * b, const ulong * c, slong d);
0658 void _n_fq_reduce2_lazy1(ulong * a, slong d, nmod_t ctx);
0659 
0660 /* len(a) = 6d (4d used), len(b) = len(c) = d */
0661 void _n_fq_madd2_lazy2(ulong * a, const ulong * b, const ulong * c, slong d);
0662 void _n_fq_mul2_lazy2(ulong * a, const ulong * b, const ulong * c, slong d);
0663 void _n_fq_reduce2_lazy2(ulong * a, slong d, nmod_t ctx);
0664 
0665 /* len(a) = 6d, len(b) = len(c) = d */
0666 void _n_fq_madd2_lazy3(ulong * a, const ulong * b, const ulong * c, slong d);
0667 void _n_fq_mul2_lazy3(ulong * a, const ulong * b, const ulong * c, slong d);
0668 void _n_fq_reduce2_lazy3(ulong * a, slong d, nmod_t ctx);
0669 
0670 #define N_FQ_INV_ITCH 1
0671 void _n_fq_inv(ulong * a, const ulong * b, const fq_nmod_ctx_t ctx, ulong * t);
0672 void n_fq_inv(ulong * a, const ulong * b, const fq_nmod_ctx_t ctx);
0673 
0674 #define N_FQ_MUL_INV_ITCH FLINT_MAX(N_FQ_MUL_ITCH, N_FQ_INV_ITCH)
0675 void n_fq_mul(ulong * a, const ulong * b, const ulong * c, const fq_nmod_ctx_t ctx);
0676 void n_fq_mul_fq_nmod(ulong * a, const ulong * b, const fq_nmod_t c, const fq_nmod_ctx_t ctx);
0677 
0678 void n_fq_addmul(ulong * a, const ulong * b, const ulong * c, const ulong * d, const fq_nmod_ctx_t ctx);
0679 
0680 void _n_fq_pow_ui(ulong * a, const ulong * b, ulong e, const fq_nmod_ctx_t ctx);
0681 void n_fq_pow_ui(ulong * a, const ulong * b, ulong e, const fq_nmod_ctx_t ctx);
0682 void n_fq_pow_fmpz(ulong * a, const ulong * b, const fmpz_t e, const fq_nmod_ctx_t ctx);
0683 
0684 /* n_fq_poly *****************************************************************/
0685 
0686 #define N_FQ_POLY_DIVREM_DIVCONQUER_CUTOFF 20
0687 
0688 #define n_fq_poly_init n_poly_init
0689 void n_fq_poly_init2(n_fq_poly_t A, slong alloc, const fq_nmod_ctx_t ctx);
0690 #define n_fq_poly_clear n_poly_clear
0691 #define n_fq_poly_swap n_poly_swap
0692 int n_fq_poly_is_canonical(const n_fq_poly_t a, const fq_nmod_ctx_t ctx);
0693 
0694 #define n_fq_poly_degree n_poly_degree
0695 
0696 #define n_fq_poly_zero n_poly_zero
0697 void _n_fq_poly_one(n_fq_poly_t A, slong d);
0698 FLINT_FORCE_INLINE
0699 void n_fq_poly_one(n_fq_poly_t A, const fq_nmod_ctx_t ctx)
0700 {
0701     _n_fq_poly_one(A, fq_nmod_ctx_degree(ctx));
0702 }
0703 
0704 #define n_fq_poly_is_zero n_poly_is_zero
0705 int n_fq_poly_is_one(n_fq_poly_t A, const fq_nmod_ctx_t ctx);
0706 int n_fq_poly_equal(const n_fq_poly_t A, const n_fq_poly_t B, const fq_nmod_ctx_t ctx);
0707 
0708 FLINT_FORCE_INLINE
0709 void _n_fq_poly_normalise(n_fq_poly_t A, slong d)
0710 {
0711     while (A->length > 0 && _n_fq_is_zero(A->coeffs + d*(A->length - 1), d))
0712         A->length--;
0713 }
0714 
0715 void n_fq_poly_print_pretty(const n_fq_poly_t A, const char * x, const fq_nmod_ctx_t ctx);
0716 
0717 void n_fq_poly_set(n_fq_poly_t A, const n_fq_poly_t B, const fq_nmod_ctx_t ctx);
0718 
0719 void n_fq_poly_randtest(n_fq_poly_t A, flint_rand_t state, slong len, const fq_nmod_ctx_t ctx);
0720 
0721 void n_fq_poly_make_monic(n_fq_poly_t A, const n_poly_t B, const fq_nmod_ctx_t ctx);
0722 
0723 void n_fq_poly_get_coeff_n_fq(ulong * c, const n_poly_t A, slong e, const fq_nmod_ctx_t ctx);
0724 void n_fq_poly_get_coeff_fq_nmod(fq_nmod_t c, const n_poly_t A, slong e, const fq_nmod_ctx_t ctx);
0725 
0726 void n_fq_poly_set_coeff_fq_nmod(n_poly_t A, slong j, const fq_nmod_t c, const fq_nmod_ctx_t ctx);
0727 void n_fq_poly_set_coeff_n_fq(n_poly_t A, slong j, const ulong * c, const fq_nmod_ctx_t ctx);
0728 
0729 void n_fq_poly_scalar_mul_ui(n_poly_t A, const n_poly_t B, ulong c, const fq_nmod_ctx_t ctx);
0730 void n_fq_poly_scalar_mul_n_fq(n_poly_t A, const n_poly_t B, const ulong * c, const fq_nmod_ctx_t ctx);
0731 void n_fq_poly_scalar_addmul_n_fq(n_fq_poly_t A, const n_fq_poly_t B, const n_fq_poly_t C, const ulong * d, const fq_nmod_ctx_t ctx);
0732 
0733 void n_fq_poly_shift_left_scalar_submul(n_poly_t A, slong k, const ulong * c, const fq_nmod_ctx_t ctx);
0734 
0735 void n_fq_poly_evaluate_fq_nmod(fq_nmod_t e, const n_poly_t A, const fq_nmod_t c, const fq_nmod_ctx_t ctx);
0736 void n_fq_poly_evaluate_n_fq(ulong * e, const n_poly_t A, const ulong * c, const fq_nmod_ctx_t ctx);
0737 
0738 void n_fq_poly_get_fq_nmod_poly(fq_nmod_poly_t A, const n_poly_t B, const fq_nmod_ctx_t ctx);
0739 
0740 void n_fq_poly_set_n_fq(n_poly_t A, const ulong * c, const fq_nmod_ctx_t ctx);
0741 void n_fq_poly_set_fq_nmod(n_poly_t A, const fq_nmod_t c, const fq_nmod_ctx_t ctx);
0742 void n_fq_poly_set_fq_nmod_poly(n_poly_t A, const fq_nmod_poly_t B, const fq_nmod_ctx_t ctx);
0743 
0744 void n_fq_poly_shift_left(n_poly_t A, const n_poly_t B, slong n, const fq_nmod_ctx_t ctx);
0745 void n_fq_poly_shift_right(n_poly_t A, const n_poly_t B, slong n, const fq_nmod_ctx_t ctx);
0746 
0747 void n_fq_poly_truncate(n_poly_t A, slong len, const fq_nmod_ctx_t ctx);
0748 
0749 void n_fq_poly_neg(n_poly_t A, const n_poly_t B, const fq_nmod_ctx_t ctx);
0750 void n_fq_poly_add(n_poly_t A, const n_poly_t B, const n_poly_t C, const fq_nmod_ctx_t ctx);
0751 void n_fq_poly_sub(n_poly_t A, const n_poly_t B, const n_poly_t C, const fq_nmod_ctx_t ctx);
0752 void n_fq_poly_add_si(n_poly_t A, const n_poly_t B, slong c, const fq_nmod_ctx_t ctx);
0753 
0754 void _n_fq_poly_mul_(ulong * A, const ulong * B, slong Blen, const ulong * C, slong Clen, const fq_nmod_ctx_t ctx, n_poly_stack_t St);
0755 void n_fq_poly_mul_(n_poly_t A, const n_poly_t B, const n_poly_t C, const fq_nmod_ctx_t ctx, n_poly_stack_t St);
0756 void n_fq_poly_mul(n_poly_t A, const n_poly_t B, const n_poly_t C, const fq_nmod_ctx_t ctx);
0757 
0758 void n_fq_poly_pow(n_poly_t A, const n_poly_t B, ulong e, const fq_nmod_ctx_t ctx);
0759 
0760 ulong n_fq_poly_remove(n_poly_t f, const n_poly_t g, const fq_nmod_ctx_t ctx);
0761 
0762 void _n_fq_poly_divrem_basecase_(ulong * Q, ulong * A, const ulong * AA, slong Alen, const ulong * B, slong Blen, const ulong * invB, const fq_nmod_ctx_t ctx, n_poly_stack_t St);
0763 void n_fq_poly_divrem_divconquer_(n_poly_t Q, n_poly_t R, const n_poly_t A, const n_poly_t B, const fq_nmod_ctx_t ctx, n_poly_stack_t St);
0764 
0765 FLINT_FORCE_INLINE
0766 void n_fq_poly_divrem_(n_poly_t Q, n_poly_t R, const n_poly_t A, const n_poly_t B, const fq_nmod_ctx_t ctx, n_poly_stack_t St)
0767 {
0768     n_fq_poly_divrem_divconquer_(Q, R, A, B, ctx, St);
0769 }
0770 void n_fq_poly_divrem(n_poly_t Q, n_poly_t R, const n_poly_t A, const n_poly_t B, const fq_nmod_ctx_t ctx);
0771 
0772 void n_fq_poly_gcd_(n_poly_t G, const n_poly_t A, const n_poly_t B, const fq_nmod_ctx_t ctx, n_poly_stack_t St);
0773 void n_fq_poly_gcd(n_poly_t G, const n_poly_t A, const n_poly_t B, const fq_nmod_ctx_t ctx);
0774 void n_fq_poly_xgcd(n_poly_t G, n_poly_t S, n_poly_t T, const n_poly_t B, const n_poly_t C, const fq_nmod_ctx_t ctx);
0775 
0776 void n_fq_poly_mulmod(n_poly_t A, const n_poly_t B, const n_poly_t C, const n_poly_t M, const fq_nmod_ctx_t ctx);
0777 
0778 void _n_fq_poly_rem_basecase_(ulong * Q, ulong * A, const ulong * AA, slong Alen, const ulong * B, slong Blen, const ulong * invB, const fq_nmod_ctx_t ctx, n_poly_stack_t St);
0779 void n_fq_poly_rem(n_poly_t R, const n_poly_t A, const n_poly_t B, const fq_nmod_ctx_t ctx);
0780 
0781 void n_fq_poly_mullow(n_poly_t A, const n_poly_t B, const n_poly_t C, slong order, const fq_nmod_ctx_t ctx);
0782 
0783 void n_fq_poly_inv_series(n_poly_t A, const n_poly_t B, slong order, const fq_nmod_ctx_t ctx);
0784 
0785 void n_fq_poly_eval_pow(ulong * ev, const n_fq_poly_t A, n_fq_poly_t alphapow, const fq_nmod_ctx_t ctx);
0786 
0787 /* n_fq_polyun ***************************************************************/
0788 
0789 #define n_fq_polyun_init n_polyun_init
0790 #define n_fq_polyun_clear n_polyun_clear
0791 
0792 void n_fq_polyun_set(n_fq_polyun_t A, const n_fq_polyun_t B, const fq_nmod_ctx_t ctx);
0793 
0794 /* n_bpoly *******************************************************************/
0795 
0796 FLINT_FORCE_INLINE
0797 void n_bpoly_init(n_bpoly_t A)
0798 {
0799     A->coeffs = NULL;
0800     A->alloc = 0;
0801     A->length = 0;
0802 }
0803 void n_bpoly_clear(n_bpoly_t A);
0804 void n_bpoly_realloc(n_bpoly_t A, slong len);
0805 
0806 FLINT_FORCE_INLINE
0807 void n_bpoly_fit_length(n_bpoly_t A, slong len)
0808 {
0809     if (len > A->alloc)
0810         n_bpoly_realloc(A, len);
0811 }
0812 
0813 FLINT_FORCE_INLINE
0814 void n_bpoly_swap(n_bpoly_t A, n_bpoly_t B)
0815 {
0816     n_bpoly_struct t = *A;
0817     *A = *B;
0818     *B = t;
0819 }
0820 
0821 void n_bpoly_print_pretty(const n_bpoly_t A, const char * xvar, const char * yvar);
0822 
0823 FLINT_FORCE_INLINE
0824 void n_bpoly_normalise(n_bpoly_t A)
0825 {
0826     while (A->length > 0 && n_poly_is_zero(A->coeffs + A->length - 1))
0827         A->length--;
0828 }
0829 
0830 FLINT_FORCE_INLINE void n_bpoly_zero(n_bpoly_t A) { A->length = 0; }
0831 void n_bpoly_one(n_bpoly_t A);
0832 void _n_bpoly_set(n_bpoly_t A, const n_bpoly_t B);
0833 
0834 FLINT_FORCE_INLINE
0835 void n_bpoly_set(n_bpoly_t A, const n_bpoly_t B)
0836 {
0837     if (A != B)
0838         _n_bpoly_set(A, B);
0839 }
0840 
0841 FLINT_FORCE_INLINE
0842 int n_bpoly_is_zero(const n_bpoly_t A) { return A->length == 0; }
0843 int n_bpoly_equal(const n_bpoly_t A, const n_bpoly_t B);
0844 
0845 void n_bpoly_set_coeff(n_bpoly_t A, slong e0, slong e1, ulong c);
0846 void n_bpoly_set_coeff_nonzero(n_bpoly_t A, slong e0, slong e1, ulong c);
0847 
0848 void n_bpoly_mod_derivative_gen0(n_bpoly_t A, const n_bpoly_t B, nmod_t ctx);
0849 
0850 FLINT_FORCE_INLINE
0851 ulong n_bpoly_get_coeff(const n_bpoly_t A, slong e0, slong e1)
0852 {
0853     return (e0 >= A->length) ? 0 : n_poly_get_coeff(A->coeffs + e0, e1);
0854 }
0855 
0856 FLINT_FORCE_INLINE
0857 slong n_bpoly_degree0(const n_bpoly_t A) { return A->length - 1; }
0858 slong n_bpoly_degree1(const n_bpoly_t A);
0859 
0860 void n_bpoly_set_poly_gen0(n_bpoly_t A, const n_poly_t B);
0861 void n_bpoly_set_poly_gen1(n_bpoly_t A, const n_poly_t B);
0862 
0863 /* n_bpoly modular arithmetic ************************************************/
0864 
0865 int n_bpoly_mod_is_canonical(const n_bpoly_t A, nmod_t mod);
0866 
0867 FLINT_FORCE_INLINE
0868 ulong n_bpoly_bidegree(const n_bpoly_t A)
0869 {
0870     ulong x, y;
0871     FLINT_ASSERT(A->length > 0);
0872     x = A->length - 1;
0873     y = A->coeffs[x].length - 1;
0874     return (x << (FLINT_BITS/2)) + y;
0875 }
0876 
0877 void n_bpoly_scalar_mul_nmod(n_bpoly_t A, ulong c, nmod_t ctx);
0878 
0879 void n_bpoly_mod_content_last(n_poly_t g, const n_bpoly_t A, nmod_t ctx);
0880 
0881 void n_bpoly_mod_divexact_last(n_bpoly_t A, const n_poly_t b, nmod_t ctx);
0882 
0883 void n_bpoly_mod_mul_last(n_bpoly_t A, const n_poly_t b, nmod_t ctx);
0884 
0885 void n_bpoly_mod_taylor_shift_gen0(n_bpoly_t A, ulong c, nmod_t ctx);
0886 void n_bpoly_mod_taylor_shift_gen1(n_bpoly_t A, const n_bpoly_t B, ulong c, nmod_t ctx);
0887 
0888 void n_bpoly_mod_add(n_bpoly_t A, const n_bpoly_t B, const n_bpoly_t C, nmod_t ctx);
0889 void n_bpoly_mod_sub(n_bpoly_t A, const n_bpoly_t B, const n_bpoly_t C, nmod_t ctx);
0890 void n_bpoly_mod_mul(n_bpoly_t A, const n_bpoly_t B, const n_bpoly_t C, nmod_t ctx);
0891 
0892 int n_bpoly_mod_divides(n_bpoly_t Q, const n_bpoly_t A, const n_bpoly_t B, nmod_t ctx);
0893 
0894 void n_bpoly_mod_make_primitive(n_poly_t g, n_bpoly_t A, nmod_t ctx);
0895 
0896 void n_bpoly_mod_mul_series(n_bpoly_t A, const n_bpoly_t B, const n_bpoly_t C, slong order, nmod_t ctx);
0897 void n_bpoly_mod_divrem_series(n_bpoly_t Q, n_bpoly_t R, const n_bpoly_t A, const n_bpoly_t B, slong order, nmod_t ctx);
0898 
0899 void n_bpoly_mod_interp_reduce_2sm_poly(n_poly_t Ap, n_poly_t Am, const n_bpoly_t A, n_poly_t alphapow, nmod_t mod);
0900 void n_bpoly_mod_interp_lift_2sm_poly(slong * deg1, n_bpoly_t T, const n_poly_t A, const n_poly_t B, ulong alpha, nmod_t mod);
0901 int n_bpoly_mod_interp_crt_2sm_poly(slong * deg1, n_bpoly_t F, n_bpoly_t T, n_poly_t A, n_poly_t B, const n_poly_t modulus, n_poly_t alphapow, nmod_t mod);
0902 
0903 int n_bpoly_mod_gcd_brown_smprime(n_bpoly_t G, n_bpoly_t Abar, n_bpoly_t Bbar, n_bpoly_t A, n_bpoly_t B, nmod_t ctx, n_poly_bpoly_stack_t Sp);
0904 
0905 /* n_fq_bpoly ****************************************************************/
0906 
0907 #define n_fq_bpoly_init n_bpoly_init
0908 #define n_fq_bpoly_clear n_bpoly_clear
0909 
0910 #define n_fq_bpoly_zero n_bpoly_zero
0911 
0912 #define n_fq_bpoly_fit_length n_bpoly_fit_length
0913 
0914 #define n_fq_bpoly_normalise n_bpoly_normalise
0915 
0916 #define n_fq_bpoly_degree0 n_bpoly_degree0
0917 #define n_fq_bpoly_degree1 n_bpoly_degree1
0918 
0919 int n_fq_bpoly_is_canonical(const n_fq_bpoly_t A, const fq_nmod_ctx_t ctx);
0920 
0921 void n_fq_bpoly_one(n_fq_bpoly_t A, const fq_nmod_ctx_t ctx);
0922 void n_fq_bpoly_set(n_fq_bpoly_t A, const n_fq_bpoly_t B, const fq_nmod_ctx_t ctx);
0923 
0924 int n_fq_bpoly_equal(const n_bpoly_t A, const n_bpoly_t B, const fq_nmod_ctx_t ctx);
0925 
0926 void n_fq_bpoly_get_coeff_n_fq(ulong * c, const n_bpoly_t A, slong e0, slong e1, const fq_nmod_ctx_t ctx);
0927 void n_fq_bpoly_get_coeff_fq_nmod(fq_nmod_t c, const n_bpoly_t A, slong e0, slong e1, const fq_nmod_ctx_t ctx);
0928 void n_fq_bpoly_set_coeff_n_fq(n_fq_bpoly_t A, slong e0, slong e1, const ulong * c, const fq_nmod_ctx_t ctx);
0929 
0930 void n_fq_bpoly_set_fq_nmod_poly_gen0(n_bpoly_t A, const fq_nmod_poly_t B, const fq_nmod_ctx_t ctx);
0931 void n_fq_bpoly_set_n_fq_poly_gen0(n_bpoly_t A, const n_poly_t B, const fq_nmod_ctx_t ctx);
0932 void n_fq_bpoly_set_n_fq_poly_gen1(n_bpoly_t A, const n_poly_t B, const fq_nmod_ctx_t ctx);
0933 
0934 void n_fq_bpoly_derivative_gen0(n_bpoly_t A, const n_bpoly_t B, const fq_nmod_ctx_t ctx);
0935 
0936 void n_fq_bpoly_scalar_mul_n_fq(n_fq_bpoly_t A, const ulong * c, const fq_nmod_ctx_t ctx);
0937 
0938 void n_fq_bpoly_taylor_shift_gen0_fq_nmod(n_bpoly_t A, const fq_nmod_t alpha, const fq_nmod_ctx_t ctx);
0939 void n_fq_bpoly_taylor_shift_gen1_fq_nmod(n_bpoly_t A, const n_bpoly_t B, const fq_nmod_t c_, const fq_nmod_ctx_t ctx);
0940 void n_fq_bpoly_taylor_shift_gen0_n_fq(n_fq_bpoly_t A, const ulong * alpha, const fq_nmod_ctx_t ctx);
0941 
0942 int n_fq_bpoly_gcd_brown_smprime(n_fq_bpoly_t G, n_fq_bpoly_t Abar, n_fq_bpoly_t Bbar, n_fq_bpoly_t A, n_fq_bpoly_t B, const fq_nmod_ctx_t ctx, n_poly_bpoly_stack_t Sp);
0943 
0944 void n_fq_bpoly_print_pretty(const n_fq_bpoly_t A, const char * xvar, const char * yvar, const fq_nmod_ctx_t ctx);
0945 
0946 /* n_tpoly *******************************************************************/
0947 
0948 FLINT_FORCE_INLINE
0949 void n_tpoly_init(n_tpoly_t A)
0950 {
0951     A->coeffs = NULL;
0952     A->alloc = 0;
0953     A->length = 0;
0954 }
0955 void n_tpoly_clear(n_tpoly_t A);
0956 void n_tpoly_fit_length(n_tpoly_t A, slong len);
0957 
0958 FLINT_FORCE_INLINE
0959 void n_tpoly_swap(n_tpoly_t A, n_tpoly_t B)
0960 {
0961     n_tpoly_struct t = *A;
0962     *A = *B;
0963     *B = t;
0964 }
0965 
0966 /* n_polyu *******************************************************************/
0967 
0968 FLINT_FORCE_INLINE
0969 void n_polyu_init(n_polyu_t A)
0970 {
0971     A->coeffs = NULL;
0972     A->exps = NULL;
0973     A->length = 0;
0974     A->alloc = 0;
0975 }
0976 void n_polyu_clear(n_polyu_t A);
0977 void n_polyu_realloc(n_polyu_t A, slong len);
0978 
0979 FLINT_FORCE_INLINE
0980 void n_polyu_fit_length(n_polyu_t A, slong len)
0981 {
0982     FLINT_ASSERT(A->alloc >= 0);
0983     if (len > A->alloc)
0984         n_polyu_realloc(A, len);
0985 }
0986 
0987 FLINT_FORCE_INLINE
0988 void n_polyu_swap(n_polyu_t A, n_polyu_t B)
0989 {
0990     n_polyu_struct T = *B;
0991     *B = *A;
0992     *A = T;
0993 }
0994 
0995 void n_polyu3_print_pretty(const n_polyu_t A, const char * gen0, const char * gen1, const char * var2);
0996 
0997 void n_polyu3_degrees(slong * deg0, slong * deg1, slong * deg2, const n_polyu_t A);
0998 
0999 /* powering ******************************************************************/
1000 
1001 void nmod_pow_cache_start(ulong b, n_poly_t pos_direct, n_poly_t pos_bin, n_poly_t neg_direct);
1002 
1003 ulong nmod_pow_cache_mulpow_ui(ulong a, ulong e, n_poly_t pos_direct, n_poly_t pos_bin, n_poly_t neg_direct, nmod_t ctx);
1004 ulong nmod_pow_cache_mulpow_neg_ui(ulong a, ulong e, n_poly_t pos_direct, n_poly_t pos_bin, n_poly_t neg_direct, nmod_t ctx);
1005 ulong nmod_pow_cache_mulpow_fmpz(ulong a, const fmpz_t e, n_poly_t pos_direct, n_poly_t pos_bin, n_poly_t neg_direct, nmod_t ctx);
1006 
1007 void n_fq_pow_cache_start_n_fq(const ulong * b, n_poly_t pos_direct, n_poly_t pos_bin, n_poly_t neg_direct, const fq_nmod_ctx_t ctx);
1008 void n_fq_pow_cache_start_fq_nmod(const fq_nmod_t b, n_poly_t pos_direct, n_poly_t pos_bin, n_poly_t neg_direct, const fq_nmod_ctx_t ctx);
1009 
1010 void n_fq_pow_cache_mulpow_ui(ulong * r, const ulong * a, ulong e, n_poly_t pos_direct, n_poly_t pos_bin, n_poly_t neg_direct, const fq_nmod_ctx_t ctx);
1011 void n_fq_pow_cache_mulpow_neg_ui(ulong * r, const ulong * a, ulong e, n_poly_t pos_direct, n_poly_t pos_bin, n_poly_t neg_direct, const fq_nmod_ctx_t ctx);
1012 void n_fq_pow_cache_mulpow_fmpz(ulong * r, const ulong * a, const fmpz_t e, n_poly_t pos_direct, n_poly_t pos_bin, n_poly_t neg_direct, const fq_nmod_ctx_t ctx);
1013 
1014 /* evaluation ****************************************************************/
1015 
1016 void nmod_eval_interp_init(nmod_eval_interp_t E);
1017 void nmod_eval_interp_clear(nmod_eval_interp_t E);
1018 
1019 int nmod_eval_interp_set_degree_modulus(nmod_eval_interp_t E, slong deg, nmod_t ctx);
1020 
1021 FLINT_FORCE_INLINE
1022 slong nmod_eval_interp_eval_length(nmod_eval_interp_t E)
1023 {
1024     return 1 + E->radix*E->d;
1025 }
1026 
1027 void nmod_eval_interp_to_coeffs_poly(n_poly_t a, const n_poly_t v, nmod_eval_interp_t E, nmod_t ctx);
1028 void nmod_eval_interp_from_coeffs_poly(n_poly_t v, const n_poly_t a, nmod_eval_interp_t E, nmod_t ctx);
1029 void nmod_eval_interp_to_coeffs_n_fq_poly(n_fq_poly_t a, const n_fq_poly_t v, nmod_eval_interp_t E, const fq_nmod_ctx_t ctx);
1030 void nmod_eval_interp_from_coeffs_n_fq_poly(n_fq_poly_t v, const n_fq_poly_t a, nmod_eval_interp_t E, const fq_nmod_ctx_t ctx);
1031 
1032 FLINT_FORCE_INLINE void nmod_evals_zero(n_poly_t a) { a->length = 0; }
1033 void nmod_evals_add_inplace(n_poly_t a, n_poly_t b, slong len, nmod_t ctx);
1034 void nmod_evals_mul(n_poly_t a, n_poly_t b, n_poly_t c, slong len, nmod_t ctx);
1035 void nmod_evals_addmul(n_poly_t a, n_poly_t b, n_poly_t c, slong len, nmod_t ctx);
1036 void nmod_evals_fmma(n_poly_t a, n_poly_t b, n_poly_t c, n_poly_t d, n_poly_t e, slong len, nmod_t ctx);
1037 
1038 FLINT_FORCE_INLINE void n_fq_evals_zero(n_fq_poly_t a) { a->length = 0; }
1039 void n_fq_evals_add_inplace(n_fq_poly_t a, n_fq_poly_t b, slong len, const fq_nmod_ctx_t ctx);
1040 void n_fq_evals_mul(n_fq_poly_t a, n_fq_poly_t b, n_fq_poly_t c, slong len, const fq_nmod_ctx_t ctx);
1041 void n_fq_evals_addmul(n_fq_poly_t a, n_fq_poly_t b, n_fq_poly_t c, slong len, const fq_nmod_ctx_t ctx);
1042 void n_fq_evals_fmma(n_fq_poly_t a, n_fq_poly_t b, n_fq_poly_t c, n_fq_poly_t f, n_fq_poly_t e, slong len, const fq_nmod_ctx_t ctx);
1043 
1044 /* n_polyun ******************************************************************/
1045 
1046 FLINT_FORCE_INLINE
1047 void n_polyun_init(n_polyun_t A)
1048 {
1049     A->coeffs = NULL;
1050     A->exps = NULL;
1051     A->length = 0;
1052     A->alloc = 0;
1053 }
1054 void n_polyun_clear(n_polyun_t A);
1055 void n_polyun_realloc(n_polyun_t A, slong len);
1056 
1057 int n_polyun_is_canonical(const n_polyun_t A);
1058 int n_polyun_mod_is_canonical(const n_polyun_t A, nmod_t mod);
1059 
1060 FLINT_FORCE_INLINE
1061 void n_polyun_fit_length(n_polyun_t A, slong len)
1062 {
1063     if (len > A->alloc)
1064         n_polyun_realloc(A, len);
1065 }
1066 
1067 FLINT_FORCE_INLINE
1068 void n_polyun_swap(n_polyun_t A, n_polyun_t B)
1069 {
1070     n_polyun_struct t = *B;
1071     *B = *A;
1072     *A = t;
1073 }
1074 
1075 void n_polyun_set(n_polyun_t A, const n_polyun_t B);
1076 
1077 void n_polyu1n_print_pretty(const n_polyun_t A, const char * var0, const char * varlast);
1078 void n_polyu2n_print_pretty(const n_polyun_t A, const char * gen0, const char * gen1, const char * varlast);
1079 void n_polyu3n_print_pretty(const n_polyun_t A, const char * gen0, const char * gen1, const char * var2, const char * varlast);
1080 
1081 int n_polyun_equal(const n_polyun_t A, const n_polyun_t B);
1082 
1083 FLINT_FORCE_INLINE
1084 void n_polyun_one(n_polyun_t A)
1085 {
1086     n_polyun_fit_length(A, 1);
1087     A->length = 1;
1088     A->exps[0] = 0;
1089     n_poly_one(A->coeffs + 0);
1090 }
1091 
1092 FLINT_FORCE_INLINE
1093 ulong n_polyu1n_bidegree(n_polyun_t A)
1094 {
1095     ulong x = A->exps[0];
1096     ulong y = A->coeffs[0].length - 1;
1097     return (x << (FLINT_BITS/2)) + y;
1098 }
1099 
1100 int n_polyu1n_mod_gcd_brown_smprime(n_polyun_t G, n_polyun_t Abar, n_polyun_t Bbar,n_polyun_t A, n_polyun_t B, nmod_t ctx, n_poly_polyun_stack_t St);
1101 
1102 /* products ******************************************************************/
1103 
1104 void n_fq_poly_product_roots_n_fq(n_poly_t M, const ulong * H, slong length, const fq_nmod_ctx_t ctx, n_poly_stack_t St);
1105 slong n_polyun_product_roots(n_polyun_t M, const n_polyun_t H, nmod_t ctx);
1106 slong n_fq_polyun_product_roots(n_fq_polyun_t M, const n_fq_polyun_t H, const fq_nmod_ctx_t ctx, n_poly_stack_t St);
1107 
1108 ulong _nmod_zip_eval_step(ulong * cur, const ulong * inc, const ulong * coeffs, slong length, nmod_t ctx);
1109 void _n_fq_zip_eval_step(ulong * res, ulong * cur, const ulong * inc, const ulong * coeffs, slong length, const fq_nmod_ctx_t ctx);
1110 void _n_fqp_zip_eval_step(ulong * res, ulong * cur, const ulong * inc, const ulong * coeffs, slong length, slong d, nmod_t mod);
1111 
1112 int _nmod_zip_vand_solve(ulong * coeffs, const ulong * monomials, slong mlength, const ulong * evals, slong elength, const ulong * master, ulong * scratch, nmod_t ctx);
1113 int _n_fq_zip_vand_solve(ulong * coeffs, const ulong * monomials, slong mlength, const ulong * evals, slong elength, const ulong * master, ulong * scratch, const fq_nmod_ctx_t ctx);
1114 int _n_fqp_zip_vand_solve(ulong * coeffs, const ulong * monomials, slong mlength, const ulong * evals, slong elength, const ulong * master, ulong * scratch, const fq_nmod_ctx_t ctx);
1115 
1116 /* n_poly_stack **************************************************************/
1117 
1118 void n_poly_stack_init(n_poly_stack_t S);
1119 void n_poly_stack_clear(n_poly_stack_t S);
1120 
1121 n_poly_struct ** n_poly_stack_fit_request(n_poly_stack_t S, slong k);
1122 
1123 FLINT_FORCE_INLINE
1124 ulong * n_poly_stack_vec_init(n_poly_stack_t S, slong len)
1125 {
1126     n_poly_struct * poly_top;
1127     poly_top = n_poly_stack_fit_request(S, 1)[0];
1128     S->top += 1;
1129     n_poly_fit_length(poly_top, len);
1130     return poly_top->coeffs;
1131 }
1132 
1133 FLINT_FORCE_INLINE
1134 void n_poly_stack_vec_clear(n_poly_stack_t S)
1135 {
1136     FLINT_ASSERT(S->top >= 1);
1137     S->top -= 1;
1138 }
1139 
1140 FLINT_FORCE_INLINE
1141 n_poly_struct ** n_poly_stack_request(n_poly_stack_t S, slong k)
1142 {
1143     n_poly_struct ** poly_top;
1144     poly_top = n_poly_stack_fit_request(S, k);
1145     S->top += k;
1146     return poly_top;
1147 }
1148 
1149 FLINT_FORCE_INLINE
1150 n_poly_struct * n_poly_stack_take_top(n_poly_stack_t S)
1151 {
1152     /* assume the request for 1 has already been fitted */
1153     n_poly_struct ** poly_top;
1154     FLINT_ASSERT(S->top + 1 <= S->alloc);
1155     poly_top = S->array + S->top;
1156     S->top += 1;
1157     return poly_top[0];
1158 }
1159 
1160 FLINT_FORCE_INLINE
1161 void n_poly_stack_give_back(n_poly_stack_t S, slong k)
1162 {
1163     FLINT_ASSERT(S->top >= k);
1164     S->top -= k;
1165 }
1166 
1167 FLINT_FORCE_INLINE
1168 slong n_poly_stack_size(const n_poly_stack_t S)
1169 {
1170     return S->top;
1171 }
1172 
1173 /* n_bpoly_stack *************************************************************/
1174 
1175 void n_bpoly_stack_init(n_bpoly_stack_t S);
1176 void n_bpoly_stack_clear(n_bpoly_stack_t S);
1177 
1178 n_bpoly_struct ** n_bpoly_stack_fit_request(n_bpoly_stack_t S, slong k);
1179 
1180 FLINT_FORCE_INLINE
1181 n_bpoly_struct ** n_bpoly_stack_request(n_bpoly_stack_t S, slong k)
1182 {
1183     n_bpoly_struct ** bpoly_top;
1184     bpoly_top = n_bpoly_stack_fit_request(S, k);
1185     S->top += k;
1186     return bpoly_top;
1187 }
1188 
1189 FLINT_FORCE_INLINE
1190 n_bpoly_struct * n_bpoly_stack_take_top(n_bpoly_stack_t S)
1191 {
1192     /* assume the request for 1 has already been fitted */
1193     n_bpoly_struct ** bpoly_top;
1194     FLINT_ASSERT(S->top + 1 <= S->alloc);
1195     bpoly_top = S->array + S->top;
1196     S->top += 1;
1197     return bpoly_top[0];
1198 }
1199 
1200 FLINT_FORCE_INLINE
1201 void n_bpoly_stack_give_back(n_bpoly_stack_t S, slong k)
1202 {
1203     FLINT_ASSERT(S->top >= k);
1204     S->top -= k;
1205 }
1206 
1207 FLINT_FORCE_INLINE
1208 slong n_bpoly_stack_size(const n_bpoly_stack_t S)
1209 {
1210     return S->top;
1211 }
1212 
1213 /* n_polyun_stack ************************************************************/
1214 
1215 void n_polyun_stack_init(n_polyun_stack_t S);
1216 void n_polyun_stack_clear(n_polyun_stack_t S);
1217 
1218 n_polyun_struct ** n_polyun_stack_fit_request(n_polyun_stack_t S, slong k);
1219 
1220 FLINT_FORCE_INLINE
1221 n_polyun_struct ** n_polyun_stack_request(n_polyun_stack_t S, slong k)
1222 {
1223     n_polyun_struct ** polyun_top;
1224     polyun_top = n_polyun_stack_fit_request(S, k);
1225     S->top += k;
1226     return polyun_top;
1227 }
1228 
1229 FLINT_FORCE_INLINE
1230 n_polyun_struct * n_polyun_stack_take_top(n_polyun_stack_t S)
1231 {
1232     /* assume the request for 1 has already been fitted */
1233     n_polyun_struct ** polyun_top;
1234     FLINT_ASSERT(S->top + 1 <= S->alloc);
1235     polyun_top = S->array + S->top;
1236     S->top += 1;
1237     return polyun_top[0];
1238 }
1239 
1240 FLINT_FORCE_INLINE
1241 void n_polyun_stack_give_back(n_polyun_stack_t S, slong k)
1242 {
1243     FLINT_ASSERT(S->top >= k);
1244     S->top -= k;
1245 }
1246 
1247 FLINT_FORCE_INLINE
1248 slong n_polyun_stack_size(const n_polyun_stack_t S)
1249 {
1250     return S->top;
1251 }
1252 
1253 #if !defined(FQ_NMOD_H)
1254 # undef fq_nmod_ctx_degree
1255 #endif
1256 
1257 #ifdef __cplusplus
1258 }
1259 #endif
1260 
1261 #endif
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!