include/flint/nf_elem.h

0001 /*
0002     Copyright (C) 2013 William Hart
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 NF_ELEM_H
0013 #define NF_ELEM_H
0014
0015 #ifdef NF_ELEM_INLINES_C
0016 #define NF_ELEM_INLINE
0017 #else
0018 #define NF_ELEM_INLINE static inline
0019 #endif
0020
0021 #include "fmpq.h"
0022 #include "fmpz_mod_types.h"
0023 #include "nf.h"
0024
0025 #ifdef __cplusplus
0026 extern "C" {
0027 #endif
0028
0029 typedef struct /* element of a linear number field */
0030 {
0031    fmpz_t num;
0032    fmpz_t den;
0033 } lnf_elem_struct;
0034
0035 typedef lnf_elem_struct lnf_elem_t[1];
0036
0037 typedef struct /* element of a quadratic number field */
0038 {
0039    fmpz num[3]; /* extra coeff for delayed reduction */
0040    fmpz_t den;
0041 } qnf_elem_struct;
0042
0043 typedef qnf_elem_struct qnf_elem_t[1];
0044
0045 typedef union /* element in a number field (specified by an nf_t) */
0046 {
0047    fmpq_poly_t elem; /* general case */
0048    lnf_elem_t lelem; /* linear number field */
0049    qnf_elem_t qelem; /* quadratic number field */
0050 } nf_elem_struct;
0051
0052 typedef nf_elem_struct nf_elem_t[1];
0053
0054 #define NF_ELEM_NUMREF(xxx) fmpq_poly_numref((xxx)->elem)
0055 #define NF_ELEM_DENREF(xxx) fmpq_poly_denref((xxx)->elem)
0056 #define LNF_ELEM_NUMREF(xxx) ((xxx)->lelem->num)
0057 #define LNF_ELEM_DENREF(xxx) ((xxx)->lelem->den)
0058 #define QNF_ELEM_NUMREF(xxx) ((xxx)->qelem->num)
0059 #define QNF_ELEM_DENREF(xxx) ((xxx)->qelem->den)
0060 #define NF_ELEM(xxx) (xxx)->elem
0061 #define LNF_ELEM(xxx) (xxx)->lelem
0062 #define QNF_ELEM(xxx) (xxx)->qelem
0063
0064 /* memory management *********************************************************/
0065
0066 void nf_elem_init(nf_elem_t a, const nf_t nf);
0067 void nf_elem_clear(nf_elem_t a, const nf_t nf);
0068
0069 void nf_elem_swap(nf_elem_t a, nf_elem_t b, const nf_t nf);
0070
0071 void nf_elem_randtest(nf_elem_t a, flint_rand_t state, flint_bitcnt_t bits, const nf_t nf);
0072 void nf_elem_randtest_not_zero(nf_elem_t a, flint_rand_t state, flint_bitcnt_t bits, const nf_t nf);
0073
0074 NF_ELEM_INLINE
0075 void nf_elem_canonicalise(nf_elem_t a, const nf_t nf)
0076 {
0077     if (nf->flag & NF_LINEAR)
0078         _fmpq_canonicalise(LNF_ELEM_NUMREF(a), LNF_ELEM_DENREF(a));
0079     else if (nf->flag & NF_QUADRATIC)
0080         _fmpq_poly_canonicalise(QNF_ELEM_NUMREF(a), QNF_ELEM_DENREF(a), 3);
0081     else
0082         fmpq_poly_canonicalise(NF_ELEM(a));
0083 }
0084
0085 void _nf_elem_reduce(nf_elem_t a, const nf_t nf);
0086 void nf_elem_reduce(nf_elem_t a, const nf_t nf);
0087
0088 int _nf_elem_invertible_check(nf_elem_t a, const nf_t nf);
0089
0090 /* comparison ****************************************************************/
0091
0092 int _nf_elem_equal(const nf_elem_t a, const nf_elem_t b, const nf_t nf);
0093 int nf_elem_equal(const nf_elem_t a, const nf_elem_t b, const nf_t nf);
0094
0095 NF_ELEM_INLINE
0096 int nf_elem_is_zero(const nf_elem_t a, const nf_t nf)
0097 {
0098     if (nf->flag & NF_LINEAR)
0099         return fmpz_is_zero(LNF_ELEM_NUMREF(a));
0100     else if (nf->flag & NF_QUADRATIC)
0101         return fmpz_is_zero(QNF_ELEM_NUMREF(a)) && fmpz_is_zero(QNF_ELEM_NUMREF(a) + 1);
0102     else
0103         return fmpq_poly_is_zero(a->elem);
0104 }
0105
0106 NF_ELEM_INLINE
0107 int nf_elem_is_one(const nf_elem_t a, const nf_t nf)
0108 {
0109     if (nf->flag & NF_LINEAR)
0110         return fmpz_is_one(LNF_ELEM_NUMREF(a)) && fmpz_is_one(LNF_ELEM_DENREF(a));
0111     else if (nf->flag & NF_QUADRATIC)
0112         return fmpz_is_one(QNF_ELEM_NUMREF(a)) && fmpz_is_zero(QNF_ELEM_NUMREF(a) + 1)
0113                 && fmpz_is_one(QNF_ELEM_DENREF(a));
0114     else
0115         return fmpq_poly_is_one(a->elem);
0116 }
0117
0118 int nf_elem_is_gen(const nf_elem_t a, const nf_t nf);
0119
0120 NF_ELEM_INLINE
0121 int nf_elem_is_integer(const nf_elem_t a, const nf_t nf)
0122 {
0123     if (nf->flag & NF_LINEAR)
0124         return fmpz_is_one(LNF_ELEM_DENREF(a));
0125     else if (nf->flag & NF_QUADRATIC)
0126         return fmpz_is_zero(QNF_ELEM_NUMREF(a) + 1) && fmpz_is_one(QNF_ELEM_DENREF(a));
0127     else
0128         return NF_ELEM(a)->length <= 1 && fmpz_is_one(NF_ELEM_DENREF(a));
0129 }
0130
0131 NF_ELEM_INLINE
0132 int nf_elem_is_rational(const nf_elem_t a, const nf_t nf)
0133 {
0134     if (nf->flag & NF_LINEAR)
0135         return 1;
0136     else if (nf->flag & NF_QUADRATIC)
0137         return fmpz_is_zero(QNF_ELEM_NUMREF(a) + 1);
0138     else
0139         return NF_ELEM(a)->length <= 1;
0140 }
0141
0142 int nf_elem_equal_si(const nf_elem_t a, const slong b, const nf_t nf);
0143 int nf_elem_equal_ui(const nf_elem_t a, const ulong b, const nf_t nf);
0144 int nf_elem_equal_fmpz(const nf_elem_t a, const fmpz_t b, const nf_t nf);
0145 int nf_elem_equal_fmpq(const nf_elem_t a, const fmpq_t b, const nf_t nf);
0146
0147 /* I/O ***********************************************************************/
0148
0149 void nf_elem_print_pretty(const nf_elem_t a, const nf_t nf, const char * var);
0150 char * nf_elem_get_str_pretty(const nf_elem_t a, const char * var, const nf_t nf);
0151
0152 /* assignments and conversions ***********************************************/
0153
0154 void nf_elem_zero(nf_elem_t a, const nf_t nf);
0155 void nf_elem_one(nf_elem_t a, const nf_t nf);
0156 void nf_elem_gen(nf_elem_t a, const nf_t nf);
0157
0158 void nf_elem_set(nf_elem_t a, const nf_elem_t b, const nf_t nf);
0159 void nf_elem_set_si(nf_elem_t a, slong c, const nf_t nf);
0160 void nf_elem_set_ui(nf_elem_t a, ulong c, const nf_t nf);
0161 void nf_elem_set_fmpz(nf_elem_t a, const fmpz_t c, const nf_t nf);
0162 void nf_elem_set_fmpq(nf_elem_t a, const fmpq_t c, const nf_t nf);
0163 void nf_elem_set_fmpq_poly(nf_elem_t a, const fmpq_poly_t pol, const nf_t nf);
0164
0165 void nf_elem_set_fmpz_mat_row(nf_elem_t b, const fmpz_mat_t M, const slong i, fmpz_t den, const nf_t nf);
0166 void nf_elem_get_fmpz_mat_row(fmpz_mat_t M, const slong i, fmpz_t den, const nf_elem_t b, const nf_t nf);
0167
0168 void nf_elem_get_fmpq_poly(fmpq_poly_t pol, const nf_elem_t a, const nf_t nf);
0169
0170 void nf_elem_get_nmod_poly_den(nmod_poly_t pol, const nf_elem_t a, const nf_t nf, int den);
0171
0172 void _nf_elem_get_nmod_poly(nmod_poly_t pol, const nf_elem_t a, const nf_t nf);
0173 void nf_elem_get_nmod_poly(nmod_poly_t pol, const nf_elem_t a, const nf_t nf);
0174
0175 void nf_elem_get_fmpz_mod_poly_den(fmpz_mod_poly_t pol, const nf_elem_t a, const nf_t nf, int den, const fmpz_mod_ctx_t ctx);
0176
0177 void _nf_elem_get_fmpz_mod_poly(fmpz_mod_poly_t pol, const nf_elem_t a, const nf_t nf, const fmpz_mod_ctx_t ctx);
0178 void nf_elem_get_fmpz_mod_poly(fmpz_mod_poly_t pol, const nf_elem_t a, const nf_t nf, const fmpz_mod_ctx_t ctx);
0179
0180 /* manipulation **************************************************************/
0181
0182 NF_ELEM_INLINE
0183 void nf_elem_get_den(fmpz_t d, const nf_elem_t b, const nf_t nf)
0184 {
0185     if (nf->flag & NF_LINEAR)
0186         fmpz_set(d, LNF_ELEM_DENREF(b));
0187     else if (nf->flag & NF_QUADRATIC)
0188         fmpz_set(d, QNF_ELEM_DENREF(b));
0189     else
0190         fmpz_set(d, NF_ELEM_DENREF(b));
0191 }
0192
0193 NF_ELEM_INLINE
0194 void nf_elem_set_den(nf_elem_t b, fmpz_t d, const nf_t nf)
0195 {
0196     if (nf->flag & NF_LINEAR)
0197         fmpz_set(LNF_ELEM_DENREF(b), d);
0198     else if (nf->flag & NF_QUADRATIC)
0199         fmpz_set(QNF_ELEM_DENREF(b), d);
0200     else
0201         fmpz_set(NF_ELEM_DENREF(b), d);
0202 }
0203
0204 void nf_elem_get_coeff_fmpq(fmpq_t a, const nf_elem_t b, slong i, const nf_t nf);
0205
0206 void nf_elem_get_coeff_fmpz(fmpz_t a, const nf_elem_t b, slong i, const nf_t nf);
0207
0208 NF_ELEM_INLINE
0209 int nf_elem_den_is_one(const nf_elem_t a, const nf_t nf)
0210 {
0211     if (nf->flag & NF_LINEAR)
0212         return fmpz_is_one(LNF_ELEM_DENREF(a));
0213     else if (nf->flag & NF_QUADRATIC)
0214         return fmpz_is_one(QNF_ELEM_DENREF(a));
0215     else
0216         return fmpz_is_one(NF_ELEM_DENREF(a));
0217 }
0218
0219 void _nf_elem_set_coeff_num_fmpz(nf_elem_t a, slong i, const fmpz_t b, const nf_t nf);
0220
0221 /* arithmetic ****************************************************************/
0222
0223 void nf_elem_neg(nf_elem_t a, const nf_elem_t b, const nf_t nf);
0224
0225 void nf_elem_add_si(nf_elem_t a, const nf_elem_t b, slong c, const nf_t nf);
0226 void nf_elem_add_fmpz(nf_elem_t a, const nf_elem_t b, const fmpz_t c, const nf_t nf);
0227 void nf_elem_add_fmpq(nf_elem_t a, const nf_elem_t b, const fmpq_t c, const nf_t nf);
0228
0229 void nf_elem_sub_si(nf_elem_t a, const nf_elem_t b, slong c, const nf_t nf);
0230 void nf_elem_sub_fmpz(nf_elem_t a, const nf_elem_t b, const fmpz_t c, const nf_t nf);
0231 void nf_elem_sub_fmpq(nf_elem_t a, const nf_elem_t b, const fmpq_t c, const nf_t nf);
0232 void nf_elem_si_sub(nf_elem_t a, slong c, const nf_elem_t b, const nf_t nf);
0233 void nf_elem_fmpz_sub(nf_elem_t a, const fmpz_t c, const nf_elem_t b, const nf_t nf);
0234 void nf_elem_fmpq_sub(nf_elem_t a, const fmpq_t c, const nf_elem_t b, const nf_t nf);
0235
0236 void nf_elem_scalar_mul_si(nf_elem_t a, const nf_elem_t b, slong c, const nf_t nf);
0237 void nf_elem_scalar_mul_fmpz(nf_elem_t a, const nf_elem_t b, const fmpz_t c, const nf_t nf);
0238 void nf_elem_scalar_mul_fmpq(nf_elem_t a, const nf_elem_t b, const fmpq_t c, const nf_t nf);
0239
0240 void nf_elem_scalar_div_si(nf_elem_t a, const nf_elem_t b, slong c, const nf_t nf);
0241 void nf_elem_scalar_div_fmpz(nf_elem_t a, const nf_elem_t b, const fmpz_t c, const nf_t nf);
0242 void nf_elem_scalar_div_fmpq(nf_elem_t a, const nf_elem_t b, const fmpq_t c, const nf_t nf);
0243
0244 void _nf_elem_add_lf(nf_elem_t a, const nf_elem_t b, const nf_elem_t c, const nf_t nf, int can);
0245 void _nf_elem_sub_lf(nf_elem_t a, const nf_elem_t b, const nf_elem_t c, const nf_t nf, int can);
0246
0247 void _nf_elem_add_qf(nf_elem_t a, const nf_elem_t b, const nf_elem_t c, const nf_t nf, int can);
0248 void nf_elem_add_qf(nf_elem_t a, const nf_elem_t b, const nf_elem_t c, const nf_t nf);
0249
0250 void _nf_elem_sub_qf(nf_elem_t a, const nf_elem_t b, const nf_elem_t c, const nf_t nf, int can);
0251 void nf_elem_sub_qf(nf_elem_t a, const nf_elem_t b, const nf_elem_t c, const nf_t nf);
0252
0253 void _nf_elem_add(nf_elem_t a, const nf_elem_t b, const nf_elem_t c, const nf_t nf);
0254 void nf_elem_add(nf_elem_t a, const nf_elem_t b, const nf_elem_t c, const nf_t nf);
0255
0256 void _nf_elem_sub(nf_elem_t a, const nf_elem_t b, const nf_elem_t c, const nf_t nf);
0257 void nf_elem_sub(nf_elem_t a, const nf_elem_t b, const nf_elem_t c, const nf_t nf);
0258
0259 void nf_elem_mul_gen(nf_elem_t a, const nf_elem_t b, const nf_t nf);
0260
0261 void _nf_elem_mul(nf_elem_t a, const nf_elem_t b, const nf_elem_t c, const nf_t nf);
0262 void nf_elem_mul(nf_elem_t a, const nf_elem_t b, const nf_elem_t c, const nf_t nf);
0263
0264 void _nf_elem_mul_red(nf_elem_t a, const nf_elem_t b, const nf_elem_t c, const nf_t nf, int red);
0265 void nf_elem_mul_red(nf_elem_t a, const nf_elem_t b, const nf_elem_t c, const nf_t nf, int red);
0266
0267 void _nf_elem_inv(nf_elem_t a, const nf_elem_t b, const nf_t nf);
0268 void nf_elem_inv(nf_elem_t a, const nf_elem_t b, const nf_t nf);
0269
0270 void _nf_elem_div(nf_elem_t a, const nf_elem_t b, const nf_elem_t c, const nf_t nf);
0271 void nf_elem_div(nf_elem_t a, const nf_elem_t b, const nf_elem_t c, const nf_t nf);
0272
0273 void _nf_elem_pow(nf_elem_t res, const nf_elem_t b, ulong e, const nf_t nf);
0274 void nf_elem_pow(nf_elem_t res, const nf_elem_t a, ulong e, const nf_t nf);
0275
0276 void _nf_elem_norm(fmpz_t rnum, fmpz_t rden, const nf_elem_t a, const nf_t nf);
0277 void nf_elem_norm(fmpq_t res, const nf_elem_t a, const nf_t nf);
0278
0279 void _nf_elem_norm_div(fmpz_t rnum, fmpz_t rden, const nf_elem_t a, const nf_t nf, const fmpz_t divisor, slong nbits);
0280 void nf_elem_norm_div(fmpq_t res, const nf_elem_t a, const nf_t nf, const fmpz_t divisor, slong nbits);
0281
0282 void _nf_elem_trace(fmpz_t rnum, fmpz_t rden, const nf_elem_t a, const nf_t nf);
0283 void nf_elem_trace(fmpq_t res, const nf_elem_t a, const nf_t nf);
0284
0285 void nf_elem_rep_mat(fmpq_mat_t res, const nf_elem_t a, const nf_t nf);
0286
0287 void nf_elem_rep_mat_fmpz_mat_den(fmpz_mat_t res, fmpz_t den, const nf_elem_t a, const nf_t nf);
0288
0289 /* modular reduction *********************************************************/
0290
0291 void nf_elem_mod_fmpz_den(nf_elem_t res, const nf_elem_t a, const fmpz_t mod, const nf_t nf, int den);
0292
0293 void _nf_elem_mod_fmpz(nf_elem_t res, const nf_elem_t a, const fmpz_t mod, const nf_t nf, int sign);
0294 void nf_elem_mod_fmpz(nf_elem_t res, const nf_elem_t a, const fmpz_t mod, const nf_t nf);
0295
0296 void nf_elem_smod_fmpz_den(nf_elem_t res, const nf_elem_t a, const fmpz_t mod, const nf_t nf, int den);
0297
0298 void nf_elem_smod_fmpz(nf_elem_t res, const nf_elem_t a, const fmpz_t mod, const nf_t nf);
0299
0300 void nf_elem_coprime_den(nf_elem_t res, const nf_elem_t a, const fmpz_t mod, const nf_t nf);
0301 void nf_elem_coprime_den_signed(nf_elem_t res, const nf_elem_t a, const fmpz_t mod, const nf_t nf);
0302
0303 #ifdef __cplusplus
0304 }
0305 #endif
0306
0307 #endif