include/flint/nmod_poly.h

0001 /*
0002     Copyright (C) 2007, David Howden
0003     Copyright (C) 2010, 2011 William Hart
0004     Copyright (C) 2011 Sebastian Pancratz
0005     Copyright (C) 2011 Fredrik Johansson
0006     Copyright (C) 2014 Ashish Kedia
0007
0008     This file is part of FLINT.
0009
0010     FLINT is free software: you can redistribute it and/or modify it under
0011     the terms of the GNU Lesser General Public License (LGPL) as published
0012     by the Free Software Foundation; either version 3 of the License, or
0013     (at your option) any later version.  See <https://www.gnu.org/licenses/>.
0014 */
0015
0016 #ifndef NMOD_POLY_H
0017 #define NMOD_POLY_H
0018
0019 #ifdef NMOD_POLY_INLINES_C
0020 #define NMOD_POLY_INLINE
0021 #else
0022 #define NMOD_POLY_INLINE static inline
0023 #endif
0024
0025 #include "nmod_types.h"
0026
0027 #ifdef __cplusplus
0028 extern "C" {
0029 #endif
0030
0031 typedef struct
0032 {
0033    ulong res;
0034    ulong lc;
0035    slong len0;
0036    slong len1;
0037    slong off;
0038 } nmod_poly_res_struct;
0039
0040 typedef nmod_poly_res_struct nmod_poly_res_t[1];
0041
0042 typedef struct
0043 {
0044     nmod_mat_struct * A;
0045     nmod_poly_struct * poly1;
0046     nmod_poly_struct * poly2;
0047     nmod_poly_struct * poly2inv;
0048 }
0049 nmod_poly_matrix_precompute_arg_t;
0050
0051 typedef struct
0052 {
0053     nmod_mat_struct * A;
0054     nmod_poly_struct * res;
0055     nmod_poly_struct * poly1;
0056     nmod_poly_struct * poly3;
0057     nmod_poly_struct * poly3inv;
0058 }
0059 nmod_poly_compose_mod_precomp_preinv_arg_t;
0060
0061 typedef struct
0062 {
0063     nn_ptr ev_s;            /* evaluate: scaling constants */
0064     nmod_poly_t ev_f;       /* evaluate: polynomial */
0065     nn_ptr int_s1, int_s2;  /* interpolate: scaling constants */
0066     nmod_poly_t int_f;      /* interpolate: polynomial */
0067     nmod_poly_t ext_ff;     /* extrapolate forward: polynomial  */
0068     nmod_poly_t ext_fb;     /* extrapolate backward: polynomial */
0069     nn_ptr ext_s1f;         /* extrapolate: forward scaling constant  */
0070     nn_ptr ext_s1b;         /* extrapolate: backward scaling constant */
0071     nn_ptr ext_s2, ext_s3;  /* extrapolate: shared scaling constants */
0072     nmod_t mod;             /* modulus */
0073     slong len;              /* number of points */
0074     ulong function;         /* choice of precomputations */
0075 } nmod_geometric_progression_struct;
0076
0077 typedef nmod_geometric_progression_struct nmod_geometric_progression_t[1];
0078
0079 /* Memory management  ********************************************************/
0080
0081 void nmod_poly_init(nmod_poly_t poly, ulong n);
0082 void nmod_poly_init_preinv(nmod_poly_t poly, ulong n, ulong ninv);
0083
0084 void nmod_poly_init2(nmod_poly_t poly, ulong n, slong alloc);
0085 void nmod_poly_init2_preinv(nmod_poly_t poly, ulong n, ulong ninv, slong alloc);
0086
0087 void nmod_poly_realloc(nmod_poly_t poly, slong alloc);
0088
0089 void nmod_poly_clear(nmod_poly_t poly);
0090
0091 void nmod_poly_fit_length(nmod_poly_t poly, slong alloc);
0092
0093 NMOD_POLY_INLINE
0094 void nmod_poly_init_mod(nmod_poly_t poly, const nmod_t mod)
0095 {
0096     poly->coeffs = NULL;
0097     poly->alloc = 0;
0098     poly->length = 0;
0099     poly->mod = mod;
0100 }
0101
0102 NMOD_POLY_INLINE
0103 void nmod_poly_set_mod(nmod_poly_t poly, const nmod_t mod)
0104 {
0105     poly->mod = mod;
0106 }
0107
0108 NMOD_POLY_INLINE
0109 void _nmod_poly_set_length(nmod_poly_t poly, slong len)
0110 {
0111     poly->length = len;
0112 }
0113
0114 NMOD_POLY_INLINE
0115 void _nmod_poly_normalise(nmod_poly_t poly)
0116 {
0117     while (poly->length && (poly->coeffs[poly->length - 1] == WORD(0)))
0118         poly->length--;
0119 }
0120
0121 /* Polynomial parameters  ****************************************************/
0122
0123 NMOD_POLY_INLINE
0124 slong nmod_poly_length(const nmod_poly_t poly)
0125 {
0126     return poly->length;
0127 }
0128
0129 NMOD_POLY_INLINE
0130 slong nmod_poly_degree(const nmod_poly_t poly)
0131 {
0132     return poly->length - 1;
0133 }
0134
0135 NMOD_POLY_INLINE
0136 ulong nmod_poly_modulus(const nmod_poly_t poly)
0137 {
0138     return poly->mod.n;
0139 }
0140
0141 flint_bitcnt_t nmod_poly_max_bits(const nmod_poly_t poly);
0142
0143 NMOD_POLY_INLINE
0144 nn_ptr nmod_poly_lead(const nmod_poly_t poly)
0145 {
0146     if (poly->length)
0147         return poly->coeffs + (poly->length - 1);
0148     else
0149         return NULL;
0150 }
0151
0152 /* Assignment and basic manipulation  ****************************************/
0153
0154 void nmod_poly_set(nmod_poly_t a, const nmod_poly_t b);
0155
0156 NMOD_POLY_INLINE
0157 void nmod_poly_swap(nmod_poly_t poly1, nmod_poly_t poly2)
0158 {
0159     FLINT_SWAP(nmod_poly_struct, *poly1, *poly2);
0160 }
0161
0162 NMOD_POLY_INLINE
0163 void nmod_poly_zero(nmod_poly_t res)
0164 {
0165     res->length = 0;
0166 }
0167
0168 NMOD_POLY_INLINE
0169 void nmod_poly_one(nmod_poly_t res)
0170 {
0171     nmod_poly_fit_length(res, 1);
0172     res->length = (res->mod.n != UWORD(1));
0173     res->coeffs[0] = 1;
0174 }
0175
0176 void nmod_poly_set_trunc(nmod_poly_t res, const nmod_poly_t poly, slong len);
0177
0178 NMOD_POLY_INLINE
0179 void nmod_poly_truncate(nmod_poly_t poly, slong len)
0180 {
0181     nmod_poly_set_trunc(poly, poly, len);
0182 }
0183
0184 void _nmod_poly_reverse(nn_ptr output, nn_srcptr input, slong len, slong m);
0185 void nmod_poly_reverse(nmod_poly_t output, const nmod_poly_t input, slong m);
0186
0187 /* Comparison  ***************************************************************/
0188
0189 int nmod_poly_equal(const nmod_poly_t a, const nmod_poly_t b);
0190
0191 int nmod_poly_equal_nmod(const nmod_poly_t poly, ulong cst);
0192 int nmod_poly_equal_ui(const nmod_poly_t poly, ulong cst);
0193
0194 int nmod_poly_equal_trunc(const nmod_poly_t poly1, const nmod_poly_t poly2, slong n);
0195
0196 NMOD_POLY_INLINE
0197 int nmod_poly_is_zero(const nmod_poly_t poly)
0198 {
0199     return (poly->length == 0);
0200 }
0201
0202 NMOD_POLY_INLINE
0203 int nmod_poly_is_one(const nmod_poly_t poly)
0204 {
0205     return (poly->mod.n == UWORD(1)) || (poly->length == 1 && poly->coeffs[0] == 1);
0206 }
0207
0208 /* bogus for non-prime modulus */
0209 NMOD_POLY_INLINE
0210 int nmod_poly_is_unit(const nmod_poly_t poly)
0211 {
0212     return (poly->mod.n == UWORD(1)) || ((poly->length == 1) && poly->coeffs[0] != 0);
0213 }
0214
0215 NMOD_POLY_INLINE
0216 int nmod_poly_is_gen(const nmod_poly_t poly)
0217 {
0218     return (poly->mod.n == UWORD(1)) ||
0219            (poly->length == 2 && poly->coeffs[0] == 0 && poly->coeffs[1] == 1);
0220 }
0221
0222 NMOD_POLY_INLINE
0223 int nmod_poly_is_monic(const nmod_poly_t poly)
0224 {
0225     return (poly->length && poly->coeffs[(poly->length - 1)] == 1);
0226 }
0227
0228 /* Randomisation  ************************************************************/
0229
0230 void nmod_poly_randtest(nmod_poly_t poly, flint_rand_t state, slong len);
0231
0232 NMOD_POLY_INLINE
0233 void nmod_poly_randtest_not_zero(nmod_poly_t poly, flint_rand_t state, slong len)
0234 {
0235     do {
0236         nmod_poly_randtest(poly, state, len);
0237     } while (nmod_poly_is_zero(poly));
0238 }
0239
0240 /* Construction of irreducibles *********************************************/
0241
0242 void nmod_poly_minimal_irreducible(nmod_poly_t res, ulong n);
0243
0244 void nmod_poly_randtest_irreducible(nmod_poly_t poly, flint_rand_t state, slong len);
0245
0246 void nmod_poly_randtest_monic(nmod_poly_t poly, flint_rand_t state, slong len);
0247 void nmod_poly_randtest_monic_irreducible(nmod_poly_t poly, flint_rand_t state, slong len);
0248 void nmod_poly_randtest_monic_primitive(nmod_poly_t poly, flint_rand_t state, slong len);
0249
0250 void nmod_poly_randtest_trinomial(nmod_poly_t poly, flint_rand_t state, slong len);
0251 int nmod_poly_randtest_trinomial_irreducible(nmod_poly_t poly, flint_rand_t state, slong len, slong max_attempts);
0252
0253 void nmod_poly_randtest_pentomial(nmod_poly_t poly, flint_rand_t state, slong len);
0254 int nmod_poly_randtest_pentomial_irreducible(nmod_poly_t poly, flint_rand_t state, slong len, slong max_attempts);
0255
0256 void nmod_poly_randtest_sparse_irreducible(nmod_poly_t poly, flint_rand_t state, slong len);
0257
0258 /* Getting and setting coefficients  *****************************************/
0259
0260 NMOD_POLY_INLINE
0261 ulong nmod_poly_get_coeff_ui(const nmod_poly_t poly, slong j)
0262 {
0263     return (j >= poly->length) ? 0 : poly->coeffs[j];
0264 }
0265
0266 void nmod_poly_set_coeff_ui(nmod_poly_t poly, slong j, ulong c);
0267
0268 /* Input and output  *********************************************************/
0269
0270 char * nmod_poly_get_str(const nmod_poly_t poly);
0271
0272 char * nmod_poly_get_str_pretty(const nmod_poly_t poly, const char * x);
0273
0274 int nmod_poly_set_str(nmod_poly_t poly, const char * s);
0275
0276 #ifdef FLINT_HAVE_FILE
0277 int nmod_poly_fprint(FILE * f, const nmod_poly_t poly);
0278 int nmod_poly_fprint_pretty(FILE * f, const nmod_poly_t a, const char * x);
0279
0280 int nmod_poly_fread(FILE * f, nmod_poly_t poly);
0281 #endif
0282
0283 int nmod_poly_print(const nmod_poly_t a);
0284 int nmod_poly_print_pretty(const nmod_poly_t a, const char * x);
0285
0286 int nmod_poly_read(nmod_poly_t poly);
0287
0288 /* Shifting  *****************************************************************/
0289
0290 void _nmod_poly_shift_left(nn_ptr res, nn_srcptr poly, slong len, slong k);
0291 void nmod_poly_shift_left(nmod_poly_t res, const nmod_poly_t poly, slong k);
0292
0293 void _nmod_poly_shift_right(nn_ptr res, nn_srcptr poly, slong len, slong k);
0294 void nmod_poly_shift_right(nmod_poly_t res, const nmod_poly_t poly, slong k);
0295
0296 /* Addition and subtraction  *************************************************/
0297
0298 void _nmod_poly_add(nn_ptr res, nn_srcptr poly1, slong len1, nn_srcptr poly2, slong len2, nmod_t mod);
0299 void nmod_poly_add(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2);
0300
0301 void _nmod_poly_sub(nn_ptr res, nn_srcptr poly1, slong len1, nn_srcptr poly2, slong len2, nmod_t mod);
0302 void nmod_poly_sub(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2);
0303
0304 void nmod_poly_add_series(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2, slong n);
0305 void nmod_poly_sub_series(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2, slong n);
0306
0307 void nmod_poly_add_ui(nmod_poly_t res, const nmod_poly_t poly, ulong c);
0308 void nmod_poly_sub_ui(nmod_poly_t res, const nmod_poly_t poly, ulong c);
0309
0310 void nmod_poly_neg(nmod_poly_t res, const nmod_poly_t poly1);
0311
0312 /* Scalar multiplication and division  ***************************************/
0313
0314 void nmod_poly_scalar_mul_nmod(nmod_poly_t res, const nmod_poly_t poly, ulong c);
0315
0316 void nmod_poly_scalar_addmul_nmod(nmod_poly_t res, const nmod_poly_t poly, ulong c);
0317
0318 void _nmod_poly_make_monic(nn_ptr output, nn_srcptr input, slong len, nmod_t mod);
0319 void nmod_poly_make_monic(nmod_poly_t output, const nmod_poly_t input);
0320
0321 /* Bit packing and unpacking aand reduction  **********************************/
0322
0323 void _nmod_poly_KS2_pack1(nn_ptr res, nn_srcptr op, slong n, slong s, ulong b, ulong k, slong r);
0324 void _nmod_poly_KS2_pack(nn_ptr res, nn_srcptr op, slong n, slong s, ulong b, ulong k, slong r);
0325
0326 void _nmod_poly_KS2_unpack1(nn_ptr res, nn_srcptr op, slong n, ulong b, ulong k);
0327 void _nmod_poly_KS2_unpack2(nn_ptr res, nn_srcptr op, slong n, ulong b, ulong k);
0328 void _nmod_poly_KS2_unpack3(nn_ptr res, nn_srcptr op, slong n, ulong b, ulong k);
0329 void _nmod_poly_KS2_unpack(nn_ptr res, nn_srcptr op, slong n, ulong b, ulong k);
0330
0331 void _nmod_poly_KS2_reduce(nn_ptr res, slong s, nn_srcptr op, slong n, ulong w, nmod_t mod);
0332
0333 void _nmod_poly_KS2_recover_reduce1(nn_ptr res, slong s, nn_srcptr op1, nn_srcptr op2, slong n, ulong b, nmod_t mod);
0334 void _nmod_poly_KS2_recover_reduce2(nn_ptr res, slong s, nn_srcptr op1, nn_srcptr op2, slong n, ulong b, nmod_t mod);
0335 void _nmod_poly_KS2_recover_reduce2b(nn_ptr res, slong s, nn_srcptr op1, nn_srcptr op2, slong n, ulong FLINT_UNUSED(b), nmod_t mod);
0336 void _nmod_poly_KS2_recover_reduce3(nn_ptr res, slong s, nn_srcptr op1, nn_srcptr op2, slong n, ulong b, nmod_t mod);
0337 void _nmod_poly_KS2_recover_reduce(nn_ptr res, slong s, nn_srcptr op1, nn_srcptr op2, slong n, ulong b, nmod_t mod);
0338
0339 void _nmod_poly_bit_pack(nn_ptr res, nn_srcptr poly, slong len, flint_bitcnt_t bits);
0340 void nmod_poly_bit_pack(fmpz_t f, const nmod_poly_t poly, flint_bitcnt_t bit_size);
0341
0342 void _nmod_poly_bit_unpack(nn_ptr res, slong nlo, slong nhi, nn_srcptr mpn, flint_bitcnt_t bits, nmod_t mod);
0343 void nmod_poly_bit_unpack(nmod_poly_t poly, const fmpz_t f, flint_bitcnt_t bit_size);
0344
0345 /* Multiplication  ***********************************************************/
0346
0347 void _nmod_poly_mul_classical(nn_ptr res, nn_srcptr poly1, slong len1, nn_srcptr poly2, slong len2, nmod_t mod);
0348 void nmod_poly_mul_classical(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2);
0349
0350 void _nmod_poly_mullow_classical(nn_ptr res, nn_srcptr poly1, slong len1, nn_srcptr poly2, slong len2, slong trunc, nmod_t mod);
0351 void nmod_poly_mullow_classical(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2, slong trunc);
0352
0353 void _nmod_poly_mulhigh_classical(nn_ptr res, nn_srcptr poly1, slong len1, nn_srcptr poly2, slong len2, slong start, nmod_t mod);
0354 void nmod_poly_mulhigh_classical(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2, slong start);
0355
0356 void _nmod_poly_mul_KS(nn_ptr out, nn_srcptr in1, slong len1, nn_srcptr in2, slong len2, nmod_t mod);
0357 void nmod_poly_mul_KS(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2);
0358
0359 void _nmod_poly_mul_KS2(nn_ptr res, nn_srcptr op1, slong n1, nn_srcptr op2, slong n2, nmod_t mod);
0360 void nmod_poly_mul_KS2(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2);
0361
0362 void _nmod_poly_mul_KS4(nn_ptr res, nn_srcptr op1, slong n1, nn_srcptr op2, slong n2, nmod_t mod);
0363 void nmod_poly_mul_KS4(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2);
0364
0365 void _nmod_poly_mullow_KS(nn_ptr out, nn_srcptr in1, slong len1, nn_srcptr in2, slong len2, slong n, nmod_t mod);
0366 void nmod_poly_mullow_KS(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2, slong n);
0367
0368 void _nmod_poly_mul(nn_ptr res, nn_srcptr poly1, slong len1, nn_srcptr poly2, slong len2, nmod_t mod);
0369 void nmod_poly_mul(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2);
0370
0371 int _nmod_poly_mulmid_fft_small_repack(nn_ptr z, nn_srcptr a, slong an, nn_srcptr b, slong bn, slong znlo, slong zn, nmod_t mod);
0372 int _nmod_poly_mullow_want_fft_small(slong len1, slong len2, slong n, int squaring, nmod_t mod);
0373
0374 void _nmod_poly_mulmid_fft_small(nn_ptr z, nn_srcptr a, slong an, nn_srcptr b, slong bn, slong znlo, slong zn, nmod_t mod);
0375 void _nmod_poly_mullow_fft_small(nn_ptr z, nn_srcptr a, slong an, nn_srcptr b, slong bn, slong zn, nmod_t mod);
0376
0377 void _nmod_poly_mullow(nn_ptr res, nn_srcptr poly1, slong len1, nn_srcptr poly2, slong len2, slong trunc, nmod_t mod);
0378 void nmod_poly_mullow(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2, slong trunc);
0379
0380 void _nmod_poly_mulmid_classical(nn_ptr res, nn_srcptr poly1, slong len1, nn_srcptr poly2, slong len2, slong nlo, slong nhi, nmod_t mod);
0381 void nmod_poly_mulmid_classical(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2, slong nlo, slong nhi);
0382 void _nmod_poly_mulmid_KS(nn_ptr res, nn_srcptr poly1, slong len1, nn_srcptr poly2, slong len2, slong nlo, slong nhi, nmod_t mod);
0383 void nmod_poly_mulmid_KS(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2, slong nlo, slong nhi);
0384 void _nmod_poly_mulmid(nn_ptr res, nn_srcptr poly1, slong len1, nn_srcptr poly2, slong len2, slong nlo, slong nhi, nmod_t mod);
0385 void nmod_poly_mulmid(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2, slong nlo, slong nhi);
0386
0387 void _nmod_poly_mulhigh(nn_ptr res, nn_srcptr poly1, slong len1, nn_srcptr poly2, slong len2, slong n, nmod_t mod);
0388 void nmod_poly_mulhigh(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2, slong n);
0389
0390 void _nmod_poly_mulmod(nn_ptr res, nn_srcptr poly1, slong len1, nn_srcptr poly2, slong len2, nn_srcptr f, slong lenf, nmod_t mod);
0391 void nmod_poly_mulmod(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2, const nmod_poly_t f);
0392
0393 void _nmod_poly_mulmod_preinv(nn_ptr res, nn_srcptr poly1, slong len1, nn_srcptr poly2, slong len2, nn_srcptr f, slong lenf, nn_srcptr finv, slong lenfinv, nmod_t mod);
0394 void nmod_poly_mulmod_preinv(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2, const nmod_poly_t f, const nmod_poly_t finv);
0395
0396 int _nmod_poly_invmod(ulong *A, const ulong *B, slong lenB, const ulong *P, slong lenP, const nmod_t mod);
0397 int nmod_poly_invmod(nmod_poly_t A, const nmod_poly_t B, const nmod_poly_t P);
0398
0399 /* Preconditioned modular multiplication *************************************/
0400
0401 #define NMOD_POLY_MULMOD_PRECOND_NONE 0
0402 #define NMOD_POLY_MULMOD_PRECOND_SHOUP 1
0403 #define NMOD_POLY_MULMOD_PRECOND_MATRIX 2
0404 /* TODO
0405 #define NMOD_POLY_MULMOD_PRECOND_SPARSE 3
0406 #define NMOD_POLY_MULMOD_PRECOND_FFT 4
0407 */
0408
0409 typedef struct
0410 {
0411     int method;
0412     slong n;          /* Degree of modulus */
0413
0414     nn_srcptr a;      /* Operand (important: shallow reference) */
0415     slong alen;
0416
0417     nn_srcptr d;      /* Modulus (important: shallow reference) */
0418     nn_srcptr dinv;   /* Modulus inverse (important: shallow reference) */
0419     slong lendinv;    /* Length of modulus inverse */
0420
0421     nn_ptr adivd;     /* Precomputed quotient a * x^n / d for Shoup. */
0422
0423     nn_ptr matrix;    /* Array of size ceil(n / packing) * n storing multiplication matrix */
0424     int packing;      /* Matrix entries per word: 1, 2, 3 or 4 */
0425     dot_params_t dot_params;
0426 }
0427 nmod_poly_mulmod_precond_struct;
0428
0429 typedef nmod_poly_mulmod_precond_struct nmod_poly_mulmod_precond_t[1];
0430
0431 void _nmod_poly_mulmod_precond_init_method(nmod_poly_mulmod_precond_t precond, nn_srcptr a, slong alen, nn_srcptr d, slong dlen, nn_srcptr dinv, slong lendinv, int method, nmod_t mod);
0432 void nmod_poly_mulmod_precond_init_method(nmod_poly_mulmod_precond_t precond, const nmod_poly_t a, const nmod_poly_t d, const nmod_poly_t dinv, int method);
0433 void _nmod_poly_mulmod_precond_init_num(nmod_poly_mulmod_precond_t precond, nn_srcptr a, slong alen, nn_srcptr d, slong dlen, nn_srcptr dinv, slong lendinv, slong num, nmod_t mod);
0434 void nmod_poly_mulmod_precond_init_num(nmod_poly_mulmod_precond_t precond, const nmod_poly_t a, const nmod_poly_t d, const nmod_poly_t dinv, slong num);
0435 void nmod_poly_mulmod_precond_clear(nmod_poly_mulmod_precond_t precond);
0436
0437 void _nmod_poly_mulmod_precond(nn_ptr res, const nmod_poly_mulmod_precond_t precond, nn_srcptr b, slong blen, nmod_t mod);
0438 void nmod_poly_mulmod_precond(nmod_poly_t res, const nmod_poly_mulmod_precond_t precond, const nmod_poly_t b);
0439
0440 /* Powering  *****************************************************************/
0441
0442 void _nmod_poly_pow_binexp(nn_ptr res, nn_srcptr poly, slong len, ulong e, nmod_t mod);
0443 void nmod_poly_pow_binexp(nmod_poly_t res, const nmod_poly_t poly, ulong e);
0444
0445 void _nmod_poly_pow(nn_ptr res, nn_srcptr poly, slong len, ulong e, nmod_t mod);
0446 void nmod_poly_pow(nmod_poly_t res, const nmod_poly_t poly, ulong e);
0447
0448 void _nmod_poly_pow_trunc_binexp(nn_ptr res, nn_srcptr poly, ulong e, slong trunc, nmod_t mod);
0449 void nmod_poly_pow_trunc_binexp(nmod_poly_t res, const nmod_poly_t poly, ulong e, slong trunc);
0450
0451 void _nmod_poly_pow_trunc(nn_ptr res, nn_srcptr poly, ulong e, slong trunc, nmod_t mod);
0452 void nmod_poly_pow_trunc(nmod_poly_t res, const nmod_poly_t poly, ulong e, slong trunc);
0453
0454 void _nmod_poly_powmod_ui_binexp(nn_ptr res, nn_srcptr poly, ulong e, nn_srcptr f, slong lenf, nmod_t mod);
0455 void nmod_poly_powmod_ui_binexp(nmod_poly_t res, const nmod_poly_t poly, ulong e, const nmod_poly_t f);
0456
0457 void _nmod_poly_powmod_fmpz_binexp(nn_ptr res, nn_srcptr poly, fmpz_t e, nn_srcptr f, slong lenf, nmod_t mod);
0458 void nmod_poly_powmod_fmpz_binexp(nmod_poly_t res, const nmod_poly_t poly, fmpz_t e, const nmod_poly_t f);
0459
0460 void _nmod_poly_powmod_ui_binexp_preinv (nn_ptr res, nn_srcptr poly, ulong e, nn_srcptr f, slong lenf, nn_srcptr finv, slong lenfinv, nmod_t mod);
0461 void nmod_poly_powmod_ui_binexp_preinv(nmod_poly_t res, const nmod_poly_t poly, ulong e, const nmod_poly_t f, const nmod_poly_t finv);
0462
0463 void _nmod_poly_powmod_fmpz_binexp_preinv (nn_ptr res, nn_srcptr poly, fmpz_t e, nn_srcptr f, slong lenf, nn_srcptr finv, slong lenfinv, nmod_t mod);
0464 void nmod_poly_powmod_fmpz_binexp_preinv(nmod_poly_t res, const nmod_poly_t poly, fmpz_t e, const nmod_poly_t f, const nmod_poly_t finv);
0465
0466 void _nmod_poly_powmod_x_ui_preinv (nn_ptr res, ulong e, nn_srcptr f, slong lenf, nn_srcptr finv, slong lenfinv, nmod_t mod);
0467 void nmod_poly_powmod_x_ui_preinv(nmod_poly_t res, ulong e, const nmod_poly_t f, const nmod_poly_t finv);
0468
0469 void _nmod_poly_powmod_x_fmpz_preinv (nn_ptr res, fmpz_t e, nn_srcptr f, slong lenf, nn_srcptr finv, slong lenfinv, nmod_t mod);
0470 void nmod_poly_powmod_x_fmpz_preinv(nmod_poly_t res, fmpz_t e, const nmod_poly_t f,                             const nmod_poly_t finv);
0471
0472 void _nmod_poly_powers_mod_preinv_naive(nn_ptr * res, nn_srcptr f,
0473                                         slong flen, slong n, nn_srcptr g, slong glen, nn_srcptr ginv,
0474                                         slong ginvlen, const nmod_t mod);
0475
0476 void nmod_poly_powers_mod_naive(nmod_poly_struct * res,
0477                             const nmod_poly_t f, slong n, const nmod_poly_t g);
0478
0479 void _nmod_poly_powers_mod_preinv_threaded_pool(nn_ptr * res,
0480                                                 nn_srcptr f, slong flen, slong n, nn_srcptr g, slong glen,
0481                                                 nn_srcptr ginv, slong ginvlen, const nmod_t mod,
0482                                                 thread_pool_handle * threads, slong num_threads);
0483
0484 void
0485 _nmod_poly_powers_mod_preinv_threaded(nn_ptr * res, nn_srcptr f,
0486                                       slong flen, slong n, nn_srcptr g, slong glen,
0487                               nn_srcptr ginv, slong ginvlen, const nmod_t mod);
0488
0489 void nmod_poly_powers_mod_bsgs(nmod_poly_struct * res,
0490                             const nmod_poly_t f, slong n, const nmod_poly_t g);
0491
0492 /* Division  *****************************************************************/
0493
0494 void _nmod_poly_divrem_q1_preinv1(nn_ptr Q, nn_ptr R, nn_srcptr A, slong lenA, nn_srcptr B, slong lenB, ulong invL, nmod_t mod);
0495 void _nmod_poly_divrem_basecase_preinv1(nn_ptr Q, nn_ptr R, nn_srcptr A, slong A_len, nn_srcptr B, slong B_len, ulong invB, nmod_t mod);
0496
0497 void _nmod_poly_divrem_basecase(nn_ptr Q, nn_ptr R, nn_srcptr A, slong A_len, nn_srcptr B, slong B_len, nmod_t mod);
0498 void nmod_poly_divrem_basecase(nmod_poly_t Q, nmod_poly_t R, const nmod_poly_t A, const nmod_poly_t B);
0499
0500 void _nmod_poly_divrem(nn_ptr Q, nn_ptr R, nn_srcptr A, slong lenA, nn_srcptr B, slong lenB, nmod_t mod);
0501 void nmod_poly_divrem(nmod_poly_t Q, nmod_poly_t R, const nmod_poly_t A, const nmod_poly_t B);
0502
0503 void _nmod_poly_div(nn_ptr Q, nn_srcptr A, slong lenA, nn_srcptr B, slong lenB, nmod_t mod);
0504 void nmod_poly_div(nmod_poly_t Q, const nmod_poly_t A, const nmod_poly_t B);
0505
0506 void _nmod_poly_rem(nn_ptr R, nn_srcptr A, slong lenA, nn_srcptr B, slong lenB, nmod_t mod);
0507 void nmod_poly_rem(nmod_poly_t R, const nmod_poly_t A, const nmod_poly_t B);
0508
0509 void _nmod_poly_divexact(nn_ptr Q, nn_srcptr A, slong lenA, nn_srcptr B, slong lenB, nmod_t mod);
0510 void nmod_poly_divexact(nmod_poly_t Q, const nmod_poly_t A, const nmod_poly_t B);
0511
0512 void _nmod_poly_inv_series_basecase(nn_ptr Qinv, nn_srcptr Q, slong Qlen, slong n, nmod_t mod);
0513 void nmod_poly_inv_series_basecase(nmod_poly_t Qinv, const nmod_poly_t Q, slong n);
0514
0515 void _nmod_poly_inv_series_newton(nn_ptr Qinv, nn_srcptr Q, slong Qlen, slong n, nmod_t mod);
0516 void nmod_poly_inv_series_newton(nmod_poly_t Qinv, const nmod_poly_t Q, slong n);
0517
0518 void _nmod_poly_inv_series(nn_ptr Qinv, nn_srcptr Q, slong Qlen, slong n, nmod_t mod);
0519 void nmod_poly_inv_series(nmod_poly_t Qinv, const nmod_poly_t Q, slong n);
0520
0521 void _nmod_poly_div_series_basecase(nn_ptr Q, nn_srcptr A, slong Alen, nn_srcptr B, slong Blen, slong n, nmod_t mod);
0522 void nmod_poly_div_series_basecase(nmod_poly_t Q, const nmod_poly_t A, const nmod_poly_t B, slong n);
0523
0524 void _nmod_poly_div_series(nn_ptr Q, nn_srcptr A, slong Alen, nn_srcptr B, slong Blen, slong n, nmod_t mod);
0525 void nmod_poly_div_series(nmod_poly_t Q, const nmod_poly_t A, const nmod_poly_t B, slong n);
0526
0527 void _nmod_poly_div_newton_n_preinv(nn_ptr Q, nn_srcptr A, slong lenA, nn_srcptr FLINT_UNUSED(B), slong lenB, nn_srcptr Binv, slong lenBinv, nmod_t mod);
0528 void nmod_poly_div_newton_n_preinv (nmod_poly_t Q, const nmod_poly_t A, const nmod_poly_t B, const nmod_poly_t Binv);
0529
0530 void _nmod_poly_divrem_newton_n_preinv (nn_ptr Q, nn_ptr R, nn_srcptr A, slong lenA, nn_srcptr B, slong lenB, nn_srcptr Binv, slong lenBinv, nmod_t mod);
0531 void nmod_poly_divrem_newton_n_preinv(nmod_poly_t Q, nmod_poly_t R, const nmod_poly_t A, const nmod_poly_t B, const nmod_poly_t Binv);
0532
0533 ulong _nmod_poly_div_root(nn_ptr Q, nn_srcptr A, slong len, ulong c, nmod_t mod);
0534
0535 ulong nmod_poly_div_root(nmod_poly_t Q, const nmod_poly_t A, ulong c);
0536
0537 /* Divisibility testing  *****************************************************/
0538
0539 int _nmod_poly_divides_classical(nn_ptr Q, nn_srcptr A, slong lenA, nn_srcptr B, slong lenB, nmod_t mod);
0540 int nmod_poly_divides_classical(nmod_poly_t Q, const nmod_poly_t A, const nmod_poly_t B);
0541
0542 int _nmod_poly_divides(nn_ptr Q, nn_srcptr A, slong lenA, nn_srcptr B, slong lenB, nmod_t mod);
0543 int nmod_poly_divides(nmod_poly_t Q, const nmod_poly_t A, const nmod_poly_t B);
0544
0545 ulong nmod_poly_remove(nmod_poly_t f, const nmod_poly_t p);
0546
0547 /* Derivative  ***************************************************************/
0548
0549 void _nmod_poly_derivative(nn_ptr x_prime, nn_srcptr x, slong len, nmod_t mod);
0550 void nmod_poly_derivative(nmod_poly_t x_prime, const nmod_poly_t x);
0551
0552 void _nmod_poly_integral(nn_ptr x_int, nn_srcptr x, slong len, nmod_t mod);
0553 void nmod_poly_integral(nmod_poly_t x_int, const nmod_poly_t x);
0554
0555 /* Evaluation  ***************************************************************/
0556
0557 ulong _nmod_poly_evaluate_nmod_horner(nn_srcptr poly, slong len, ulong c, nmod_t mod);
0558 ulong _nmod_poly_evaluate_nmod_rectangular(nn_srcptr poly, slong len, ulong c, nmod_t mod);
0559 ulong _nmod_poly_evaluate_nmod(nn_srcptr poly, slong len, ulong c, nmod_t mod);
0560 ulong _nmod_poly_evaluate_nmod_precomp(nn_srcptr poly, slong len, ulong c, ulong c_precomp, ulong modn);
0561 ulong _nmod_poly_evaluate_nmod_precomp_lazy(nn_srcptr poly, slong len, ulong c, ulong c_precomp, ulong modn);
0562 ulong nmod_poly_evaluate_nmod(const nmod_poly_t poly, ulong c);
0563
0564 void _nmod_poly_evaluate_nmod_vec(nn_ptr ys, nn_srcptr coeffs, slong ilen, nn_srcptr xs, slong olen, nmod_t mod);
0565 void nmod_poly_evaluate_nmod_vec(nn_ptr ys, const nmod_poly_t poly, nn_srcptr xs, slong olen);
0566
0567 void _nmod_poly_evaluate_nmod_vec_iter(nn_ptr ys, nn_srcptr coeffs, slong ilen, nn_srcptr xs, slong olen, nmod_t mod);
0568 void nmod_poly_evaluate_nmod_vec_iter(nn_ptr ys, const nmod_poly_t poly, nn_srcptr xs, slong olen);
0569
0570 void _nmod_poly_evaluate_nmod_vec_fast_precomp(nn_ptr vs, nn_srcptr poly, slong ilen, const nn_ptr * tree, slong olen, nmod_t mod);
0571
0572 void _nmod_poly_evaluate_nmod_vec_fast(nn_ptr ys, nn_srcptr coeffs, slong ilen, nn_srcptr xs, slong olen, nmod_t mod);
0573 void nmod_poly_evaluate_nmod_vec_fast(nn_ptr ys, const nmod_poly_t poly, nn_srcptr xs, slong olen);
0574
0575 void nmod_mat_one_addmul(nmod_mat_t dest, const nmod_mat_t mat, ulong c);
0576
0577 void nmod_poly_evaluate_mat_horner(nmod_mat_t dest, const nmod_poly_t poly, const nmod_mat_t c);
0578
0579 void nmod_poly_evaluate_mat_paterson_stockmeyer(nmod_mat_t dest, const nmod_poly_t poly, const nmod_mat_t c);
0580
0581 NMOD_POLY_INLINE
0582 void nmod_poly_evaluate_mat(nmod_mat_t dest, const nmod_poly_t poly, const nmod_mat_t c)
0583 {
0584     if (poly->length < 5 || c->r * poly->length < 425)
0585     {
0586         nmod_poly_evaluate_mat_horner(dest, poly, c);
0587     }
0588     else
0589     {
0590         nmod_poly_evaluate_mat_paterson_stockmeyer(dest, poly, c);
0591     }
0592 }
0593
0594 /* Subproduct tree  **********************************************************/
0595
0596 nn_ptr * _nmod_poly_tree_alloc(slong len);
0597
0598 void _nmod_poly_tree_free(nn_ptr * tree, slong len);
0599
0600 void _nmod_poly_tree_build(nn_ptr * tree, nn_srcptr roots, slong len, nmod_t mod);
0601
0602 /* Geometric evaluation / interpolation / extrapolation *********************/
0603
0604 void _nmod_geometric_progression_init_function(nmod_geometric_progression_t G,
0605                                                ulong r, slong len, nmod_t mod,
0606                                                ulong function);
0607 void nmod_geometric_progression_init(nmod_geometric_progression_t G,
0608                                      ulong r, slong len, nmod_t mod);
0609
0610 void nmod_geometric_progression_clear(nmod_geometric_progression_t G);
0611
0612 void _nmod_poly_evaluate_geometric_nmod_vec_iter(nn_ptr ys, nn_srcptr coeffs, slong ilen, ulong r, slong olen, nmod_t mod);
0613 void nmod_poly_evaluate_geometric_nmod_vec_iter(nn_ptr ys, const nmod_poly_t poly, ulong r, slong olen);
0614
0615 void _nmod_poly_evaluate_geometric_nmod_vec_fast_precomp(nn_ptr vs, nn_srcptr poly, slong ilen, const nmod_geometric_progression_t G, slong olen, nmod_t mod);
0616 void _nmod_poly_evaluate_geometric_nmod_vec_fast(nn_ptr ys, nn_srcptr coeffs, slong ilen, ulong r, slong olen, nmod_t mod);
0617 void nmod_poly_evaluate_geometric_nmod_vec_fast(nn_ptr ys, const nmod_poly_t poly, ulong r, slong olen);
0618
0619 void _nmod_poly_interpolate_geometric_nmod_vec_fast_precomp(nn_ptr poly, nn_srcptr v, const nmod_geometric_progression_t G, slong len, nmod_t mod);
0620 void nmod_poly_interpolate_geometric_nmod_vec_fast_precomp(nmod_poly_t poly, nn_srcptr v, const nmod_geometric_progression_t G, slong len);
0621 void nmod_poly_interpolate_geometric_nmod_vec_fast(nmod_poly_t poly, ulong r, nn_srcptr ys, slong len);
0622
0623 void nmod_poly_extrapolate_geometric(nn_ptr oval, slong olen, nn_srcptr ival, slong ilen, slong offset, ulong r, nmod_t mod);
0624 void nmod_poly_extrapolate_geometric_precomp(nn_ptr oval, slong olen, nn_srcptr ival, slong ilen, slong offset, const nmod_geometric_progression_t G);
0625
0626 /* Interpolation  ************************************************************/
0627
0628 void _nmod_poly_interpolate_nmod_vec_newton(nn_ptr poly, nn_srcptr xs, nn_srcptr ys, slong len, nmod_t mod);
0629 void nmod_poly_interpolate_nmod_vec_newton(nmod_poly_t poly, nn_srcptr xs, nn_srcptr ys, slong n);
0630
0631 void _nmod_poly_interpolate_nmod_vec_barycentric(nn_ptr poly, nn_srcptr xs, nn_srcptr ys, slong len, nmod_t mod);
0632 void nmod_poly_interpolate_nmod_vec_barycentric(nmod_poly_t poly, nn_srcptr xs, nn_srcptr ys, slong len);
0633
0634 void _nmod_poly_interpolate_nmod_vec(nn_ptr poly, nn_srcptr xs, nn_srcptr ys, slong len, nmod_t mod);
0635 void nmod_poly_interpolate_nmod_vec(nmod_poly_t poly, nn_srcptr xs, nn_srcptr ys, slong len);
0636
0637 void _nmod_poly_interpolate_nmod_vec_fast(nn_ptr poly, nn_srcptr xs, nn_srcptr ys, slong len, nmod_t mod);
0638 void nmod_poly_interpolate_nmod_vec_fast(nmod_poly_t poly, nn_srcptr xs, nn_srcptr ys, slong len);
0639
0640 void _nmod_poly_interpolate_nmod_vec_fast_precomp(nn_ptr poly, nn_srcptr ys,
0641     const nn_ptr * tree, nn_srcptr weights, slong len, nmod_t mod);
0642
0643 void _nmod_poly_interpolation_weights(nn_ptr w, const nn_ptr * tree, slong len, nmod_t mod);
0644
0645 /* Composition  **************************************************************/
0646
0647 void _nmod_poly_compose_horner(nn_ptr res, nn_srcptr poly1, slong len1, nn_srcptr poly2, slong len2, nmod_t mod);
0648 void nmod_poly_compose_horner(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2);
0649
0650 void _nmod_poly_compose(nn_ptr res, nn_srcptr poly1, slong len1, nn_srcptr poly2, slong len2, nmod_t mod);
0651 void nmod_poly_compose(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2);
0652
0653 /* obsolete implementation */
0654 #define _nmod_poly_compose_divconquer _nmod_poly_compose
0655 #define nmod_poly_compose_divconquer nmod_poly_compose
0656
0657 /* Taylor shift  *************************************************************/
0658
0659 void _nmod_poly_taylor_shift_horner(nn_ptr poly, ulong c, slong len, nmod_t mod);
0660 void nmod_poly_taylor_shift_horner(nmod_poly_t g, const nmod_poly_t f, ulong c);
0661
0662 void _nmod_poly_taylor_shift_convolution(nn_ptr poly, ulong c, slong len, nmod_t mod);
0663 void nmod_poly_taylor_shift_convolution(nmod_poly_t g, const nmod_poly_t f, ulong c);
0664
0665 void _nmod_poly_taylor_shift(nn_ptr poly, ulong c, slong len, nmod_t mod);
0666 void nmod_poly_taylor_shift(nmod_poly_t g, const nmod_poly_t f, ulong c);
0667
0668 /* Modular composition  ******************************************************/
0669
0670 void _nmod_poly_mod_matrix_rows_evaluate(nn_ptr res, const nmod_mat_t A, nn_srcptr h, slong n, nn_srcptr poly3, slong len3,
0671     nn_srcptr poly3inv, slong len3inv, nmod_t mod);
0672
0673 void _nmod_poly_compose_mod_brent_kung(nn_ptr res, nn_srcptr f, slong lenf, nn_srcptr g, nn_srcptr h, slong lenh, nmod_t mod);
0674 void nmod_poly_compose_mod_brent_kung(nmod_poly_t res, const nmod_poly_t f, const nmod_poly_t g, const nmod_poly_t h);
0675
0676 void _nmod_poly_reduce_matrix_mod_poly(nmod_mat_t A, const nmod_mat_t B, const nmod_poly_t f);
0677
0678 void _nmod_poly_precompute_matrix(nmod_mat_t A, nn_srcptr poly1, nn_srcptr poly2,
0679                slong len2, nn_srcptr poly2inv, slong len2inv, nmod_t mod);
0680
0681 void _nmod_poly_precompute_matrix_worker(void * arg_ptr);
0682
0683 void nmod_poly_precompute_matrix(nmod_mat_t A, const nmod_poly_t poly1,
0684                           const nmod_poly_t poly2, const nmod_poly_t poly2inv);
0685
0686 void _nmod_poly_compose_mod_brent_kung_precomp_preinv(nn_ptr res, nn_srcptr poly1,
0687                             slong len1, const nmod_mat_t A, nn_srcptr poly3,
0688                             slong len3, nn_srcptr poly3inv, slong len3inv,
0689                             nmod_t mod);
0690
0691 void _nmod_poly_compose_mod_brent_kung_precomp_preinv_worker(void * arg_ptr);
0692
0693 void nmod_poly_compose_mod_brent_kung_precomp_preinv(nmod_poly_t res,
0694                     const nmod_poly_t poly1, const nmod_mat_t A,
0695                     const nmod_poly_t poly3, const nmod_poly_t poly3inv);
0696
0697 void _nmod_poly_compose_mod_brent_kung_preinv(nn_ptr res, nn_srcptr poly1, slong len1,
0698                             nn_srcptr poly2, nn_srcptr poly3, slong len3,
0699                             nn_srcptr poly3inv, slong len3inv, nmod_t mod);
0700
0701 void nmod_poly_compose_mod_brent_kung_preinv(nmod_poly_t res,
0702                     const nmod_poly_t poly1, const nmod_poly_t poly2,
0703                     const nmod_poly_t poly3, const nmod_poly_t poly3inv);
0704
0705 void
0706 _nmod_poly_compose_mod_brent_kung_vec_preinv(nmod_poly_struct * res,
0707         const nmod_poly_struct * polys, slong FLINT_UNUSED(lenpolys), slong l,
0708         nn_srcptr g, slong glen, nn_srcptr poly, slong len,
0709         nn_srcptr polyinv, slong leninv, nmod_t mod);
0710
0711 void nmod_poly_compose_mod_brent_kung_vec_preinv(nmod_poly_struct * res,
0712                     const nmod_poly_struct * polys, slong len1, slong n,
0713                     const nmod_poly_t g, const nmod_poly_t poly,
0714                     const nmod_poly_t polyinv);
0715
0716 void _nmod_poly_compose_mod_brent_kung_vec_preinv_worker(void * arg_ptr);
0717
0718 void
0719 nmod_poly_compose_mod_brent_kung_vec_preinv_threaded_pool(nmod_poly_struct * res,
0720            const nmod_poly_struct * polys, slong len1, slong n,
0721                           const nmod_poly_t g, const nmod_poly_t poly,
0722                      const nmod_poly_t polyinv, thread_pool_handle * threads,
0723                                                                 slong num_threads);
0724
0725 void _nmod_poly_compose_mod_brent_kung_vec_preinv_threaded_pool(
0726         nmod_poly_struct * res,
0727         const nmod_poly_struct * polys,
0728         slong FLINT_UNUSED(lenpolys), slong l,
0729         nn_srcptr g, slong glen,
0730         nn_srcptr poly, slong len,
0731         nn_srcptr polyinv, slong leninv,
0732         nmod_t mod,
0733         thread_pool_handle * threads,
0734         slong num_threads);
0735
0736 void nmod_poly_compose_mod_brent_kung_vec_preinv_threaded(
0737         nmod_poly_struct * res,
0738         const nmod_poly_struct * polys,
0739         slong len1, slong n,
0740         const nmod_poly_t g, const nmod_poly_t poly,
0741         const nmod_poly_t polyinv);
0742
0743 void _nmod_poly_compose_mod_horner(nn_ptr res, nn_srcptr f, slong lenf, nn_srcptr g, nn_srcptr h, slong lenh, nmod_t mod);
0744 void nmod_poly_compose_mod_horner(nmod_poly_t res, const nmod_poly_t f, const nmod_poly_t g, const nmod_poly_t h);
0745
0746 void _nmod_poly_compose_mod(nn_ptr res, nn_srcptr f, slong lenf, nn_srcptr g, nn_srcptr h, slong lenh, nmod_t mod);
0747 void nmod_poly_compose_mod(nmod_poly_t res, const nmod_poly_t f, const nmod_poly_t g, const nmod_poly_t h);
0748
0749 /* Power series composition and reversion ************************************/
0750
0751 void _nmod_poly_compose_series(nn_ptr res, nn_srcptr poly1, slong len1, nn_srcptr poly2, slong len2, slong n, nmod_t mod);
0752 void nmod_poly_compose_series(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2, slong n);
0753
0754 void _nmod_poly_revert_series(nn_ptr Qinv, nn_srcptr Q, slong Qlen, slong n, nmod_t mod);
0755 void nmod_poly_revert_series(nmod_poly_t Qinv, const nmod_poly_t Q, slong n);
0756
0757 /* norms *********************************************************************/
0758
0759 NMOD_POLY_INLINE slong _nmod_poly_hamming_weight(nn_srcptr a, slong len)
0760 {
0761     slong i, sum = 0;
0762     for (i = 0; i < len; i++)
0763         sum += !(a[i] == 0);
0764     return sum;
0765 }
0766
0767 NMOD_POLY_INLINE slong nmod_poly_hamming_weight(const nmod_poly_t A)
0768 {
0769     return _nmod_poly_hamming_weight(A->coeffs, A->length);
0770 }
0771
0772 /* Greatest common divisor  **************************************************/
0773
0774 /* HGCD: Basecase -> Recursion */
0775 slong nmod_poly_hgcd_iter_recursive_cutoff(nmod_t mod);
0776 /* HGCD: Euclidean -> HGCD */
0777 slong nmod_poly_hgcd_outer_cutoff(nmod_t mod);
0778 /* GCD:  Euclidean -> HGCD */
0779 slong nmod_poly_gcd_hgcd_cutoff(nmod_t mod);
0780 /* XGCD:  Euclidean -> HGCD */
0781 slong nmod_poly_xgcd_hgcd_cutoff(nmod_t mod);
0782
0783 /* Euclidean GCD: normal -> redc_fast */
0784 #define NMOD_POLY_GCD_EUCLIDEAN_USE_REDC_FAST(lenB, mod) (lenB >= 32 && NMOD_BITS(mod) >= FLINT_BITS / 2 && NMOD_BITS(mod) <= FLINT_BITS - 2)
0785
0786 slong _nmod_poly_gcd_euclidean(nn_ptr G, nn_srcptr A, slong lenA, nn_srcptr B, slong lenB, nmod_t mod);
0787 void nmod_poly_gcd_euclidean(nmod_poly_t G, const nmod_poly_t A, const nmod_poly_t B);
0788
0789 slong _nmod_poly_gcd_euclidean_redc_fast(nn_ptr G, nn_srcptr A, slong lenA, nn_srcptr B, slong lenB, nmod_t mod);
0790 void nmod_poly_gcd_euclidean_redc_fast(nmod_poly_t G, const nmod_poly_t A, const nmod_poly_t B);
0791
0792 slong _nmod_poly_hgcd_recursive(nn_ptr *M, slong *lenM, nn_ptr A, slong *lenA, nn_ptr B, slong *lenB, nn_srcptr a, slong lena, nn_srcptr b, slong lenb, nn_ptr P, nmod_t mod, int flag, nmod_poly_res_t res);
0793
0794 slong nmod_poly_hgcd_ref(nmod_poly_t m11, nmod_poly_t m12, nmod_poly_t m21, nmod_poly_t m22, nmod_poly_t A, nmod_poly_t B, const nmod_poly_t a, const nmod_poly_t b);
0795
0796 slong _nmod_poly_hgcd(nn_ptr *M, slong *lenM, nn_ptr A, slong *lenA, nn_ptr B, slong *lenB, nn_srcptr a, slong lena, nn_srcptr b, slong lenb, nmod_t mod);
0797 slong nmod_poly_hgcd(nmod_poly_t m11, nmod_poly_t m12, nmod_poly_t m21, nmod_poly_t m22, nmod_poly_t A, nmod_poly_t B, const nmod_poly_t a, const nmod_poly_t b);
0798
0799 slong _nmod_poly_gcd_hgcd(nn_ptr G, nn_srcptr A, slong lenA, nn_srcptr B, slong lenB, nmod_t mod);
0800 void nmod_poly_gcd_hgcd(nmod_poly_t G, const nmod_poly_t A, const nmod_poly_t B);
0801
0802 slong _nmod_poly_gcd(nn_ptr G, nn_srcptr A, slong lenA, nn_srcptr B, slong lenB, nmod_t mod);
0803 void nmod_poly_gcd(nmod_poly_t G, const nmod_poly_t A, const nmod_poly_t B);
0804
0805 slong _nmod_poly_xgcd_euclidean(nn_ptr res, nn_ptr s, nn_ptr t, nn_srcptr poly1, slong len1, nn_srcptr poly2, slong len2, nmod_t mod);
0806 void nmod_poly_xgcd_euclidean(nmod_poly_t G, nmod_poly_t S, nmod_poly_t T, const nmod_poly_t A, const nmod_poly_t B);
0807
0808 slong _nmod_poly_xgcd_hgcd(nn_ptr G, nn_ptr S, nn_ptr T, nn_srcptr A, slong lenA, nn_srcptr B, slong lenB, nmod_t mod);
0809 void nmod_poly_xgcd_hgcd(nmod_poly_t G, nmod_poly_t S, nmod_poly_t T, const nmod_poly_t A, const nmod_poly_t B);
0810
0811 slong _nmod_poly_xgcd(nn_ptr G, nn_ptr S, nn_ptr T, nn_srcptr A, slong lenA, nn_srcptr B, slong lenB, nmod_t mod);
0812 void nmod_poly_xgcd(nmod_poly_t G, nmod_poly_t S, nmod_poly_t T, const nmod_poly_t A, const nmod_poly_t B);
0813
0814 ulong _nmod_poly_resultant_euclidean(nn_srcptr poly1, slong len1, nn_srcptr poly2, slong len2, nmod_t mod);
0815 ulong nmod_poly_resultant_euclidean(const nmod_poly_t f, const nmod_poly_t g);
0816
0817 ulong _nmod_poly_resultant_hgcd(nn_srcptr A, slong lenA, nn_srcptr B, slong lenB, nmod_t mod);
0818 ulong nmod_poly_resultant_hgcd(const nmod_poly_t A, const nmod_poly_t B);
0819
0820 ulong _nmod_poly_resultant(nn_srcptr A, slong lenA, nn_srcptr B, slong lenB, nmod_t mod);
0821 ulong nmod_poly_resultant(const nmod_poly_t A, const nmod_poly_t B);
0822
0823 slong _nmod_poly_gcdinv(ulong *G, ulong *S, const ulong *A, slong lenA, const ulong *B, slong lenB, const nmod_t mod);
0824 void nmod_poly_gcdinv(nmod_poly_t G, nmod_poly_t S, const nmod_poly_t A, const nmod_poly_t B);
0825
0826 /* Discriminant **************************************************************/
0827
0828 ulong _nmod_poly_discriminant(nn_srcptr poly, slong len, nmod_t mod);
0829 ulong nmod_poly_discriminant(const nmod_poly_t f);
0830
0831 /* Square roots **************************************************************/
0832
0833 void _nmod_poly_invsqrt_series(nn_ptr g, nn_srcptr h, slong hlen, slong n, nmod_t mod);
0834 void nmod_poly_invsqrt_series(nmod_poly_t g, const nmod_poly_t h, slong n);
0835
0836 void _nmod_poly_sqrt_series(nn_ptr g, nn_srcptr h, slong hlen, slong n, nmod_t mod);
0837 void nmod_poly_sqrt_series(nmod_poly_t g, const nmod_poly_t h, slong n);
0838
0839 int _nmod_poly_sqrt(nn_ptr s, nn_srcptr p, slong len, nmod_t mod);
0840 int nmod_poly_sqrt(nmod_poly_t b, const nmod_poly_t a);
0841
0842 /* Power sums ****************************************************************/
0843
0844 void _nmod_poly_power_sums_naive(nn_ptr res, nn_srcptr poly, slong len, slong n, nmod_t mod);
0845 void nmod_poly_power_sums_naive(nmod_poly_t res, const nmod_poly_t poly, slong n);
0846
0847 void _nmod_poly_power_sums_schoenhage(nn_ptr res, nn_srcptr poly, slong len, slong n, nmod_t mod);
0848 void nmod_poly_power_sums_schoenhage(nmod_poly_t res, const nmod_poly_t poly, slong n);
0849
0850 void _nmod_poly_power_sums(nn_ptr res, nn_srcptr poly, slong len, slong n, nmod_t mod);
0851 void nmod_poly_power_sums(nmod_poly_t res, const nmod_poly_t poly, slong n);
0852
0853 void _nmod_poly_power_sums_to_poly_naive(nn_ptr res, nn_srcptr poly, slong len, nmod_t mod);
0854 void nmod_poly_power_sums_to_poly_naive(nmod_poly_t res, const nmod_poly_t Q);
0855
0856 void _nmod_poly_power_sums_to_poly_schoenhage(nn_ptr res, nn_srcptr poly, slong len, nmod_t mod);
0857 void nmod_poly_power_sums_to_poly_schoenhage(nmod_poly_t res, const nmod_poly_t Q);
0858
0859 void _nmod_poly_power_sums_to_poly(nn_ptr res, nn_srcptr poly, slong len, nmod_t mod);
0860 void nmod_poly_power_sums_to_poly(nmod_poly_t res, const nmod_poly_t Q);
0861
0862 /* Transcendental functions **************************************************/
0863
0864 void _nmod_poly_atan_series(nn_ptr g, nn_srcptr h, slong hlen, slong n, nmod_t mod);
0865 void nmod_poly_atan_series(nmod_poly_t g, const nmod_poly_t h, slong n);
0866
0867 void _nmod_poly_tan_series(nn_ptr g, nn_srcptr h, slong hlen, slong n, nmod_t mod);
0868 void nmod_poly_tan_series(nmod_poly_t g, const nmod_poly_t h, slong n);
0869
0870 void _nmod_poly_asin_series(nn_ptr g, nn_srcptr h, slong hlen, slong n, nmod_t mod);
0871 void nmod_poly_asin_series(nmod_poly_t g, const nmod_poly_t h, slong n);
0872
0873 void _nmod_poly_sin_series(nn_ptr g, nn_srcptr h, slong hlen, slong n, nmod_t mod);
0874 void nmod_poly_sin_series(nmod_poly_t g, const nmod_poly_t h, slong n);
0875
0876 void _nmod_poly_cos_series(nn_ptr g, nn_srcptr h, slong hlen, slong n, nmod_t mod);
0877 void nmod_poly_cos_series(nmod_poly_t g, const nmod_poly_t h, slong n);
0878
0879 void _nmod_poly_asinh_series(nn_ptr g, nn_srcptr h, slong hlen, slong n, nmod_t mod);
0880 void nmod_poly_asinh_series(nmod_poly_t g, const nmod_poly_t h, slong n);
0881
0882 void _nmod_poly_atanh_series(nn_ptr g, nn_srcptr h, slong hlen, slong n, nmod_t mod);
0883 void nmod_poly_atanh_series(nmod_poly_t g, const nmod_poly_t h, slong n);
0884
0885 void _nmod_poly_sinh_series(nn_ptr g, nn_srcptr h, slong n, nmod_t mod);
0886 void nmod_poly_sinh_series(nmod_poly_t g, const nmod_poly_t h, slong n);
0887
0888 void _nmod_poly_cosh_series(nn_ptr g, nn_srcptr h, slong n, nmod_t mod);
0889 void nmod_poly_cosh_series(nmod_poly_t g, const nmod_poly_t h, slong n);
0890
0891 void _nmod_poly_tanh_series(nn_ptr g, nn_srcptr h, slong hlen, slong n, nmod_t mod);
0892 void nmod_poly_tanh_series(nmod_poly_t g, const nmod_poly_t h, slong n);
0893
0894 void _nmod_poly_log_series(nn_ptr res, nn_srcptr f, slong flen, slong n, nmod_t mod);
0895 void nmod_poly_log_series(nmod_poly_t res, const nmod_poly_t f, slong n);
0896
0897 void  _nmod_poly_exp_expinv_series(nn_ptr f, nn_ptr g, nn_srcptr h, slong hlen, slong n, nmod_t mod);
0898 void _nmod_poly_exp_series(nn_ptr f, nn_srcptr h, slong hlen, slong n, nmod_t mod);
0899 void nmod_poly_exp_series(nmod_poly_t f, const nmod_poly_t h, slong n);
0900
0901 /* Special polynomials *******************************************************/
0902
0903 int _nmod_poly_conway(nn_ptr op, ulong prime, slong deg);
0904
0905 ulong _nmod_poly_conway_rand(slong * degree, flint_rand_t state, int type);
0906
0907 /* Products  *****************************************************************/
0908
0909 void nmod_poly_product_roots_nmod_vec(nmod_poly_t poly, nn_srcptr xs, slong n);
0910
0911 void _nmod_poly_product_roots_nmod_vec(nn_ptr poly, nn_srcptr xs, slong n, nmod_t mod);
0912
0913 void _nmod_poly_split_rabin(nmod_poly_t a, nmod_poly_t b, const nmod_poly_t f, nmod_poly_t t, nmod_poly_t t2, flint_rand_t randstate);
0914
0915 int nmod_poly_find_distinct_nonzero_roots(ulong * roots, const nmod_poly_t P);
0916
0917 /* CRT ***********************************************************************/
0918
0919 /* instructions do A = B + I*(C - B) mod M */
0920 typedef struct
0921 {
0922     slong a_idx; /* index of A */
0923     slong b_idx; /* index of B */
0924     slong c_idx; /* index of C */
0925     nmod_poly_t idem;     /* I */
0926     nmod_poly_t modulus;  /* M */
0927 } _nmod_poly_multi_crt_prog_instr;
0928
0929 typedef struct
0930 {
0931     _nmod_poly_multi_crt_prog_instr * prog; /* straight line program */
0932     slong length; /* length of prog */
0933     slong alloc;  /* alloc of prog */
0934     slong localsize; /* length of outputs required in nmod_poly_multi_crt_run */
0935     slong temp1loc; /* index of temporary used in run */
0936     slong temp2loc; /* index of another temporary used in run */
0937     int good;   /* the moduli are good for CRT, essentially relatively prime */
0938 } nmod_poly_multi_crt_struct;
0939
0940 typedef nmod_poly_multi_crt_struct nmod_poly_multi_crt_t[1];
0941
0942 void nmod_poly_multi_crt_init(nmod_poly_multi_crt_t CRT);
0943 void nmod_poly_multi_crt_clear(nmod_poly_multi_crt_t CRT);
0944
0945 int nmod_poly_multi_crt_precompute(nmod_poly_multi_crt_t CRT, const nmod_poly_struct * moduli, slong len);
0946 int nmod_poly_multi_crt_precompute_p(nmod_poly_multi_crt_t CRT, const nmod_poly_struct * const * moduli, slong len);
0947
0948 void nmod_poly_multi_crt_precomp(nmod_poly_t output, const nmod_poly_multi_crt_t CRT, const nmod_poly_struct * values);
0949 void nmod_poly_multi_crt_precomp_p(nmod_poly_t output, const nmod_poly_multi_crt_t CRT, const nmod_poly_struct * const * values);
0950
0951 int nmod_poly_multi_crt(nmod_poly_t output, const nmod_poly_struct * moduli, const nmod_poly_struct * values, slong len);
0952
0953 NMOD_POLY_INLINE
0954 slong _nmod_poly_multi_crt_local_size(const nmod_poly_multi_crt_t CRT)
0955 {
0956     return CRT->localsize;
0957 }
0958
0959 void _nmod_poly_multi_crt_run(nmod_poly_struct * outputs, const nmod_poly_multi_crt_t CRT, const nmod_poly_struct * inputs);
0960 void _nmod_poly_multi_crt_run_p(nmod_poly_struct * outputs, const nmod_poly_multi_crt_t CRT, const nmod_poly_struct * const * inputs);
0961
0962 /* Inflation and deflation ***************************************************/
0963
0964 slong nmod_poly_deflation(const nmod_poly_t input);
0965
0966 void nmod_poly_deflate(nmod_poly_t result, const nmod_poly_t input, slong deflation);
0967 void nmod_poly_inflate(nmod_poly_t result, const nmod_poly_t input, slong inflation);
0968
0969 /* Characteristic polynomial and minimal polynomial */
0970 /* FIXME: These should be moved to nmod_mat.h. */
0971
0972 void _nmod_mat_charpoly_berkowitz(nn_ptr p, const nmod_mat_t M, nmod_t mod);
0973 void nmod_mat_charpoly_berkowitz(nmod_poly_t p, const nmod_mat_t M);
0974 int nmod_mat_charpoly_danilevsky(nmod_poly_t p, const nmod_mat_t M);
0975 void nmod_mat_charpoly(nmod_poly_t p, const nmod_mat_t M);
0976
0977 void nmod_mat_minpoly_with_gens(nmod_poly_t p, const nmod_mat_t X, ulong * P);
0978
0979 void nmod_mat_minpoly(nmod_poly_t p, const nmod_mat_t M);
0980
0981 /* Berlekamp-Massey Algorithm - see nmod_poly/berlekamp_massey.c for more info ************/
0982
0983 typedef struct
0984 {
0985     slong npoints;
0986     nmod_poly_t R0, R1;
0987     nmod_poly_t V0, V1;
0988     nmod_poly_t qt, rt;
0989     nmod_poly_t points;
0990 } nmod_berlekamp_massey_struct;
0991
0992 typedef nmod_berlekamp_massey_struct nmod_berlekamp_massey_t[1];
0993
0994 void nmod_berlekamp_massey_init(nmod_berlekamp_massey_t B, ulong p);
0995 void nmod_berlekamp_massey_clear(nmod_berlekamp_massey_t B);
0996
0997 void nmod_berlekamp_massey_start_over(nmod_berlekamp_massey_t B);
0998
0999 void nmod_berlekamp_massey_set_prime(nmod_berlekamp_massey_t B, ulong p);
1000
1001 void nmod_berlekamp_massey_print(const nmod_berlekamp_massey_t B);
1002
1003 void nmod_berlekamp_massey_add_point(nmod_berlekamp_massey_t B, ulong a);
1004 void nmod_berlekamp_massey_add_points(nmod_berlekamp_massey_t B, const ulong * a, slong count);
1005 void nmod_berlekamp_massey_add_zeros(nmod_berlekamp_massey_t B, slong count);
1006
1007 int nmod_berlekamp_massey_reduce(nmod_berlekamp_massey_t B);
1008
1009 NMOD_POLY_INLINE const ulong * nmod_berlekamp_massey_points(const nmod_berlekamp_massey_t B)
1010 {
1011     return B->points->coeffs;
1012 }
1013
1014 NMOD_POLY_INLINE slong nmod_berlekamp_massey_point_count(const nmod_berlekamp_massey_t B)
1015 {
1016     return B->points->length;
1017 }
1018
1019 NMOD_POLY_INLINE const nmod_poly_struct * nmod_berlekamp_massey_V_poly(const nmod_berlekamp_massey_t B)
1020 {
1021     return B->V1;
1022 }
1023
1024 NMOD_POLY_INLINE const nmod_poly_struct * nmod_berlekamp_massey_R_poly(const nmod_berlekamp_massey_t B)
1025 {
1026     return B->R1;
1027 }
1028
1029 #ifdef __cplusplus
1030 }
1031 #endif
1032
1033 #endif