include/flint/qadic.h

0001 /*
0002     Copyright (C) 2011, 2012, 2013 Sebastian Pancratz
0003
0004     This file is part of FLINT.
0005
0006     FLINT is free software: you can redistribute it and/or modify it under
0007     the terms of the GNU Lesser General Public License (LGPL) as published
0008     by the Free Software Foundation; either version 3 of the License, or
0009     (at your option) any later version.  See <https://www.gnu.org/licenses/>.
0010 */
0011
0012 #ifndef QADIC_H
0013 #define QADIC_H
0014
0015 #ifdef QADIC_INLINES_C
0016 #define QADIC_INLINE
0017 #else
0018 #define QADIC_INLINE static inline
0019 #endif
0020
0021 #include "fmpz_vec.h"
0022 #include "fmpz_mod_types.h"
0023 #include "nmod_types.h"
0024 #include "padic.h"
0025 #include "padic_poly.h"
0026
0027 #ifdef __cplusplus
0028  extern "C" {
0029 #endif
0030
0031 /* Data types and context ****************************************************/
0032
0033 typedef padic_poly_t qadic_t;
0034
0035 typedef padic_poly_struct qadic_struct;
0036
0037 QADIC_INLINE slong qadic_val(const qadic_t op)
0038 {
0039     return padic_poly_val(op);
0040 }
0041
0042 QADIC_INLINE slong qadic_prec(const qadic_t op)
0043 {
0044     return padic_poly_prec(op);
0045 }
0046
0047 typedef struct
0048 {
0049     padic_ctx_struct pctx;
0050
0051     fmpz *a;
0052     slong *j;
0053     slong len;
0054
0055     char *var;
0056 }
0057 qadic_ctx_struct;
0058
0059 typedef qadic_ctx_struct qadic_ctx_t[1];
0060
0061 int _qadic_ctx_init_conway_ui(qadic_ctx_t ctx, ulong p, slong d,
0062         slong min, slong max, const char * var, enum padic_print_mode mode);
0063
0064 void qadic_ctx_init_conway(qadic_ctx_t ctx,
0065                            const fmpz_t p, slong d, slong min, slong max,
0066                            const char *var, enum padic_print_mode mode);
0067
0068 void qadic_ctx_init_modulus(qadic_ctx_t ctx, const fmpz_t p, const fmpz_mod_poly_t modulus,
0069                            slong min, slong max,
0070                            const char *var, enum padic_print_mode mode);
0071
0072 void qadic_ctx_init_modulus_nmod(qadic_ctx_t ctx, ulong p, const nmod_poly_t modulus,
0073                            slong min, slong max,
0074                            const char *var, enum padic_print_mode mode);
0075
0076 void qadic_ctx_init(qadic_ctx_t ctx,
0077                            const fmpz_t p, slong d, slong min, slong max,
0078                            const char *var, enum padic_print_mode mode);
0079
0080 void qadic_ctx_clear(qadic_ctx_t ctx);
0081
0082 QADIC_INLINE slong qadic_ctx_degree(const qadic_ctx_t ctx)
0083 {
0084     return ctx->j[ctx->len - 1];
0085 }
0086
0087 QADIC_INLINE void qadic_ctx_print(const qadic_ctx_t ctx)
0088 {
0089     slong i, k;
0090
0091     flint_printf("p    = "), fmpz_print((&ctx->pctx)->p), flint_printf("\n");
0092     flint_printf("d    = %wd\n", ctx->j[ctx->len - 1]);
0093     flint_printf("f(X) = ");
0094     fmpz_print(ctx->a + 0);
0095     for (k = 1; k < ctx->len; k++)
0096     {
0097         i = ctx->j[k];
0098         flint_printf(" + ");
0099         if (fmpz_is_one(ctx->a + k))
0100         {
0101             if (i == 1)
0102                 flint_printf("X");
0103             else
0104                 flint_printf("X^%wd", i);
0105         }
0106         else
0107         {
0108             fmpz_print(ctx->a + k);
0109             if (i == 1)
0110                 flint_printf("*X");
0111             else
0112                 flint_printf("*X^%wd", i);
0113         }
0114     }
0115     flint_printf("\n");
0116 }
0117
0118 /* Memory management *********************************************************/
0119
0120 QADIC_INLINE void qadic_init(qadic_t x)
0121 {
0122     padic_poly_init(x);
0123 }
0124
0125 QADIC_INLINE void qadic_init2(qadic_t rop, slong prec)
0126 {
0127     padic_poly_init2(rop, 0, prec);
0128 }
0129
0130 QADIC_INLINE void qadic_clear(qadic_t x)
0131 {
0132     padic_poly_clear(x);
0133 }
0134
0135 /*
0136     TODO:  Consider renaming this function, prefix for the "qadic" module.
0137  */
0138
0139 QADIC_INLINE void
0140 _fmpz_poly_reduce(fmpz *R, slong lenR, const fmpz *a, const slong *j, slong len)
0141 {
0142     const slong d = j[len - 1];
0143     slong i, k;
0144
0145     FMPZ_VEC_NORM(R, lenR);
0146
0147     for (i = lenR - 1; i >= d; i--)
0148     {
0149         for (k = len - 2; k >= 0; k--)
0150         {
0151             fmpz_submul(R + j[k] + i - d, R + i, a + k);
0152         }
0153         fmpz_zero(R + i);
0154     }
0155 }
0156
0157 /*
0158     TODO:  Consider renaming this function, prefix for the "qadic" module.
0159  */
0160
0161 QADIC_INLINE void
0162 _fmpz_mod_poly_reduce(fmpz *R, slong lenR,
0163                       const fmpz *a, const slong *j, slong len, const fmpz_t p)
0164 {
0165     const slong d = j[len - 1];
0166
0167     if (lenR > d)
0168     {
0169         _fmpz_poly_reduce(R, lenR, a, j, len);
0170         _fmpz_vec_scalar_mod_fmpz(R, R, d, p);
0171     }
0172     else
0173     {
0174         _fmpz_vec_scalar_mod_fmpz(R, R, lenR, p);
0175     }
0176 }
0177
0178 QADIC_INLINE void qadic_reduce(qadic_t x, const qadic_ctx_t ctx)
0179 {
0180     const slong N = qadic_prec(x);
0181     const slong d = ctx->j[ctx->len - 1];
0182
0183     if (x->length == 0 || x->val >= N)
0184     {
0185         padic_poly_zero(x);
0186     }
0187     else
0188     {
0189         fmpz_t pow;
0190         int alloc;
0191
0192         alloc = _padic_ctx_pow_ui(pow, N - x->val, &ctx->pctx);
0193
0194         _fmpz_mod_poly_reduce(x->coeffs, x->length, ctx->a, ctx->j, ctx->len, pow);
0195         _padic_poly_set_length(x, FLINT_MIN(x->length, d));
0196         _padic_poly_normalise(x);
0197         padic_poly_canonicalise(x, (&ctx->pctx)->p);
0198
0199         if (alloc)
0200             fmpz_clear(pow);
0201     }
0202 }
0203
0204 /* Randomisation *************************************************************/
0205
0206 QADIC_INLINE void
0207 qadic_randtest(qadic_t x, flint_rand_t state, const qadic_ctx_t ctx)
0208 {
0209     padic_poly_randtest(x, state, qadic_ctx_degree(ctx), &ctx->pctx);
0210 }
0211
0212 QADIC_INLINE void
0213 qadic_randtest_not_zero(qadic_t x, flint_rand_t state, const qadic_ctx_t ctx)
0214 {
0215     padic_poly_randtest_not_zero(x, state, qadic_ctx_degree(ctx),
0216                                  &ctx->pctx);
0217 }
0218
0219 QADIC_INLINE void
0220 qadic_randtest_val(qadic_t x, flint_rand_t state, slong val,
0221                    const qadic_ctx_t ctx)
0222 {
0223     padic_poly_randtest_val(x, state, val, qadic_ctx_degree(ctx), &ctx->pctx);
0224 }
0225
0226 QADIC_INLINE void
0227 qadic_randtest_int(qadic_t x, flint_rand_t state, const qadic_ctx_t ctx)
0228 {
0229     const slong N = qadic_prec(x);
0230
0231     if (N <= 0)
0232     {
0233         padic_poly_zero(x);
0234     }
0235     else
0236     {
0237         padic_poly_randtest_val(x, state, n_randint(state, N),
0238                                 qadic_ctx_degree(ctx), &ctx->pctx);
0239     }
0240 }
0241
0242 /* Assignments and conversions ***********************************************/
0243
0244 QADIC_INLINE void qadic_zero(qadic_t op)
0245 {
0246     padic_poly_zero(op);
0247 }
0248
0249 QADIC_INLINE void qadic_one(qadic_t op)
0250 {
0251     padic_poly_one(op);
0252 }
0253
0254 QADIC_INLINE void qadic_gen(qadic_t x, const qadic_ctx_t ctx)
0255 {
0256     const slong N = qadic_prec(x);
0257     const slong d = qadic_ctx_degree(ctx);
0258
0259     if (d > 1)
0260     {
0261         if (N > 0)
0262         {
0263             padic_poly_fit_length(x, 2);
0264             fmpz_zero(x->coeffs + 0);
0265             fmpz_one(x->coeffs + 1);
0266             _padic_poly_set_length(x, 2);
0267             x->val = 0;
0268         }
0269         else
0270         {
0271             padic_poly_zero(x);
0272         }
0273     }
0274     else
0275     {
0276         padic_poly_fit_length(x, 1);
0277     fmpz_neg(x->coeffs + 0, ctx->a + 0);
0278     _padic_poly_set_length(x, 1);
0279     x->val = 0;
0280     }
0281 }
0282
0283 QADIC_INLINE
0284 void qadic_set_ui(qadic_t rop, ulong op, const qadic_ctx_t ctx)
0285 {
0286     padic_poly_set_ui(rop, op, &ctx->pctx);
0287 }
0288
0289 QADIC_INLINE int
0290 qadic_get_padic(padic_t rop, const qadic_t op, const qadic_ctx_t ctx)
0291 {
0292     if (op->length > 0)
0293     {
0294         if (_fmpz_vec_is_zero(op->coeffs + 1, op->length - 1))
0295         {
0296             fmpz_set(padic_unit(rop), op->coeffs + 0);
0297             padic_val(rop) = op->val;
0298             _padic_canonicalise(rop, &ctx->pctx);
0299             return 1;
0300         }
0301         else
0302         {
0303             return 0;
0304         }
0305     }
0306     else
0307     {
0308         padic_zero(rop);
0309         return 1;
0310     }
0311 }
0312
0313 QADIC_INLINE void qadic_set(qadic_t rop, const qadic_t op, const qadic_ctx_t ctx)
0314 {
0315     padic_poly_set(rop, op, &(ctx->pctx));
0316 }
0317
0318 void qadic_set_fmpz_poly(qadic_t rop, const fmpz_poly_t op,
0319                          const qadic_ctx_t ctx);
0320
0321 /* Comparison ****************************************************************/
0322
0323 QADIC_INLINE int qadic_is_zero(const qadic_t op)
0324 {
0325     return padic_poly_is_zero(op);
0326 }
0327
0328 QADIC_INLINE int qadic_is_one(const qadic_t op)
0329 {
0330     return padic_poly_is_one(op);
0331 }
0332
0333 QADIC_INLINE int qadic_equal(const qadic_t op1, const qadic_t op2)
0334 {
0335     return padic_poly_equal(op1, op2);
0336 }
0337
0338 /* Basic arithmetic **********************************************************/
0339
0340 QADIC_INLINE void
0341 qadic_add(qadic_t x, const qadic_t y, const qadic_t z, const qadic_ctx_t ctx)
0342 {
0343     padic_poly_add(x, y, z, &ctx->pctx);
0344 }
0345
0346 QADIC_INLINE void
0347 qadic_sub(qadic_t x, const qadic_t y, const qadic_t z, const qadic_ctx_t ctx)
0348 {
0349     padic_poly_sub(x, y, z, &ctx->pctx);
0350 }
0351
0352 QADIC_INLINE void
0353 qadic_neg(qadic_t x, const qadic_t y, const qadic_ctx_t ctx)
0354 {
0355     padic_poly_neg(x, y, &ctx->pctx);
0356 }
0357
0358 void qadic_mul(qadic_t x, const qadic_t y, const qadic_t z,
0359                           const qadic_ctx_t ctx);
0360
0361 void _qadic_inv(fmpz *rop, const fmpz *op, slong len,
0362                 const fmpz *a, const slong *j, slong lena,
0363                 const fmpz_t p, slong N);
0364
0365 void qadic_inv(qadic_t x, const qadic_t y, const qadic_ctx_t ctx);
0366
0367 void _qadic_pow(fmpz *rop, const fmpz *op, slong len, const fmpz_t e,
0368                 const fmpz *a, const slong *j, slong lena,
0369                 const fmpz_t p);
0370
0371 void qadic_pow(qadic_t x, const qadic_t y, const fmpz_t e, const qadic_ctx_t ctx);
0372
0373 /* Special functions *********************************************************/
0374
0375 void _qadic_exp_rectangular(fmpz *rop, const fmpz *op, slong v, slong len,
0376                             const fmpz *a, const slong *j, slong lena,
0377                             const fmpz_t p, slong N, const fmpz_t pN);
0378
0379 int qadic_exp_rectangular(qadic_t rop, const qadic_t op,
0380                           const qadic_ctx_t ctx);
0381
0382 void _qadic_exp_balanced(fmpz *rop, const fmpz *op, slong v, slong len,
0383                          const fmpz *a, const slong *j, slong lena,
0384                          const fmpz_t p, slong N, const fmpz_t pN);
0385
0386 int qadic_exp_balanced(qadic_t rop, const qadic_t op,
0387                        const qadic_ctx_t ctx);
0388
0389 void _qadic_exp(fmpz *rop, const fmpz *op, slong v, slong len,
0390                            const fmpz *a, const slong *j, slong lena,
0391                            const fmpz_t p, slong N, const fmpz_t pN);
0392
0393 int qadic_exp(qadic_t rop, const qadic_t op, const qadic_ctx_t ctx);
0394
0395 void _qadic_log_rectangular(fmpz *z, const fmpz *y, slong v, slong len,
0396                             const fmpz *a, const slong *j, slong lena,
0397                             const fmpz_t p, slong N, const fmpz_t pN);
0398
0399 int qadic_log_rectangular(qadic_t rop, const qadic_t op, const qadic_ctx_t ctx);
0400
0401 void _qadic_log_balanced(fmpz *z, const fmpz *y, slong len,
0402                          const fmpz *a, const slong *j, slong lena,
0403                          const fmpz_t p, slong N, const fmpz_t pN);
0404
0405 int qadic_log_balanced(qadic_t rop, const qadic_t op, const qadic_ctx_t ctx);
0406
0407 void _qadic_log(fmpz *z, const fmpz *y, slong v, slong len,
0408                 const fmpz *a, const slong *j, slong lena,
0409                 const fmpz_t p, slong N, const fmpz_t pN);
0410
0411 int qadic_log(qadic_t rop, const qadic_t op, const qadic_ctx_t ctx);
0412
0413 void _qadic_frobenius_a(fmpz *rop, slong exp,
0414                         const fmpz *a, const slong *j, slong lena,
0415                                   const fmpz_t p, slong N);
0416
0417
0418 void _qadic_frobenius(fmpz *rop, const fmpz *op, slong len, slong e,
0419                   const fmpz *a, const slong *j, slong lena,
0420                   const fmpz_t p, slong N);
0421
0422 void qadic_frobenius(qadic_t rop, const qadic_t op, slong e, const qadic_ctx_t ctx);
0423
0424 void _qadic_teichmuller(fmpz *rop, const fmpz *op, slong len,
0425                         const fmpz *a, const slong *j, slong lena,
0426                         const fmpz_t p, slong N);
0427
0428 void qadic_teichmuller(qadic_t rop, const qadic_t op, const qadic_ctx_t ctx);
0429
0430 void _qadic_trace(fmpz_t rop, const fmpz *op, slong len,
0431                   const fmpz *a, const slong *j, slong lena, const fmpz_t pN);
0432
0433 void qadic_trace(padic_t rop, const qadic_t op, const qadic_ctx_t ctx);
0434
0435
0436 void _qadic_norm_resultant(fmpz_t rop, const fmpz *op, slong len,
0437                            const fmpz *a, const slong *j, slong lena,
0438                            const fmpz_t p, slong N);
0439 void _qadic_norm_analytic(fmpz_t rop, const fmpz *y, slong v, slong len,
0440                           const fmpz *a, const slong *j, slong lena,
0441                           const fmpz_t p, slong N);
0442 void _qadic_norm(fmpz_t rop, const fmpz *op, slong len,
0443                  const fmpz *a, const slong *j, slong lena,
0444                  const fmpz_t p, slong N);
0445
0446 void qadic_norm(padic_t rop, const qadic_t op, const qadic_ctx_t ctx);
0447 void qadic_norm_analytic(padic_t rop, const qadic_t op, const qadic_ctx_t ctx);
0448 void qadic_norm_resultant(padic_t rop, const qadic_t op, const qadic_ctx_t ctx);
0449
0450 int qadic_sqrt(qadic_t rop, const qadic_t op, const qadic_ctx_t ctx);
0451
0452 struct qadic2_sqrt_precomp;
0453
0454 struct qadic2_sqrt_precomp *_qadic_char2_sqrt_precomp_init(const qadic_ctx_t ctx);
0455 int _qadic_char2_sqrt_with_precomp(qadic_t rop, const qadic_t op, const qadic_ctx_t ctx,
0456                                    const struct qadic2_sqrt_precomp *data);
0457 void _qadic_char2_sqrt_precomp_clear(struct qadic2_sqrt_precomp *data);
0458
0459 /* Output ********************************************************************/
0460
0461 #ifdef FLINT_HAVE_FILE
0462 int qadic_fprint_pretty(FILE * file, const qadic_t op, const qadic_ctx_t ctx);
0463 #endif
0464
0465 int qadic_print_pretty(const qadic_t op, const qadic_ctx_t ctx);
0466 int qadic_debug(const qadic_t op);
0467
0468 #ifdef __cplusplus
0469 }
0470 #endif
0471
0472 #endif