include/flint/fq_poly_templates.h

0001 /*
0002     Copyright (C) 2012 Andres Goens
0003     Copyright (C) 2012 Sebastian Pancratz
0004     Copyright (C) 2013 Mike Hansen
0005
0006     This file is part of FLINT.
0007
0008     FLINT is free software: you can redistribute it and/or modify it under
0009     the terms of the GNU Lesser General Public License (LGPL) as published
0010     by the Free Software Foundation; either version 3 of the License, or
0011     (at your option) any later version.  See <https://www.gnu.org/licenses/>.
0012 */
0013
0014 #ifdef T
0015
0016 #include "templates.h"
0017 #include "nmod_types.h"
0018 #include "fmpz_mod_types.h"
0019
0020 #ifdef __cplusplus
0021 extern "C" {
0022 #endif
0023
0024 /*  Memory management ********************************************************/
0025
0026 void TEMPLATE(T, poly_init)(TEMPLATE(T, poly_t) poly, const TEMPLATE(T, ctx_t) FLINT_UNUSED(ctx));
0027
0028 void TEMPLATE(T, poly_init2)(TEMPLATE(T, poly_t) poly, slong alloc,
0029                         const TEMPLATE(T, ctx_t) ctx);
0030
0031 void TEMPLATE(T, poly_realloc)(TEMPLATE(T, poly_t) poly, slong alloc,
0032                           const TEMPLATE(T, ctx_t) ctx);
0033
0034 void TEMPLATE(T, poly_truncate)(TEMPLATE(T, poly_t) poly, slong len,
0035                           const TEMPLATE(T, ctx_t) ctx);
0036
0037 void TEMPLATE(T, poly_set_trunc)(TEMPLATE(T, poly_t) poly1, TEMPLATE(T, poly_t) poly2, slong len,
0038                           const TEMPLATE(T, ctx_t) ctx);
0039
0040 void TEMPLATE(T, poly_fit_length)(TEMPLATE(T, poly_t) poly, slong len,
0041                              const TEMPLATE(T, ctx_t) ctx);
0042
0043 void TEMPLATE(T, poly_clear)(TEMPLATE(T, poly_t) poly,
0044                         const TEMPLATE(T, ctx_t) ctx);
0045
0046 void _TEMPLATE(T, poly_normalise)(TEMPLATE(T, poly_t) poly,
0047                              const TEMPLATE(T, ctx_t) ctx);
0048
0049 void _TEMPLATE(T, poly_normalise2)(const TEMPLATE(T, struct) *poly, slong *length,
0050                               const TEMPLATE(T, ctx_t) ctx);
0051
0052 void _TEMPLATE(T, poly_set_length)(TEMPLATE(T, poly_t) poly, slong len,
0053                               const TEMPLATE(T, ctx_t) ctx);
0054
0055 /*  Polynomial parameters  ***************************************************/
0056
0057 FQ_POLY_TEMPLATES_INLINE slong
0058 TEMPLATE(T, poly_length)(const TEMPLATE(T, poly_t) poly,
0059                          const TEMPLATE(T, ctx_t) FLINT_UNUSED(ctx))
0060 {
0061     return poly->length;
0062 }
0063
0064 FQ_POLY_TEMPLATES_INLINE slong
0065 TEMPLATE(T, poly_degree)(const TEMPLATE(T, poly_t) poly,
0066                          const TEMPLATE(T, ctx_t) FLINT_UNUSED(ctx))
0067 {
0068     return poly->length - 1;
0069 }
0070
0071 FQ_POLY_TEMPLATES_INLINE TEMPLATE(T, struct) *
0072 TEMPLATE(T, poly_lead)(const TEMPLATE(T, poly_t) poly,
0073                        const TEMPLATE(T, ctx_t) FLINT_UNUSED(ctx))
0074 {
0075     return poly->length > 0 ? poly->coeffs + (poly->length - 1) : NULL;
0076 }
0077
0078 /*  Randomisation  ***********************************************************/
0079
0080 void TEMPLATE(T, poly_randtest)(TEMPLATE(T, poly_t) f, flint_rand_t state,
0081                            slong len, const TEMPLATE(T, ctx_t) ctx);
0082
0083 void TEMPLATE(T, poly_randtest_not_zero)(TEMPLATE(T, poly_t) f, flint_rand_t state,
0084                                     slong len, const TEMPLATE(T, ctx_t) ctx);
0085
0086 void TEMPLATE(T, poly_randtest_monic) (TEMPLATE(T, poly_t) f, flint_rand_t state,
0087                                   slong len, const TEMPLATE(T, ctx_t) ctx);
0088
0089 void TEMPLATE(T, poly_randtest_irreducible) (TEMPLATE(T, poly_t) f,
0090                                         flint_rand_t state, slong len,
0091                                         const TEMPLATE(T, ctx_t) ctx);
0092
0093
0094 /*  Assignment and basic manipulation  ***************************************/
0095
0096 void _TEMPLATE(T, poly_set)(TEMPLATE(T, struct) *rop, const TEMPLATE(T, struct) *op,
0097                        slong len, const TEMPLATE(T, ctx_t) ctx);
0098
0099 void TEMPLATE(T, poly_set)(TEMPLATE(T, poly_t) rop, const TEMPLATE(T, poly_t) op,
0100                       const TEMPLATE(T, ctx_t) ctx);
0101
0102 void TEMPLATE3(T, poly_set, T)(TEMPLATE(T, poly_t) poly, const TEMPLATE(T, t) c,
0103                           const TEMPLATE(T, ctx_t) ctx);
0104
0105 void TEMPLATE(T, poly_set_fmpz_mod_poly)(TEMPLATE(T, poly_t) rop,
0106                                                    const fmpz_mod_poly_t op,
0107                                                    const TEMPLATE(T, ctx_t) ctx);
0108
0109 void TEMPLATE(T, poly_set_nmod_poly)(TEMPLATE(T, poly_t) rop,
0110                                                const nmod_poly_t op,
0111                                                const TEMPLATE(T, ctx_t) ctx);
0112
0113 void TEMPLATE(T, poly_swap)(TEMPLATE(T, poly_t) op1, TEMPLATE(T, poly_t) op2,
0114                        const TEMPLATE(T, ctx_t) FLINT_UNUSED(ctx));
0115
0116 void _TEMPLATE(T, poly_zero)(TEMPLATE(T, struct) *rop, slong len, const TEMPLATE(T, ctx_t) ctx);
0117 void TEMPLATE(T, poly_zero)(TEMPLATE(T, poly_t) poly, const TEMPLATE(T, ctx_t) ctx);
0118 void TEMPLATE(T, poly_one)(TEMPLATE(T, poly_t) poly, const TEMPLATE(T, ctx_t) ctx);
0119
0120 void TEMPLATE(T, poly_gen)(TEMPLATE(T, poly_t) f, const TEMPLATE(T, ctx_t) ctx);
0121
0122 void _TEMPLATE(T, poly_make_monic)(TEMPLATE(T, struct) *rop,
0123                               const TEMPLATE(T, struct) *op, slong length,
0124                               const TEMPLATE(T, ctx_t) ctx);
0125
0126 void TEMPLATE(T, poly_make_monic)(TEMPLATE(T, poly_t) rop,
0127                                   const TEMPLATE(T, poly_t) op,
0128                                   const TEMPLATE(T, ctx_t) ctx);
0129
0130 void _TEMPLATE(T, poly_reverse)(TEMPLATE(T, struct) * res,
0131                            const TEMPLATE(T, struct) * poly, slong len, slong n,
0132                            const TEMPLATE(T, ctx_t) ctx);
0133
0134 void TEMPLATE(T, poly_reverse)(TEMPLATE(T, poly_t) res,
0135                           const TEMPLATE(T, poly_t) poly, slong n,
0136                           const TEMPLATE(T, ctx_t) ctx);
0137
0138 ulong TEMPLATE(T, poly_deflation)(const TEMPLATE(T, poly_t) input,
0139                             const TEMPLATE(T, ctx_t) ctx);
0140
0141 void TEMPLATE(T, poly_deflate)(TEMPLATE(T, poly_t) result,
0142                           const TEMPLATE(T, poly_t) input, ulong deflation,
0143                           const TEMPLATE(T, ctx_t) ctx);
0144
0145 void TEMPLATE(T, poly_inflate)(TEMPLATE(T, poly_t) result,
0146                           const TEMPLATE(T, poly_t) input, ulong inflation,
0147                           const TEMPLATE(T, ctx_t) ctx);
0148
0149 /*  Getting and setting coefficients  ****************************************/
0150
0151 void TEMPLATE(T, poly_get_coeff)(TEMPLATE(T, t) x, const TEMPLATE(T, poly_t) poly,
0152                             slong n, const TEMPLATE(T, ctx_t) ctx);
0153
0154 void TEMPLATE(T, poly_set_coeff)(TEMPLATE(T, poly_t) poly, slong n,
0155                                  const TEMPLATE(T, t) x,
0156                                  const TEMPLATE(T, ctx_t) ctx);
0157
0158 void TEMPLATE(T, poly_set_coeff_fmpz)(TEMPLATE(T, poly_t) poly, slong n,
0159                                  const fmpz_t x, const TEMPLATE(T, ctx_t) ctx);
0160
0161 int TEMPLATE(T, poly_is_gen)(const TEMPLATE(T, poly_t) poly,
0162                                 const TEMPLATE(T, ctx_t) ctx);
0163
0164 /*  Comparison  **************************************************************/
0165
0166 int TEMPLATE(T, poly_equal)(const TEMPLATE(T, poly_t) poly1,
0167                             const TEMPLATE(T, poly_t) poly2,
0168                             const TEMPLATE(T, ctx_t) ctx);
0169
0170 int TEMPLATE(T, poly_equal_trunc)(const TEMPLATE(T, poly_t) poly1,
0171                             const TEMPLATE(T, poly_t) poly2,
0172                             slong n, const TEMPLATE(T, ctx_t) ctx);
0173
0174 FQ_POLY_TEMPLATES_INLINE int
0175 TEMPLATE(T, poly_is_zero)(const TEMPLATE(T, poly_t) poly,
0176                           const TEMPLATE(T, ctx_t) FLINT_UNUSED(ctx))
0177 {
0178     return (poly->length == 0);
0179 }
0180
0181 int TEMPLATE(T, poly_is_one)(const TEMPLATE(T, poly_t) op, const TEMPLATE(T, ctx_t) ctx);
0182 int TEMPLATE(T, poly_is_unit)(const TEMPLATE(T, poly_t) op, const TEMPLATE(T, ctx_t) ctx);
0183 int TEMPLATE3(T, poly_equal, T)(const TEMPLATE(T, poly_t) poly, const TEMPLATE(T, t) c, const TEMPLATE(T, ctx_t) ctx);
0184
0185 /*  Addition and subtraction  ************************************************/
0186
0187 void _TEMPLATE(T, poly_add)(TEMPLATE(T, struct) *res,
0188                        const TEMPLATE(T, struct) *poly1, slong len1,
0189                        const TEMPLATE(T, struct) *poly2, slong len2,
0190                        const TEMPLATE(T, ctx_t) ctx);
0191
0192 void TEMPLATE(T, poly_add)(TEMPLATE(T, poly_t) rop, const TEMPLATE(T, poly_t) op1,
0193                       const TEMPLATE(T, poly_t) op2,
0194                       const TEMPLATE(T, ctx_t) ctx);
0195
0196 void TEMPLATE(T, poly_add_si)(TEMPLATE(T, poly_t) rop,
0197                                     const TEMPLATE(T, poly_t) op1, slong c,
0198                                                  const TEMPLATE(T, ctx_t) ctx);
0199
0200 void TEMPLATE(T, poly_add_series)(TEMPLATE(T, poly_t) rop, const TEMPLATE(T, poly_t) op1,
0201                       const TEMPLATE(T, poly_t) op2,
0202                       slong n, const TEMPLATE(T, ctx_t) ctx);
0203
0204 void _TEMPLATE(T, poly_sub)(TEMPLATE(T, struct) *res,
0205                        const TEMPLATE(T, struct) *poly1, slong len1,
0206                        const TEMPLATE(T, struct) *poly2, slong len2,
0207                        const TEMPLATE(T, ctx_t) ctx);
0208
0209 void TEMPLATE(T, poly_sub)(TEMPLATE(T, poly_t) rop,
0210                       const TEMPLATE(T, poly_t) op1,
0211                       const TEMPLATE(T, poly_t) op2,
0212                       const TEMPLATE(T, ctx_t) ctx);
0213
0214 void TEMPLATE(T, poly_sub_series)(TEMPLATE(T, poly_t) rop,
0215                       const TEMPLATE(T, poly_t) op1,
0216                       const TEMPLATE(T, poly_t) op2,
0217                       slong n, const TEMPLATE(T, ctx_t) ctx);
0218
0219 void _TEMPLATE(T, poly_neg)(TEMPLATE(T, struct) *rop,
0220                        const TEMPLATE(T, struct) *op, slong len,
0221                        const TEMPLATE(T, ctx_t) ctx);
0222
0223 void TEMPLATE(T, poly_neg)(TEMPLATE(T, poly_t) rop, const TEMPLATE(T, poly_t) op,
0224                       const TEMPLATE(T, ctx_t) ctx);
0225
0226 /*  Scalar multiplication and division  **************************************/
0227
0228 void _TEMPLATE3(T, poly_scalar_mul, T)(TEMPLATE(T, struct) *rop,
0229                                   const TEMPLATE(T, struct) *op, slong len,
0230                                   const TEMPLATE(T, t) x,
0231                                   const TEMPLATE(T, ctx_t) ctx);
0232
0233 void TEMPLATE3(T, poly_scalar_mul, T)(TEMPLATE(T, poly_t) rop,
0234                                  const TEMPLATE(T, poly_t) op,
0235                                  const TEMPLATE(T, t) x,
0236                                  const TEMPLATE(T, ctx_t) ctx);
0237
0238 void _TEMPLATE3(T, poly_scalar_div, T)(TEMPLATE(T, struct) *rop,
0239                                   const TEMPLATE(T, struct) *op, slong len,
0240                                   const TEMPLATE(T, t) x,
0241                                   const TEMPLATE(T, ctx_t) ctx);
0242
0243 void TEMPLATE3(T, poly_scalar_div, T)(TEMPLATE(T, poly_t) rop,
0244                                  const TEMPLATE(T, poly_t) op,
0245                                  const TEMPLATE(T, t) x,
0246                                  const TEMPLATE(T, ctx_t) ctx);
0247
0248 void  _TEMPLATE3(T, poly_scalar_addmul, T)(TEMPLATE(T, struct) *rop,
0249                                      const TEMPLATE(T, struct) *op, slong len,
0250                                      const TEMPLATE(T, t) x,
0251                                      const TEMPLATE(T, ctx_t) ctx);
0252
0253 void TEMPLATE3(T, poly_scalar_addmul, T)(TEMPLATE(T, poly_t) rop,
0254                                     const TEMPLATE(T, poly_t) op,
0255                                     const TEMPLATE(T, t) x,
0256                                     const TEMPLATE(T, ctx_t) ctx);
0257
0258 void _TEMPLATE3(T, poly_scalar_submul, T)(TEMPLATE(T, struct) *rop,
0259                                      const TEMPLATE(T, struct) *op, slong len,
0260                                      const TEMPLATE(T, t) x,
0261                                      const TEMPLATE(T, ctx_t) ctx);
0262
0263 void TEMPLATE3(T, poly_scalar_submul, T)(TEMPLATE(T, poly_t) rop,
0264                                     const TEMPLATE(T, poly_t) op,
0265                                     const TEMPLATE(T, t) x,
0266                                     const TEMPLATE(T, ctx_t) ctx);
0267
0268 /*  Multiplication  **********************************************************/
0269
0270 void _TEMPLATE(T, poly_mul_classical)(TEMPLATE(T, struct) *rop,
0271                                  const TEMPLATE(T, struct) *op1, slong len1,
0272                                  const TEMPLATE(T, struct) *op2, slong len2,
0273                                  const TEMPLATE(T, ctx_t) ctx);
0274
0275 void TEMPLATE(T, poly_mul_classical)(TEMPLATE(T, poly_t) rop,
0276                                 const TEMPLATE(T, poly_t) op1,
0277                                 const TEMPLATE(T, poly_t) op2,
0278                                 const TEMPLATE(T, ctx_t) ctx);
0279
0280 void _TEMPLATE(T, poly_mul_reorder)(TEMPLATE(T, struct) *rop,
0281                                const TEMPLATE(T, struct) *op1, slong len1,
0282                                const TEMPLATE(T, struct) *op2, slong len2,
0283                                const TEMPLATE(T, ctx_t) ctx);
0284
0285 void TEMPLATE(T, poly_mul_reorder)(TEMPLATE(T, poly_t) rop,
0286                               const TEMPLATE(T, poly_t) op1,
0287                               const TEMPLATE(T, poly_t) op2,
0288                               const TEMPLATE(T, ctx_t) ctx);
0289
0290 void _TEMPLATE(T, poly_mul_univariate)(TEMPLATE(T, struct) *rop,
0291                           const TEMPLATE(T, struct) *op1, slong len1,
0292                           const TEMPLATE(T, struct) *op2, slong len2,
0293                           const TEMPLATE(T, ctx_t) ctx);
0294
0295 void TEMPLATE(T, poly_mul_univariate)(TEMPLATE(T, poly_t) rop,
0296                          const TEMPLATE(T, poly_t) op1,
0297                          const TEMPLATE(T, poly_t) op2,
0298                          const TEMPLATE(T, ctx_t) ctx);
0299
0300 void _TEMPLATE(T, poly_mul_KS)(TEMPLATE(T, struct) *rop,
0301                           const TEMPLATE(T, struct) *op1, slong len1,
0302                           const TEMPLATE(T, struct) *op2, slong len2,
0303                           const TEMPLATE(T, ctx_t) ctx);
0304
0305 void TEMPLATE(T, poly_mul_KS)(TEMPLATE(T, poly_t) rop,
0306                          const TEMPLATE(T, poly_t) op1,
0307                          const TEMPLATE(T, poly_t) op2,
0308                          const TEMPLATE(T, ctx_t) ctx);
0309
0310 void _TEMPLATE(T, poly_mul)(TEMPLATE(T, struct) *rop,
0311                        const TEMPLATE(T, struct) *op1, slong len1,
0312                        const TEMPLATE(T, struct) *op2, slong len2,
0313                        const TEMPLATE(T, ctx_t) ctx);
0314
0315 void TEMPLATE(T, poly_mul)(TEMPLATE(T, poly_t) rop,
0316                       const TEMPLATE(T, poly_t) op1,
0317                       const TEMPLATE(T, poly_t) op2,
0318                       const TEMPLATE(T, ctx_t) ctx);
0319
0320 void _TEMPLATE(T, poly_mullow_classical)(TEMPLATE(T, struct) *rop,
0321                                     const TEMPLATE(T, struct) *op1, slong len1,
0322                                     const TEMPLATE(T, struct) *op2, slong len2,
0323                                     slong n,
0324                                     const TEMPLATE(T, ctx_t) ctx);
0325
0326 void TEMPLATE(T, poly_mullow_classical)(TEMPLATE(T, poly_t) rop,
0327                                    const TEMPLATE(T, poly_t) op1,
0328                                    const TEMPLATE(T, poly_t) op2,
0329                                    slong n, const
0330                                    TEMPLATE(T, ctx_t) ctx);
0331
0332 void _TEMPLATE(T, poly_mullow_KS)(TEMPLATE(T, struct) *rop,
0333                              const TEMPLATE(T, struct) *op1, slong len1,
0334                              const TEMPLATE(T, struct) *op2, slong len2,
0335                              slong n,
0336                              const TEMPLATE(T, ctx_t) ctx);
0337
0338 void TEMPLATE(T, poly_mullow_KS)(TEMPLATE(T, poly_t) rop,
0339                             const TEMPLATE(T, poly_t) op1,
0340                             const TEMPLATE(T, poly_t) op2,
0341                             slong n,
0342                             const TEMPLATE(T, ctx_t) ctx);
0343
0344 void _TEMPLATE(T, poly_mullow_univariate)(TEMPLATE(T, struct) *rop,
0345                              const TEMPLATE(T, struct) *op1, slong len1,
0346                              const TEMPLATE(T, struct) *op2, slong len2,
0347                              slong n,
0348                              const TEMPLATE(T, ctx_t) ctx);
0349
0350 void TEMPLATE(T, poly_mullow_univariate)(TEMPLATE(T, poly_t) rop,
0351                             const TEMPLATE(T, poly_t) op1,
0352                             const TEMPLATE(T, poly_t) op2,
0353                             slong n,
0354                             const TEMPLATE(T, ctx_t) ctx);
0355
0356 void _TEMPLATE(T, poly_mullow)(TEMPLATE(T, struct) *rop,
0357                           const TEMPLATE(T, struct) *op1, slong len1,
0358                           const TEMPLATE(T, struct) *op2, slong len2,
0359                           slong n,
0360                           const TEMPLATE(T, ctx_t) ctx);
0361
0362 void TEMPLATE(T, poly_mullow)(TEMPLATE(T, poly_t) rop,
0363                          const TEMPLATE(T, poly_t) op1,
0364                          const TEMPLATE(T, poly_t) op2,
0365                          slong n,
0366                          const TEMPLATE(T, ctx_t) ctx);
0367
0368 void _TEMPLATE(T, poly_mulhigh_classical)(
0369     TEMPLATE(T, struct)* rop,
0370     const TEMPLATE(T, struct)* op1, slong len1,
0371     const TEMPLATE(T, struct)* op2, slong len2,
0372     slong start,
0373     const TEMPLATE(T, ctx_t) ctx);
0374
0375 void TEMPLATE(T, poly_mulhigh_classical)(TEMPLATE(T, poly_t) rop,
0376                                     const TEMPLATE(T, poly_t) op1,
0377                                     const TEMPLATE(T, poly_t) op2,
0378                                     slong start,
0379                                     const TEMPLATE(T, ctx_t) ctx);
0380
0381 void _TEMPLATE(T, poly_mulhigh)(TEMPLATE(T, struct)* res,
0382                            const TEMPLATE(T, struct)* poly1, slong len1,
0383                            const TEMPLATE(T, struct)* poly2, slong len2,
0384                            slong n, TEMPLATE(T, ctx_t) ctx);
0385
0386 void TEMPLATE(T, poly_mulhigh)(TEMPLATE(T, poly_t) rop,
0387                           const TEMPLATE(T, poly_t) op1,
0388                           const TEMPLATE(T, poly_t) op2, slong start,
0389                           const TEMPLATE(T, ctx_t) ctx);
0390
0391 void _TEMPLATE(T, poly_mulmod)(TEMPLATE(T, struct) * res,
0392                           const TEMPLATE(T, struct) * poly1, slong len1,
0393                           const TEMPLATE(T, struct) * poly2, slong len2,
0394                           const TEMPLATE(T, struct) * f, slong lenf,
0395                           const TEMPLATE(T, ctx_t) ctx);
0396
0397 void TEMPLATE(T, poly_mulmod)(TEMPLATE(T, poly_t) res,
0398                          const TEMPLATE(T, poly_t) poly1,
0399                          const TEMPLATE(T, poly_t) poly2,
0400                          const TEMPLATE(T, poly_t) f,
0401                          const TEMPLATE(T, ctx_t) ctx);
0402
0403 void _TEMPLATE(T, poly_mulmod_preinv)(TEMPLATE(T, struct) *res,
0404                                  const TEMPLATE(T, struct) *poly1, slong len1,
0405                                  const TEMPLATE(T, struct)  *poly2, slong len2,
0406                                  const TEMPLATE(T, struct) *f, slong lenf,
0407                                  const TEMPLATE(T, struct) *finv, slong lenfinv,
0408                                  const TEMPLATE(T, ctx_t) ctx);
0409 void TEMPLATE(T, poly_mulmod_preinv)(TEMPLATE(T, poly_t) res,
0410                                 const TEMPLATE(T, poly_t) poly1,
0411                                 const TEMPLATE(T, poly_t) poly2,
0412                                 const TEMPLATE(T, poly_t) f,
0413                                 const TEMPLATE(T, poly_t) finv,
0414                                 const TEMPLATE(T, ctx_t) ctx);
0415
0416 /* Squaring ******************************************************************/
0417
0418 void _TEMPLATE(T, poly_sqr_classical)(TEMPLATE(T, struct) *rop,
0419                                  const TEMPLATE(T, struct) *op, slong len,
0420                                  const TEMPLATE(T, ctx_t) ctx);
0421
0422 void TEMPLATE(T, poly_sqr_classical)(TEMPLATE(T, poly_t) rop,
0423                                 const TEMPLATE(T, poly_t) op,
0424                                 const TEMPLATE(T, ctx_t) ctx);
0425
0426 void _TEMPLATE(T, poly_sqr_reorder)(TEMPLATE(T, struct) *rop,
0427                                const TEMPLATE(T, struct) *op, slong len,
0428                                const TEMPLATE(T, ctx_t) ctx);
0429
0430 void TEMPLATE(T, poly_sqr_reorder)(TEMPLATE(T, poly_t) rop,
0431                               const TEMPLATE(T, poly_t) op,
0432                               const TEMPLATE(T, ctx_t) ctx);
0433
0434 void _TEMPLATE(T, poly_sqr_KS)(TEMPLATE(T, struct) *rop,
0435                           const TEMPLATE(T, struct) *op, slong len,
0436                           const TEMPLATE(T, ctx_t) ctx);
0437
0438 void TEMPLATE(T, poly_sqr_KS)(TEMPLATE(T, poly_t) rop,
0439                          const TEMPLATE(T, poly_t) op,
0440                          const TEMPLATE(T, ctx_t) ctx);
0441
0442 void _TEMPLATE(T, poly_sqr)(TEMPLATE(T, struct) *rop,
0443                        const TEMPLATE(T, struct) *op, slong len,
0444                        const TEMPLATE(T, ctx_t) ctx);
0445
0446 void TEMPLATE(T, poly_sqr)(TEMPLATE(T, poly_t) rop, const TEMPLATE(T, poly_t) op,
0447                       const TEMPLATE(T, ctx_t) ctx);
0448
0449 /*  Powering  ****************************************************************/
0450
0451 void _TEMPLATE(T, poly_pow)(TEMPLATE(T, struct) *rop,
0452                        const TEMPLATE(T, struct) *op, slong len,
0453                        ulong e,
0454                        const TEMPLATE(T, ctx_t) ctx);
0455
0456 void TEMPLATE(T, poly_pow)(TEMPLATE(T, poly_t) rop,
0457                       const TEMPLATE(T, poly_t) op,
0458                       ulong e,
0459                       const TEMPLATE(T, ctx_t) ctx);
0460
0461 void _TEMPLATE(T, poly_pow_trunc_binexp) (TEMPLATE(T, struct) * res,
0462                                    const TEMPLATE(T, struct) * poly,  ulong e,
0463                         slong trunc, const TEMPLATE(T, ctx_t) ctx);
0464
0465 void TEMPLATE(T, poly_pow_trunc_binexp) (TEMPLATE(T, poly_t) res,
0466                                      const TEMPLATE(T, poly_t) poly, ulong e,
0467                                     slong trunc, const TEMPLATE(T, ctx_t) ctx);
0468
0469 void _TEMPLATE(T, poly_pow_trunc) (TEMPLATE(T, struct) * res,
0470                                    const TEMPLATE(T, struct) * poly,  ulong e,
0471                                     slong trunc, const TEMPLATE(T, ctx_t) ctx);
0472
0473 void TEMPLATE(T, poly_pow_trunc) (TEMPLATE(T, poly_t) res,
0474                                      const TEMPLATE(T, poly_t) poly, ulong e,                                                 slong trunc, const TEMPLATE(T, ctx_t) ctx);
0475
0476 void _TEMPLATE(T, poly_powmod_fmpz_binexp)(TEMPLATE(T, struct) * res,
0477                                       const TEMPLATE(T, struct) * poly,
0478                                       const fmpz_t e,
0479                                       const TEMPLATE(T, struct) * f, slong lenf,
0480                                       const TEMPLATE(T, ctx_t) ctx);
0481
0482 void TEMPLATE(T, poly_powmod_fmpz_binexp)(TEMPLATE(T, poly_t) res,
0483                                      const TEMPLATE(T, poly_t) poly,
0484                                      const fmpz_t e,
0485                                      const TEMPLATE(T, poly_t) f,
0486                                      const TEMPLATE(T, ctx_t) ctx);
0487
0488 void _TEMPLATE(T, poly_powmod_fmpz_binexp_preinv)(
0489     TEMPLATE(T, struct) * res,
0490     const TEMPLATE(T, struct) * poly,
0491     const fmpz_t e,
0492     const TEMPLATE(T, struct) * f, slong lenf,
0493     const TEMPLATE(T, struct) *finv, slong lenfinv,
0494     const TEMPLATE(T, ctx_t) ctx);
0495
0496 void TEMPLATE(T, poly_powmod_fmpz_binexp_preinv)(
0497     TEMPLATE(T, poly_t) res,
0498     const TEMPLATE(T, poly_t) poly, const fmpz_t e,
0499     const TEMPLATE(T, poly_t) f, const TEMPLATE(T, poly_t) finv,
0500     const TEMPLATE(T, ctx_t) ctx);
0501
0502 void _TEMPLATE(T, poly_powmod_ui_binexp)(
0503     TEMPLATE(T, struct) * res,
0504     const TEMPLATE(T, struct) * poly,
0505     ulong e,
0506     const TEMPLATE(T, struct) * f, slong lenf,
0507     const TEMPLATE(T, ctx_t) ctx);
0508
0509 void TEMPLATE(T, poly_powmod_ui_binexp)(
0510     TEMPLATE(T, poly_t) res,
0511     const TEMPLATE(T, poly_t) poly, ulong e,
0512     const TEMPLATE(T, poly_t) f,
0513     const TEMPLATE(T, ctx_t) ctx);
0514
0515 void _TEMPLATE(T, poly_powmod_ui_binexp_preinv)(
0516     TEMPLATE(T, struct) * res,
0517     const TEMPLATE(T, struct) * poly,
0518     ulong e,
0519     const TEMPLATE(T, struct) * f, slong lenf,
0520     const TEMPLATE(T, struct) * finv, slong lenfinv,
0521     const TEMPLATE(T, ctx_t) ctx);
0522
0523 void TEMPLATE(T, poly_powmod_ui_binexp_preinv)(
0524     TEMPLATE(T, poly_t) res,
0525     const TEMPLATE(T, poly_t) poly,
0526     ulong e,
0527     const TEMPLATE(T, poly_t) f,
0528     const TEMPLATE(T, poly_t) finv,
0529     const TEMPLATE(T, ctx_t) ctx);
0530
0531 void _TEMPLATE(T, poly_powmod_fmpz_sliding_preinv)(
0532     TEMPLATE(T, struct) * res,
0533     const TEMPLATE(T, struct) * poly,
0534     const fmpz_t e, ulong k,
0535     const TEMPLATE(T, struct) * f, slong lenf,
0536     const TEMPLATE(T, struct) * finv, slong lenfinv,
0537     const TEMPLATE(T, ctx_t) ctx);
0538
0539 void TEMPLATE(T, poly_powmod_fmpz_sliding_preinv)(
0540     TEMPLATE(T, poly_t) res,
0541     const TEMPLATE(T, poly_t) poly,
0542     const fmpz_t e, ulong k,
0543     const TEMPLATE(T, poly_t) f,
0544     const TEMPLATE(T, poly_t) finv,
0545     const TEMPLATE(T, ctx_t) ctx);
0546
0547
0548 void _TEMPLATE(T, poly_powmod_x_fmpz_preinv)(
0549     TEMPLATE(T, struct) * res, const fmpz_t e,
0550     const TEMPLATE(T, struct) * f, slong lenf,
0551     const TEMPLATE(T, struct)* finv, slong lenfinv,
0552     const TEMPLATE(T, ctx_t) ctx);
0553
0554 void TEMPLATE(T, poly_powmod_x_fmpz_preinv)(
0555     TEMPLATE(T, poly_t) res, const fmpz_t e,
0556     const TEMPLATE(T, poly_t) f,
0557     const TEMPLATE(T, poly_t) finv,
0558     const TEMPLATE(T, ctx_t) ctx);
0559
0560 /*  Shifting  ****************************************************************/
0561
0562 void _TEMPLATE(T, poly_shift_left)(TEMPLATE(T, struct) *rop,
0563                               const TEMPLATE(T, struct) *op, slong len,
0564                               slong n,
0565                               const TEMPLATE(T, ctx_t) ctx);
0566
0567 void TEMPLATE(T, poly_shift_left)(TEMPLATE(T, poly_t) rop,
0568                              const TEMPLATE(T, poly_t) op,
0569                              slong n,
0570                              const TEMPLATE(T, ctx_t) ctx);
0571
0572 void _TEMPLATE(T, poly_shift_right)(TEMPLATE(T, struct) *rop,
0573                                const TEMPLATE(T, struct) *op, slong len,
0574                                slong n,
0575                                const TEMPLATE(T, ctx_t) ctx);
0576
0577 void TEMPLATE(T, poly_shift_right)(TEMPLATE(T, poly_t) rop,
0578                               const TEMPLATE(T, poly_t) op,
0579                               slong n,
0580                               const TEMPLATE(T, ctx_t) ctx);
0581
0582 /*  Norms  *******************************************************************/
0583
0584 slong _TEMPLATE(T, poly_hamming_weight)(const TEMPLATE(T, struct) *op, slong len,
0585                                   const TEMPLATE(T, ctx_t) ctx);
0586
0587 slong TEMPLATE(T, poly_hamming_weight)(const TEMPLATE(T, poly_t) op,
0588                                  const TEMPLATE(T, ctx_t) ctx);
0589
0590 /*  Greatest common divisor  *************************************************/
0591
0592 void TEMPLATE(T, poly_gcd_euclidean)(TEMPLATE(T, poly_t) rop,
0593                                 const TEMPLATE(T, poly_t) op1,
0594                                 const TEMPLATE(T, poly_t) op2,
0595                                 const TEMPLATE(T, ctx_t) ctx);
0596
0597 slong _TEMPLATE(T, poly_gcd_euclidean)(TEMPLATE(T, struct)* G,
0598                                  const TEMPLATE(T, struct)* A, slong lenA,
0599                                  const TEMPLATE(T, struct)* B, slong lenB,
0600                                  const TEMPLATE(T, t) invB,
0601                                  const TEMPLATE(T, ctx_t) ctx);
0602
0603 slong _TEMPLATE(T, poly_gcd)(TEMPLATE(T, struct)* G,
0604                        const TEMPLATE(T, struct)* A, slong lenA,
0605                        const TEMPLATE(T, struct)* B, slong lenB,
0606                        const TEMPLATE(T, ctx_t) ctx);
0607
0608 void TEMPLATE(T, poly_gcd)(TEMPLATE(T, poly_t) rop,
0609                       const TEMPLATE(T, poly_t) op1,
0610                       const TEMPLATE(T, poly_t) op2,
0611                       const TEMPLATE(T, ctx_t) ctx);
0612
0613 slong _TEMPLATE(T, poly_gcd_euclidean_f)(TEMPLATE(T, t) f, TEMPLATE(T, struct)* G,
0614                                    const TEMPLATE(T, struct)* A, slong lenA,
0615                                    const TEMPLATE(T, struct)* B, slong lenB,
0616                                    const TEMPLATE(T, ctx_t) ctx);
0617
0618 void TEMPLATE(T, poly_gcd_euclidean_f)(TEMPLATE(T, t) f, TEMPLATE(T, poly_t) G,
0619                                   const TEMPLATE(T, poly_t) A,
0620                                   const TEMPLATE(T, poly_t) B,
0621                                   const TEMPLATE(T, ctx_t) ctx);
0622
0623 slong _TEMPLATE(T, poly_xgcd_euclidean_f)(TEMPLATE(T, t) f, TEMPLATE(T, struct) *G,
0624                                     TEMPLATE(T, struct) *S,
0625                                     TEMPLATE(T, struct) *T,
0626                                     const TEMPLATE(T, struct) *A, slong lenA,
0627                                     const TEMPLATE(T, struct) *B, slong lenB,
0628                                     const TEMPLATE(T, ctx_t) ctx);
0629
0630 void TEMPLATE(T, poly_xgcd_euclidean_f)(TEMPLATE(T, t) f, TEMPLATE(T, poly_t) G,
0631                                    TEMPLATE(T, poly_t) S,
0632                                    TEMPLATE(T, poly_t) T,
0633                                    const TEMPLATE(T, poly_t) A,
0634                                    const TEMPLATE(T, poly_t) B,
0635                                    const TEMPLATE(T, ctx_t) ctx);
0636
0637 slong _TEMPLATE(T, poly_xgcd)(TEMPLATE(T, struct) *G,
0638                                   TEMPLATE(T, struct) *S,
0639                                   TEMPLATE(T, struct) *T,
0640                                   const TEMPLATE(T, struct) *A, slong lenA,
0641                                   const TEMPLATE(T, struct) *B, slong lenB,
0642                                   const TEMPLATE(T, ctx_t) ctx);
0643
0644 void TEMPLATE(T, poly_xgcd)(TEMPLATE(T, poly_t) G,
0645                                  TEMPLATE(T, poly_t) S, TEMPLATE(T, poly_t) T,
0646                                  const TEMPLATE(T, poly_t) A,
0647                                  const TEMPLATE(T, poly_t) B,
0648                                  const TEMPLATE(T, ctx_t) ctx);
0649
0650
0651 /*  Euclidean division  ******************************************************/
0652
0653 ulong TEMPLATE(T, poly_remove)(TEMPLATE(T, poly_t) f,
0654                          const TEMPLATE(T, poly_t) g,
0655                          const TEMPLATE(T, ctx_t) ctx);
0656
0657 void _TEMPLATE(T, poly_div)(TEMPLATE(T, struct) *Q,
0658                                const TEMPLATE(T, struct) *A, slong lenA,
0659                                const TEMPLATE(T, struct) *B, slong lenB,
0660                                const TEMPLATE(T, t) invB,
0661                                const TEMPLATE(T, ctx_t) ctx);
0662
0663 void TEMPLATE(T, poly_div)(TEMPLATE(T, poly_t) Q,
0664                                const TEMPLATE(T, poly_t) A,
0665                                const TEMPLATE(T, poly_t) B,
0666                                const TEMPLATE(T, ctx_t) ctx);
0667
0668 /* flint 2.x compatibility needed by Nemo */
0669 void TEMPLATE(T, poly_div_basecase)(TEMPLATE(T, poly_t) Q,
0670                                const TEMPLATE(T, poly_t) A,
0671                                const TEMPLATE(T, poly_t) B,
0672                                const TEMPLATE(T, ctx_t) ctx);
0673
0674 void _TEMPLATE(T, poly_divrem)(TEMPLATE(T, struct) *Q,
0675                                    TEMPLATE(T, struct) *R,
0676                                    const TEMPLATE(T, struct) *A, slong lenA,
0677                                    const TEMPLATE(T, struct) *B, slong lenB,
0678                                    const TEMPLATE(T, t) invB,
0679                                    const TEMPLATE(T, ctx_t) ctx);
0680
0681 void TEMPLATE(T, poly_divrem)(TEMPLATE(T, poly_t) Q, TEMPLATE(T, poly_t) R,
0682                                   const TEMPLATE(T, poly_t) A,
0683                                   const TEMPLATE(T, poly_t) B,
0684                                   const TEMPLATE(T, ctx_t) ctx);
0685
0686 void _TEMPLATE(T, poly_rem)(TEMPLATE(T, struct) *R,
0687                        const TEMPLATE(T, struct) *A, slong lenA,
0688                        const TEMPLATE(T, struct) *B, slong lenB,
0689                        const TEMPLATE(T, t) invB,
0690                        const TEMPLATE(T, ctx_t) ctx);
0691
0692 void TEMPLATE(T, poly_rem)(TEMPLATE(T, poly_t) R,
0693                       const TEMPLATE(T, poly_t) A, const TEMPLATE(T, poly_t) B,
0694                       const TEMPLATE(T, ctx_t) ctx);
0695
0696 void _TEMPLATE(T, poly_inv_series_newton)(TEMPLATE(T, struct) * Qinv,
0697                                      const TEMPLATE(T, struct) * Q, slong n,
0698                                      const TEMPLATE(T, t) cinv,
0699                                      const TEMPLATE(T, ctx_t) ctx);
0700
0701 void TEMPLATE(T, poly_inv_series_newton)(TEMPLATE(T, poly_t) Qinv,
0702                                     const TEMPLATE(T, poly_t) Q, slong n,
0703                                     const TEMPLATE(T, ctx_t) ctx);
0704
0705 FQ_POLY_TEMPLATES_INLINE void
0706 _TEMPLATE(T, poly_inv_series)(TEMPLATE(T, struct) * Qinv,
0707                                      const TEMPLATE(T, struct) * Q, slong n,
0708                                      const TEMPLATE(T, t) cinv,
0709                                      const TEMPLATE(T, ctx_t) ctx)
0710 {
0711    _TEMPLATE(T, poly_inv_series_newton) (Qinv, Q, n, cinv, ctx);
0712 }
0713
0714 FQ_POLY_TEMPLATES_INLINE void
0715 TEMPLATE(T, poly_inv_series)(TEMPLATE(T, poly_t) Qinv,
0716                                     const TEMPLATE(T, poly_t) Q, slong n,
0717                                     const TEMPLATE(T, ctx_t) ctx)
0718 {
0719    TEMPLATE(T, poly_inv_series_newton) (Qinv, Q, n, ctx);
0720 }
0721
0722 void _TEMPLATE(T, poly_div_series) (TEMPLATE(T, struct) * Q,
0723                           const TEMPLATE(T, struct) * A, slong Alen,
0724                           const TEMPLATE(T, struct) * B, slong Blen,
0725                           slong n, const TEMPLATE(T, ctx_t) ctx);
0726
0727 void TEMPLATE(T, poly_div_series)(TEMPLATE(T, poly_t) Q,
0728                const TEMPLATE(T, poly_t) A, const TEMPLATE(T, poly_t) B,
0729                                         slong n, const TEMPLATE(T, ctx_t) ctx);
0730
0731 void _TEMPLATE(T, poly_div_newton_n_preinv) (
0732     TEMPLATE(T, struct) *Q,
0733     const TEMPLATE(T, struct) *A, slong lenA,
0734     const TEMPLATE(T, struct)* FLINT_UNUSED(B), slong lenB,
0735     const TEMPLATE(T, struct)* Binv, slong lenBinv,
0736     const TEMPLATE(T, ctx_t) ctx);
0737
0738 void TEMPLATE(T, poly_div_newton_n_preinv) (TEMPLATE(T, poly_t) Q,
0739                                        const TEMPLATE(T, poly_t) A,
0740                                        const TEMPLATE(T, poly_t) B,
0741                                        const TEMPLATE(T, poly_t) Binv,
0742                                        const TEMPLATE(T, ctx_t) ctx);
0743
0744 void _TEMPLATE(T, poly_divrem_newton_n_preinv) (
0745     TEMPLATE(T, struct)* Q, TEMPLATE(T, struct)* R,
0746     const TEMPLATE(T, struct)* A, slong lenA,
0747     const TEMPLATE(T, struct)* B, slong lenB,
0748     const TEMPLATE(T, struct)* Binv, slong lenBinv,
0749     const TEMPLATE(T, ctx_t) ctx);
0750
0751 void TEMPLATE(T, poly_divrem_newton_n_preinv)(
0752     TEMPLATE(T, poly_t) Q, TEMPLATE(T, poly_t) R,
0753     const TEMPLATE(T, poly_t) A, const TEMPLATE(T, poly_t) B,
0754     const TEMPLATE(T, poly_t) Binv, const TEMPLATE(T, ctx_t) ctx);
0755
0756
0757 void _TEMPLATE(T, poly_divrem_f)(TEMPLATE(T, t) f,
0758                             TEMPLATE(T, struct)* Q, TEMPLATE(T, struct)* R,
0759                             const TEMPLATE(T, struct)* A, slong lenA,
0760                             const TEMPLATE(T, struct)* B, slong lenB,
0761                             const TEMPLATE(T, ctx_t) ctx);
0762
0763 void TEMPLATE(T, poly_divrem_f)(TEMPLATE(T, t) f,
0764                            TEMPLATE(T, poly_t) Q, TEMPLATE(T, poly_t) R,
0765                            const TEMPLATE(T, poly_t) A,
0766                            const TEMPLATE(T, poly_t) B,
0767                            const TEMPLATE(T, ctx_t) ctx);
0768
0769 /*  Divisibility testing  ***************************************************/
0770
0771 int _TEMPLATE(T, poly_divides)(TEMPLATE(T, struct) *Q,
0772                            const TEMPLATE(T, struct) *A, slong lenA,
0773                            const TEMPLATE(T, struct) *B, slong lenB,
0774                            const TEMPLATE(T, t) invB,
0775                            const TEMPLATE(T, ctx_t) ctx);
0776
0777 int TEMPLATE(T, poly_divides)(TEMPLATE(T, poly_t) Q,
0778                           const TEMPLATE(T, poly_t) A, const TEMPLATE(T, poly_t) B,
0779                           const TEMPLATE(T, ctx_t) ctx);
0780
0781 /*  Derivative  **************************************************************/
0782
0783 void _TEMPLATE(T, poly_derivative)(TEMPLATE(T, struct) *rop,
0784                               const TEMPLATE(T, struct) *op, slong len,
0785                               const TEMPLATE(T, ctx_t) ctx);
0786
0787 void TEMPLATE(T, poly_derivative)(TEMPLATE(T, poly_t) rop,
0788                              const TEMPLATE(T, poly_t) op,
0789                              const TEMPLATE(T, ctx_t) ctx);
0790
0791 /* Square root ***************************************************************/
0792
0793 void _TEMPLATE(T, poly_invsqrt_series)(TEMPLATE(T, struct) * g,
0794                const TEMPLATE(T, struct) * h, slong n, TEMPLATE(T, ctx_t) ctx);
0795
0796 void TEMPLATE(T, poly_invsqrt_series)(TEMPLATE(T, poly_t) g,
0797                  const TEMPLATE(T, poly_t) h, slong n, TEMPLATE(T, ctx_t) ctx);
0798
0799 void _TEMPLATE(T, poly_sqrt_series)(TEMPLATE(T, struct) * g,
0800                const TEMPLATE(T, struct) * h, slong n, TEMPLATE(T, ctx_t) ctx);
0801
0802 void TEMPLATE(T, poly_sqrt_series)(TEMPLATE(T, poly_t) g,
0803                  const TEMPLATE(T, poly_t) h, slong n, TEMPLATE(T, ctx_t) ctx);
0804
0805 int _TEMPLATE(T, poly_sqrt)(TEMPLATE(T, struct) * s,
0806              const TEMPLATE(T, struct) * p, slong len, TEMPLATE(T, ctx_t) ctx);
0807
0808 int TEMPLATE(T, poly_sqrt)(TEMPLATE(T, poly_t) b,
0809                           const TEMPLATE(T, poly_t) a, TEMPLATE(T, ctx_t) ctx);
0810
0811 /*  Evaluation  **************************************************************/
0812
0813 void _TEMPLATE3(T, poly_evaluate, T)(TEMPLATE(T, t) rop,
0814                                      const TEMPLATE(T, struct) *op, slong len,
0815                                      const TEMPLATE(T, t) a,
0816                                      const TEMPLATE(T, ctx_t) ctx);
0817
0818 void TEMPLATE3(T, poly_evaluate, T)(TEMPLATE(T, t) res,
0819                                     const TEMPLATE(T, poly_t) f,
0820                                     const TEMPLATE(T, t) a,
0821                                     const TEMPLATE(T, ctx_t) ctx);
0822
0823 void _TEMPLATE4(T, poly_evaluate, T, vec)(TEMPLATE(T, struct) * ys,
0824                                      const TEMPLATE(T, struct) *coeffs, slong len,
0825                                      const TEMPLATE(T, struct) *xs, slong n,
0826                                      const TEMPLATE(T, ctx_t) ctx);
0827
0828 void TEMPLATE4(T, poly_evaluate, T, vec)(TEMPLATE(T, struct) * ys,
0829                                     const TEMPLATE(T, poly_t) poly,
0830                                     const TEMPLATE(T, struct) * xs, slong n,
0831                                     const TEMPLATE(T, ctx_t) ctx);
0832
0833 TEMPLATE(T, poly_struct) **
0834 _TEMPLATE(T, poly_tree_alloc)(slong len, const TEMPLATE(T, ctx_t) ctx);
0835
0836 void _TEMPLATE(T, poly_tree_free)(TEMPLATE(T, poly_struct) ** tree, slong len,
0837                              const TEMPLATE(T, ctx_t) ctx);
0838
0839 void _TEMPLATE(T, poly_tree_build)(TEMPLATE(T, poly_struct) ** tree,
0840                               const TEMPLATE(T, struct) * roots,
0841                               slong len,
0842                               const TEMPLATE(T, ctx_t) ctx);
0843
0844 void _TEMPLATE4(T, poly_evaluate, T, vec_fast_precomp)
0845     (TEMPLATE(T, struct) * vs,
0846      const TEMPLATE(T, struct) * poly, slong plen,
0847      TEMPLATE(T, poly_struct) * const * tree, slong len,
0848      const TEMPLATE(T, ctx_t) ctx);
0849
0850 void _TEMPLATE4(T, poly_evaluate, T, vec_fast)(TEMPLATE(T, struct) * ys,
0851                                           const TEMPLATE(T, struct) * poly, slong plen,
0852                                           const TEMPLATE(T, struct) * xs, slong n,
0853                                           const TEMPLATE(T, ctx_t) ctx);
0854
0855 void TEMPLATE4(T, poly_evaluate, T, vec_fast)(TEMPLATE(T, struct) * ys,
0856                                          const TEMPLATE(T, poly_t) poly,
0857                                          const TEMPLATE(T, struct) *xs, slong n,
0858                                          const TEMPLATE(T, ctx_t) ctx);
0859
0860 void _TEMPLATE4(T, poly_evaluate, T, vec_iter)(TEMPLATE(T, struct) * ys,
0861                                           const TEMPLATE(T, struct) * coeffs, slong len,
0862                                           const TEMPLATE(T, struct) * xs, slong n,
0863                                           const TEMPLATE(T, ctx_t) ctx);
0864
0865 void TEMPLATE4(T, poly_evaluate, T, vec_iter)(TEMPLATE(T, struct) * ys,
0866                                          const TEMPLATE(T, poly_t) poly,
0867                                          const TEMPLATE(T, struct) * xs, slong n,
0868                                          const TEMPLATE(T, ctx_t) ctx);
0869
0870 /*  Composition  *************************************************************/
0871
0872 void _TEMPLATE(T, poly_compose)(TEMPLATE(T, struct) *rop,
0873                            const TEMPLATE(T, struct) *op1, slong len1,
0874                            const TEMPLATE(T, struct) *op2, slong len2,
0875                            const TEMPLATE(T, ctx_t) ctx);
0876
0877 void TEMPLATE(T, poly_compose)(TEMPLATE(T, poly_t) rop,
0878                           const TEMPLATE(T, poly_t) op1,
0879                           const TEMPLATE(T, poly_t) op2,
0880                           const TEMPLATE(T, ctx_t) ctx);
0881
0882 void _TEMPLATE(T, poly_compose_mod)(TEMPLATE(T, struct) * res,
0883                      const TEMPLATE(T, struct) * f, slong lenf,
0884                      const TEMPLATE(T, struct) * g,
0885                      const TEMPLATE(T, struct) * h, slong lenh,
0886                      const TEMPLATE(T, ctx_t) ctx);
0887
0888 void TEMPLATE(T, poly_compose_mod)(TEMPLATE(T, poly_t) res,
0889                               const TEMPLATE(T, poly_t) poly1,
0890                               const TEMPLATE(T, poly_t) poly2,
0891                               const TEMPLATE(T, poly_t) poly3,
0892                               const TEMPLATE(T, ctx_t) ctx);
0893
0894 void _TEMPLATE(T, poly_compose_mod_preinv)(
0895     TEMPLATE(T, struct) * res,
0896     const TEMPLATE(T, struct) * f, slong lenf,
0897     const TEMPLATE(T, struct) * g,
0898     const TEMPLATE(T, struct) * h, slong lenh,
0899     const TEMPLATE(T, struct) * hinv, slong lenhinv,
0900     const TEMPLATE(T, ctx_t) ctx);
0901
0902 void TEMPLATE(T, poly_compose_mod_preinv)(TEMPLATE(T, poly_t) res,
0903                                      const TEMPLATE(T, poly_t) poly1,
0904                                      const TEMPLATE(T, poly_t) poly2,
0905                                      const TEMPLATE(T, poly_t) poly3,
0906                                      const TEMPLATE(T, poly_t) poly3inv,
0907                                      const TEMPLATE(T, ctx_t) ctx);
0908
0909
0910 void _TEMPLATE(T, poly_compose_mod_horner)(
0911     TEMPLATE(T, struct) * res,
0912     const TEMPLATE(T, struct) * f, slong lenf,
0913     const TEMPLATE(T, struct) * g,
0914     const TEMPLATE(T, struct) * h, slong lenh,
0915     const TEMPLATE(T, ctx_t) ctx);
0916
0917 void TEMPLATE(T, poly_compose_mod_horner)(TEMPLATE(T, poly_t) res,
0918                                      const TEMPLATE(T, poly_t) poly1,
0919                                      const TEMPLATE(T, poly_t) poly2,
0920                                      const TEMPLATE(T, poly_t) poly3,
0921                                      const TEMPLATE(T, ctx_t) ctx);
0922
0923 void _TEMPLATE(T, poly_compose_mod_horner_preinv)(
0924     TEMPLATE(T, struct) * res,
0925     const TEMPLATE(T, struct) * f, slong lenf,
0926     const TEMPLATE(T, struct) * g,
0927     const TEMPLATE(T, struct) * h, slong lenh,
0928     const TEMPLATE(T, struct) * hinv, slong lenhinv,
0929     const TEMPLATE(T, ctx_t) ctx);
0930
0931 void TEMPLATE(T, poly_compose_mod_horner_preinv)(TEMPLATE(T, poly_t) res,
0932                                             const TEMPLATE(T, poly_t) poly1,
0933                                             const TEMPLATE(T, poly_t) poly2,
0934                                             const TEMPLATE(T, poly_t) poly3,
0935                                             const TEMPLATE(T, poly_t) poly3inv,
0936                                             const TEMPLATE(T, ctx_t) ctx);
0937
0938 void TEMPLATE(T, poly_compose_mod_brent_kung)(TEMPLATE(T, poly_t) res,
0939                                          const TEMPLATE(T, poly_t) poly1,
0940                                          const TEMPLATE(T, poly_t) poly2,
0941                                          const TEMPLATE(T, poly_t) poly3,
0942                                          const TEMPLATE(T, ctx_t) ctx);
0943
0944 void _TEMPLATE(T, poly_compose_mod_brent_kung)(
0945     TEMPLATE(T, struct) * res,
0946     const TEMPLATE(T, struct) * poly1, slong len1,
0947     const TEMPLATE(T, struct) * poly2,
0948     const TEMPLATE(T, struct) * poly3, slong len3,
0949     const TEMPLATE(T, ctx_t) ctx);
0950
0951 void _TEMPLATE(T, poly_compose_mod_brent_kung_preinv)(
0952     TEMPLATE(T, struct) * res,
0953     const TEMPLATE(T, struct) * poly1, slong len1,
0954     const TEMPLATE(T, struct) * poly2,
0955     const TEMPLATE(T, struct) * poly3, slong len3,
0956     const TEMPLATE(T, struct) * poly3inv, slong len3inv,
0957     const TEMPLATE(T, ctx_t) ctx);
0958
0959 void TEMPLATE(T, poly_compose_mod_brent_kung_preinv)(
0960     TEMPLATE(T, poly_t) res,
0961     const TEMPLATE(T, poly_t) poly1,
0962     const TEMPLATE(T, poly_t) poly2,
0963     const TEMPLATE(T, poly_t) poly3,
0964     const TEMPLATE(T, poly_t) poly3inv,
0965     const TEMPLATE(T, ctx_t) ctx);
0966
0967 void _TEMPLATE(T, poly_reduce_matrix_mod_poly) (TEMPLATE(T, mat_t) A,
0968                                            const TEMPLATE(T, mat_t) B,
0969                                            const TEMPLATE(T, poly_t) f,
0970                                            const TEMPLATE(T, ctx_t) ctx);
0971
0972 void _TEMPLATE(T, poly_precompute_matrix) (
0973     TEMPLATE(T, mat_t A),
0974     const TEMPLATE(T, struct)* poly1,
0975     const TEMPLATE(T, struct)* poly2, slong len2,
0976     const TEMPLATE(T, struct)* poly2inv, slong len2inv,
0977     const TEMPLATE(T, ctx_t) ctx);
0978
0979 void TEMPLATE(T, poly_precompute_matrix) (TEMPLATE(T, mat_t A),
0980                                      const TEMPLATE(T, poly_t) poly1,
0981                                      const TEMPLATE(T, poly_t) poly2,
0982                                      const TEMPLATE(T, poly_t) poly2inv,
0983                                      const TEMPLATE(T, ctx_t) ctx);
0984
0985 void _TEMPLATE(T, poly_compose_mod_brent_kung_precomp_preinv)(
0986     TEMPLATE(T, struct)* res,
0987     const TEMPLATE(T, struct)* poly1, slong len1,
0988     const TEMPLATE(T, mat_t) A,
0989     const TEMPLATE(T, struct)* poly3, slong len3,
0990     const TEMPLATE(T, struct)* poly3inv, slong len3inv,
0991     const TEMPLATE(T, ctx_t) ctx);
0992
0993 void TEMPLATE(T, poly_compose_mod_brent_kung_precomp_preinv)(
0994     TEMPLATE(T, poly_t) res,
0995     const TEMPLATE(T, poly_t) poly1,
0996     const TEMPLATE(T, mat_t) A,
0997     const TEMPLATE(T, poly_t) poly3,
0998     const TEMPLATE(T, poly_t) poly3inv,
0999     const TEMPLATE(T, ctx_t) ctx);
1000
1001 /*  Input and output  ********************************************************/
1002
1003 #ifdef FLINT_HAVE_FILE
1004 int _TEMPLATE(T, poly_fprint_pretty)(FILE *file, const TEMPLATE(T, struct) *poly, slong len, const char *x, const TEMPLATE(T, ctx_t) ctx);
1005 int TEMPLATE(T, poly_fprint_pretty)(FILE * file, const TEMPLATE(T, poly_t) poly, const char *x, const TEMPLATE(T, ctx_t) ctx);
1006 int _TEMPLATE(T, poly_fprint)(FILE * file, const TEMPLATE(T, struct) *poly, slong len, const TEMPLATE(T, ctx_t) ctx);
1007 int TEMPLATE(T, poly_fprint)(FILE * file, const TEMPLATE(T, poly_t) poly, const TEMPLATE(T, ctx_t) ctx);
1008 #endif
1009
1010 int _TEMPLATE(T, poly_print)(const TEMPLATE(T, struct) *poly, slong len, const TEMPLATE(T, ctx_t) ctx);
1011 int TEMPLATE(T, poly_print)(const TEMPLATE(T, poly_t) poly, const TEMPLATE(T, ctx_t) ctx);
1012 int _TEMPLATE(T, poly_print_pretty)(const TEMPLATE(T, struct) *poly, slong len, const char *x, const TEMPLATE(T, ctx_t) ctx);
1013 int TEMPLATE(T, poly_print_pretty)(const TEMPLATE(T, poly_t) poly, const char *x, const TEMPLATE(T, ctx_t) ctx);
1014
1015 char * _TEMPLATE(T, poly_get_str_pretty)(const TEMPLATE(T, struct) * poly, slong len,
1016                                   const char *x,
1017                                   const TEMPLATE(T, ctx_t) ctx);
1018
1019 char * TEMPLATE(T, poly_get_str_pretty)(const TEMPLATE(T, poly_t) poly,
1020                                  const char *x,
1021                                  const TEMPLATE(T, ctx_t) ctx);
1022
1023 char * _TEMPLATE(T, poly_get_str)(const TEMPLATE(T, struct) * poly, slong len,
1024                            const TEMPLATE(T, ctx_t) ctx);
1025
1026 char * TEMPLATE(T, poly_get_str)(const TEMPLATE(T, poly_t) poly,
1027                           const TEMPLATE(T, ctx_t) ctx);
1028
1029 /* Characteristic polynomial ************************************************/
1030
1031 void TEMPLATE(T, mat_charpoly)(TEMPLATE(T, poly_t) p,
1032                        const TEMPLATE(T, mat_t) M, const TEMPLATE(T, ctx_t) ctx);
1033
1034 /* Minimal polynomial ************************************************/
1035
1036
1037 void TEMPLATE(T, mat_minpoly) (TEMPLATE(T, poly_t) p,
1038                       const TEMPLATE(T, mat_t) X, const TEMPLATE(T, ctx_t) ctx);
1039
1040 #ifdef __cplusplus
1041 }
1042 #endif
1043
1044 #endif