include/flint/fmpz.h

0001 /*
0002     Copyright (C) 2009 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 FMPZ_H
0013 #define FMPZ_H
0014
0015 #ifdef FMPZ_INLINES_C
0016 #define FMPZ_INLINE
0017 #else
0018 #define FMPZ_INLINE static inline
0019 #endif
0020
0021 #include "fmpz_types.h"
0022
0023 #ifdef __cplusplus
0024 extern "C" {
0025 #endif
0026
0027 /* Memory management *********************************************************/
0028
0029 #if defined(__GMP_H__)
0030 mpz_ptr _fmpz_new_mpz(void);
0031
0032 mpz_ptr _fmpz_promote(fmpz_t f);
0033 mpz_ptr _fmpz_promote_val(fmpz_t f);
0034
0035 void _fmpz_init_readonly_mpz(fmpz_t f, const mpz_t z);
0036 void flint_mpz_init_set_readonly(mpz_t z, const fmpz_t f);
0037 void fmpz_init_set_readonly(fmpz_t f, const mpz_t z);
0038
0039 void flint_mpz_clear_readonly(mpz_t z);
0040 void _fmpz_clear_readonly_mpz(mpz_t z);
0041 #endif
0042
0043 void _fmpz_clear_mpz(fmpz f);
0044 void _fmpz_cleanup_mpz_content(void);
0045 void _fmpz_cleanup(void);
0046
0047 FMPZ_INLINE
0048 void _fmpz_demote(fmpz_t f)
0049 {
0050     if (COEFF_IS_MPZ(*f))
0051     {
0052         _fmpz_clear_mpz(*f);
0053         (*f) = WORD(0);
0054     }
0055 }
0056
0057 void _fmpz_demote_val(fmpz_t f);
0058
0059 FMPZ_INLINE void fmpz_init(fmpz_t f) { *f = WORD(0); }
0060 FMPZ_INLINE void fmpz_clear(fmpz_t f) { if (COEFF_IS_MPZ(*f)) _fmpz_clear_mpz(*f); }
0061
0062 void fmpz_init2(fmpz_t f, ulong limbs);
0063
0064 void _fmpz_promote_set_ui(fmpz_t f, ulong v);
0065 void _fmpz_promote_set_si(fmpz_t f, slong v);
0066 void _fmpz_promote_neg_ui(fmpz_t f, ulong v);
0067 void _fmpz_promote_set_uiui(fmpz_t f, ulong hi, ulong lo);
0068 void _fmpz_promote_neg_uiui(fmpz_t f, ulong hi, ulong lo);
0069 void _fmpz_init_promote_set_ui(fmpz_t f, ulong v);
0070 void _fmpz_init_promote_set_si(fmpz_t f, slong v);
0071
0072 void fmpz_set(fmpz_t f, const fmpz_t g);
0073
0074 FMPZ_INLINE
0075 void fmpz_init_set(fmpz_t f, const fmpz_t g)
0076 {
0077     if (!COEFF_IS_MPZ(*g))
0078     {
0079         *f = *g;
0080     }
0081     else
0082     {
0083         *f = 0;
0084         fmpz_set(f, g);
0085     }
0086 }
0087
0088 FMPZ_INLINE
0089 void fmpz_init_set_ui(fmpz_t f, ulong g)
0090 {
0091     if (g <= COEFF_MAX)
0092         *f = g;
0093     else
0094         _fmpz_init_promote_set_ui(f, g);
0095 }
0096
0097 FMPZ_INLINE
0098 void fmpz_init_set_si(fmpz_t f, slong g)
0099 {
0100     if (COEFF_MIN <= g && g <= COEFF_MAX)
0101         *f = g;
0102     else
0103         _fmpz_init_promote_set_si(f, g);
0104 }
0105
0106 void fmpz_clear_readonly(fmpz_t f);
0107
0108 int _fmpz_is_canonical(const fmpz_t x);
0109
0110 /* Randomisation *************************************************************/
0111
0112 void fmpz_randbits_unsigned(fmpz_t f, flint_rand_t state, flint_bitcnt_t bits);
0113 void fmpz_randbits(fmpz_t f, flint_rand_t state, flint_bitcnt_t bits);
0114 void fmpz_randm(fmpz_t f, flint_rand_t state, const fmpz_t m);
0115 void fmpz_randtest(fmpz_t f, flint_rand_t state, flint_bitcnt_t bits);
0116 void fmpz_randtest_unsigned(fmpz_t f, flint_rand_t state, flint_bitcnt_t bits);
0117 void fmpz_randtest_not_zero(fmpz_t f, flint_rand_t state, flint_bitcnt_t bits);
0118 void fmpz_randtest_mod(fmpz_t f, flint_rand_t state, const fmpz_t m);
0119 void fmpz_randtest_mod_signed(fmpz_t f, flint_rand_t state, const fmpz_t m);
0120 void fmpz_randprime(fmpz_t f, flint_rand_t state, flint_bitcnt_t bits, int proved);
0121
0122 /* Assignments and conversions ***********************************************/
0123
0124 FMPZ_INLINE
0125 void fmpz_zero(fmpz_t f)
0126 {
0127     if (COEFF_IS_MPZ(*f))
0128         _fmpz_clear_mpz(*f);
0129     *f = WORD(0);
0130 }
0131
0132 FMPZ_INLINE
0133 void fmpz_one(fmpz_t f)
0134 {
0135     if (COEFF_IS_MPZ(*f))
0136         _fmpz_clear_mpz(*f);
0137     *f = WORD(1);
0138 }
0139
0140 FMPZ_INLINE void fmpz_swap(fmpz_t f, fmpz_t g) { FLINT_SWAP(fmpz, *f, *g); }
0141
0142 slong fmpz_get_si(const fmpz_t f);
0143 ulong fmpz_get_ui(const fmpz_t f);
0144
0145 FMPZ_INLINE void
0146 fmpz_set_si(fmpz_t f, slong val)
0147 {
0148     if (val >= COEFF_MIN && val <= COEFF_MAX)
0149     {
0150         if (COEFF_IS_MPZ(*f))
0151             _fmpz_clear_mpz(*f);
0152         *f = val;
0153     }
0154     else
0155         _fmpz_promote_set_si(f, val);
0156 }
0157
0158 FMPZ_INLINE void
0159 fmpz_set_ui(fmpz_t f, ulong val)
0160 {
0161     if (val <= COEFF_MAX)
0162     {
0163         if (COEFF_IS_MPZ(*f))
0164             _fmpz_clear_mpz(*f);
0165         *f = val;
0166     }
0167     else
0168         _fmpz_promote_set_ui(f, val);
0169 }
0170
0171 FMPZ_INLINE void
0172 fmpz_neg_ui(fmpz_t f, ulong val)
0173 {
0174     if (val <= COEFF_MAX)
0175     {
0176         if (COEFF_IS_MPZ(*f))
0177             _fmpz_clear_mpz(*f);
0178         *f = -(slong) val;
0179     }
0180     else
0181         _fmpz_promote_neg_ui(f, val);
0182 }
0183
0184 FMPZ_INLINE void fmpz_get_uiui(ulong * hi, ulong * low, const fmpz_t f)
0185 {
0186     if (!COEFF_IS_MPZ(*f))
0187     {
0188         *low = *f;
0189         *hi  = 0;
0190     }
0191     else
0192     {
0193         zz_srcptr zf = FMPZ_TO_ZZ(*f);
0194         *low = zf->ptr[0];
0195         *hi  = zf->size == 2 ? zf->ptr[1] : 0;
0196     }
0197 }
0198
0199 FMPZ_INLINE void fmpz_set_uiui(fmpz_t f, ulong hi, ulong lo)
0200 {
0201     if (hi == 0)
0202         fmpz_set_ui(f, lo);
0203     else
0204         _fmpz_promote_set_uiui(f, hi, lo);
0205 }
0206
0207 FMPZ_INLINE void fmpz_neg_uiui(fmpz_t f, ulong hi, ulong lo)
0208 {
0209     if (hi == 0)
0210         fmpz_neg_ui(f, lo);
0211     else
0212         _fmpz_promote_neg_uiui(f, hi, lo);
0213 }
0214
0215 void fmpz_get_signed_uiui(ulong * hi, ulong * lo, const fmpz_t x);
0216
0217 FMPZ_INLINE void
0218 fmpz_set_signed_uiui(fmpz_t r, ulong hi, ulong lo)
0219 {
0220     if (((slong) hi) < 0)
0221     {
0222         hi = -hi - (lo != 0);
0223         lo = -lo;
0224         fmpz_neg_uiui(r, hi, lo);
0225     }
0226     else
0227     {
0228         fmpz_set_uiui(r, hi, lo);
0229     }
0230 }
0231
0232 void fmpz_set_signed_uiuiui(fmpz_t r, ulong hi, ulong mid, ulong lo);
0233
0234 void fmpz_get_ui_array(ulong * out, slong n, const fmpz_t in);
0235 void fmpz_set_ui_array(fmpz_t out, const ulong * in, slong n);
0236
0237 void fmpz_get_signed_ui_array(ulong * out, slong n, const fmpz_t in);
0238 void fmpz_set_signed_ui_array(fmpz_t out, const ulong * in, slong n);
0239
0240 void fmpz_set_mpn_large(fmpz_t z, nn_srcptr src, slong n, int negative);
0241
0242 ulong fmpz_get_nmod(const fmpz_t f, nmod_t mod);
0243
0244 double fmpz_get_d(const fmpz_t f);
0245 void fmpz_set_d(fmpz_t f, double c);
0246
0247 #if defined(__GMP_H__)
0248 void fmpz_get_mpz(mpz_t x, const fmpz_t f);
0249 void fmpz_set_mpz(fmpz_t f, const mpz_t x);
0250
0251 void fmpz_get_mpf(mpf_t x, const fmpz_t f);
0252 void fmpz_set_mpf(fmpz_t f, const mpf_t x);
0253 #endif
0254
0255 #ifdef __MPFR_H
0256 void fmpz_get_mpfr(mpfr_t x, const fmpz_t f, mpfr_rnd_t rnd);
0257 #endif
0258
0259 int fmpz_get_mpn(nn_ptr * n, fmpz_t n_in);
0260
0261 /* Comparisons ***************************************************************/
0262
0263 FMPZ_INLINE int fmpz_is_zero(const fmpz_t f) { return (*f == 0); }
0264 FMPZ_INLINE int fmpz_is_one(const fmpz_t f) { return (*f == 1); }
0265 FMPZ_INLINE int fmpz_is_pm1(const fmpz_t f) { return (*f == 1 || *f == -1); }
0266
0267 int fmpz_equal(const fmpz_t f, const fmpz_t g);
0268 int fmpz_equal_si(const fmpz_t f, slong g);
0269 int fmpz_equal_ui(const fmpz_t f, ulong g);
0270
0271 int fmpz_cmp(const fmpz_t f, const fmpz_t g);
0272 int fmpz_cmp_ui(const fmpz_t f, ulong g);
0273 int fmpz_cmp_si(const fmpz_t f, slong g);
0274
0275 int fmpz_cmpabs(const fmpz_t f, const fmpz_t g);
0276 int fmpz_cmp2abs(const fmpz_t f, const fmpz_t g);
0277
0278 /* Basic properties and manipulation *****************************************/
0279
0280 FMPZ_INLINE
0281 int fmpz_is_even(const fmpz_t f)
0282 {
0283     if (!COEFF_IS_MPZ(*f))
0284         return !((*f) & WORD(1));
0285     else
0286         return !(FMPZ_TO_ZZ(*f)->ptr[0] & 1);
0287 }
0288
0289 FMPZ_INLINE
0290 int fmpz_is_odd(const fmpz_t f)
0291 {
0292     if (!COEFF_IS_MPZ(*f))
0293         return ((*f) & WORD(1));
0294     else
0295         return (FMPZ_TO_ZZ(*f)->ptr[0] & 1);
0296 }
0297
0298 int fmpz_sgn(const fmpz_t f);
0299
0300 int fmpz_abs_fits_ui(const fmpz_t f);
0301 int fmpz_fits_si(const fmpz_t f);
0302
0303 size_t fmpz_sizeinbase(const fmpz_t f, int b);
0304 slong fmpz_size(const fmpz_t f);
0305 flint_bitcnt_t fmpz_bits(const fmpz_t f);
0306 flint_bitcnt_t fmpz_val2(const fmpz_t x);
0307
0308 int fmpz_is_square(const fmpz_t f);
0309 int fmpz_is_perfect_power(fmpz_t root, const fmpz_t f);
0310
0311 ulong fmpz_abs_ubound_ui_2exp(slong * exp, const fmpz_t x, int bits);
0312 ulong fmpz_abs_lbound_ui_2exp(slong * exp, const fmpz_t x, int bits);
0313
0314 /* I/O ***********************************************************************/
0315
0316 int fmpz_read(fmpz_t f);
0317 int fmpz_print(const fmpz_t x);
0318
0319 int fmpz_set_str(fmpz_t f, const char * str, int b);
0320 char * fmpz_get_str(char * str, int b, const fmpz_t f);
0321
0322 #ifdef FLINT_HAVE_FILE
0323 int fmpz_fread(FILE * file, fmpz_t f);
0324 int fmpz_fprint(FILE * file, const fmpz_t x);
0325
0326 size_t fmpz_inp_raw(fmpz_t x, FILE * fin);
0327 size_t fmpz_out_raw(FILE * fout, const fmpz_t x);
0328 #endif
0329
0330 /* Basic arithmetic **********************************************************/
0331
0332 void fmpz_add(fmpz_t f, const fmpz_t g, const fmpz_t h);
0333 void fmpz_add_ui(fmpz_t f, const fmpz_t g, ulong x);
0334
0335 void fmpz_sub(fmpz_t f, const fmpz_t g, const fmpz_t h);
0336 void fmpz_sub_ui(fmpz_t f, const fmpz_t g, ulong x);
0337
0338 FMPZ_INLINE void fmpz_add_si(fmpz_t f, const fmpz_t g, slong x)
0339 {
0340     if (x >= 0)
0341         fmpz_add_ui(f, g, (ulong) x);
0342     else
0343         fmpz_sub_ui(f, g, -(ulong) x);
0344 }
0345
0346 FMPZ_INLINE void fmpz_sub_si(fmpz_t f, const fmpz_t g, slong x)
0347 {
0348     if (x >= 0)
0349         fmpz_sub_ui(f, g, (ulong) x);
0350     else
0351         fmpz_add_ui(f, g, -(ulong) x);
0352 }
0353
0354 void fmpz_abs(fmpz_t f1, const fmpz_t f2);
0355 void fmpz_neg(fmpz_t f1, const fmpz_t f2);
0356
0357 void fmpz_mul_ui(fmpz_t f, const fmpz_t g, ulong x);
0358 void fmpz_mul_si(fmpz_t f, const fmpz_t g, slong x);
0359 void fmpz_mul(fmpz_t f, const fmpz_t g, const fmpz_t h);
0360
0361 void fmpz_mul2_uiui(fmpz_t f, const fmpz_t g, ulong h1, ulong h2);
0362
0363 void fmpz_mul_2exp(fmpz_t f, const fmpz_t g, ulong exp);
0364 void fmpz_one_2exp(fmpz_t f, ulong exp);
0365
0366 void fmpz_addmul(fmpz_t f, const fmpz_t g, const fmpz_t h);
0367 void fmpz_addmul_si(fmpz_t f, const fmpz_t g, slong x);
0368 void fmpz_addmul_ui(fmpz_t f, const fmpz_t g, ulong x);
0369
0370 void fmpz_submul(fmpz_t f, const fmpz_t g, const fmpz_t h);
0371 void fmpz_submul_si(fmpz_t f, const fmpz_t g, slong x);
0372 void fmpz_submul_ui(fmpz_t f, const fmpz_t g, ulong x);
0373
0374 void fmpz_fmma(fmpz_t f, const fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_t d);
0375 void fmpz_fmms(fmpz_t f, const fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_t d);
0376
0377 void fmpz_pow_ui(fmpz_t f, const fmpz_t g, ulong exp);
0378 void fmpz_ui_pow_ui(fmpz_t x, ulong b, ulong e);
0379 int fmpz_pow_fmpz(fmpz_t a, const fmpz_t b, const fmpz_t e);
0380
0381 void fmpz_sqrt(fmpz_t f, const fmpz_t g);
0382 void fmpz_sqrtrem(fmpz_t f, fmpz_t r, const fmpz_t g);
0383
0384 int fmpz_root(fmpz_t r, const fmpz_t f, slong n);
0385
0386 int fmpz_divisible(const fmpz_t f, const fmpz_t g);
0387 int fmpz_divisible_ui(const fmpz_t f, ulong g);
0388 FMPZ_INLINE int fmpz_divisible_si(const fmpz_t f, slong g) { return fmpz_divisible_ui(f, FLINT_UABS(g)); }
0389 int fmpz_divides(fmpz_t q, const fmpz_t g, const fmpz_t h);
0390
0391 void fmpz_divexact(fmpz_t f, const fmpz_t g, const fmpz_t h);
0392 void fmpz_divexact_ui(fmpz_t f, const fmpz_t g, ulong h);
0393 void fmpz_divexact_si(fmpz_t f, const fmpz_t g, slong h);
0394
0395 void fmpz_divexact2_uiui(fmpz_t f, const fmpz_t g, ulong h1, ulong h2);
0396
0397 void fmpz_cdiv_qr(fmpz_t f, fmpz_t s, const fmpz_t g, const fmpz_t h);
0398 void fmpz_fdiv_qr(fmpz_t f, fmpz_t s, const fmpz_t g, const fmpz_t h);
0399 void fmpz_tdiv_qr(fmpz_t f, fmpz_t s, const fmpz_t g, const fmpz_t h);
0400 void fmpz_ndiv_qr(fmpz_t q, fmpz_t r, const fmpz_t a, const fmpz_t b);
0401
0402 void fmpz_cdiv_r_2exp(fmpz_t f, const fmpz_t g, ulong exp);
0403 void fmpz_fdiv_r_2exp(fmpz_t f, const fmpz_t g, ulong exp);
0404 void fmpz_tdiv_r_2exp(fmpz_t f, const fmpz_t g, ulong exp);
0405
0406 void fmpz_cdiv_q_2exp(fmpz_t f, const fmpz_t g, ulong exp);
0407 void fmpz_fdiv_q_2exp(fmpz_t f, const fmpz_t g, ulong exp);
0408 void fmpz_tdiv_q_2exp(fmpz_t f, const fmpz_t g, ulong exp);
0409
0410 ulong fmpz_cdiv_ui(const fmpz_t g, ulong h);
0411 ulong fmpz_fdiv_ui(const fmpz_t g, ulong h);
0412 ulong fmpz_tdiv_ui(const fmpz_t g, ulong h);
0413
0414 void fmpz_cdiv_q(fmpz_t f, const fmpz_t g, const fmpz_t h);
0415 void fmpz_fdiv_q(fmpz_t f, const fmpz_t g, const fmpz_t h);
0416 void fmpz_tdiv_q(fmpz_t f, const fmpz_t g, const fmpz_t h);
0417
0418 void fmpz_fdiv_r(fmpz_t f, const fmpz_t g, const fmpz_t h);
0419
0420 void fmpz_cdiv_q_ui(fmpz_t f, const fmpz_t g, ulong h);
0421 void fmpz_fdiv_q_ui(fmpz_t f, const fmpz_t g, ulong h);
0422 void fmpz_tdiv_q_ui(fmpz_t f, const fmpz_t g, ulong h);
0423
0424 void fmpz_cdiv_q_si(fmpz_t f, const fmpz_t g, slong h);
0425 void fmpz_fdiv_q_si(fmpz_t f, const fmpz_t g, slong h);
0426 void fmpz_tdiv_q_si(fmpz_t f, const fmpz_t g, slong h);
0427
0428 void fmpz_mul_tdiv_q_2exp(fmpz_t f, const fmpz_t g, const fmpz_t h, ulong exp);
0429
0430 void fmpz_mul_si_tdiv_q_2exp(fmpz_t f, const fmpz_t g, slong x, ulong exp);
0431
0432 double fmpz_dlog(const fmpz_t x);
0433
0434 slong fmpz_clog(const fmpz_t x, const fmpz_t b);
0435 slong fmpz_flog(const fmpz_t x, const fmpz_t b);
0436
0437 slong fmpz_clog_ui(const fmpz_t x, ulong b);
0438 slong fmpz_flog_ui(const fmpz_t x, ulong b);
0439
0440 double fmpz_get_d_2exp(slong * exp, const fmpz_t f);
0441 void fmpz_set_d_2exp(fmpz_t f, double m, slong exp);
0442
0443 #if FLINT_HAVE_FFT_SMALL
0444 #define MPZ_WANT_FLINT_DIVISION(a, b) (mpz_size(b) >= 1250 && mpz_size(a) - mpz_size(b) >= 1250)
0445 #else
0446 #define MPZ_WANT_FLINT_DIVISION(a, b) 0
0447 #endif
0448
0449 void _fmpz_tdiv_q_newton(fmpz_t q, const fmpz_t a, const fmpz_t b);
0450 void _fmpz_fdiv_q_newton(fmpz_t q, const fmpz_t a, const fmpz_t b);
0451 void _fmpz_cdiv_q_newton(fmpz_t q, const fmpz_t a, const fmpz_t b);
0452 void _fmpz_tdiv_qr_newton(fmpz_t q, fmpz_t r, const fmpz_t a, const fmpz_t b);
0453 void _fmpz_fdiv_qr_newton(fmpz_t q, fmpz_t r, const fmpz_t a, const fmpz_t b);
0454 void _fmpz_cdiv_qr_newton(fmpz_t q, fmpz_t r, const fmpz_t a, const fmpz_t b);
0455 void _fmpz_tdiv_r_newton(fmpz_t r, const fmpz_t a, const fmpz_t b);
0456 void _fmpz_fdiv_r_newton(fmpz_t r, const fmpz_t a, const fmpz_t b);
0457 void _fmpz_cdiv_r_newton(fmpz_t r, const fmpz_t a, const fmpz_t b);
0458 void _fmpz_mod_newton(fmpz_t r, const fmpz_t a, const fmpz_t b);
0459 void _fmpz_divexact_newton(fmpz_t q, const fmpz_t a, const fmpz_t b);
0460
0461 /* Bitwise operations ********************************************************/
0462
0463 void fmpz_setbit(fmpz_t f, ulong i);
0464 void fmpz_clrbit(fmpz_t f, ulong i);
0465 int fmpz_tstbit(const fmpz_t f, ulong i);
0466
0467 void fmpz_complement(fmpz_t r, const fmpz_t f);
0468
0469 void fmpz_combit(fmpz_t f, ulong i);
0470
0471 void fmpz_and(fmpz_t r, const fmpz_t a, const fmpz_t b);
0472 void fmpz_or(fmpz_t r, const fmpz_t a, const fmpz_t b);
0473 void fmpz_xor(fmpz_t r, const fmpz_t a, const fmpz_t b);
0474
0475 flint_bitcnt_t fmpz_popcnt(const fmpz_t c);
0476
0477 /* Bit packing ***************************************************************/
0478
0479 int fmpz_bit_pack(nn_ptr arr, flint_bitcnt_t shift, flint_bitcnt_t bits, const fmpz_t coeff, int negate, int borrow);
0480 int fmpz_bit_unpack(fmpz_t coeff, nn_srcptr arr, flint_bitcnt_t shift, flint_bitcnt_t bits, int negate, int borrow);
0481 void fmpz_bit_unpack_unsigned(fmpz_t coeff, nn_srcptr arr, flint_bitcnt_t shift, flint_bitcnt_t bits);
0482
0483 /* Modular arithmetic ********************************************************/
0484
0485 FMPZ_INLINE ulong
0486 fmpz_mod_ui(fmpz_t f, const fmpz_t g, ulong h)
0487 {
0488     h = fmpz_fdiv_ui(g, h);
0489     fmpz_set_ui(f, h);
0490     return h;
0491 }
0492
0493 FMPZ_INLINE void fmpz_set_ui_smod(fmpz_t f, ulong x, ulong m)
0494 {
0495     if (x <= m / 2)
0496         fmpz_set_ui(f, x);
0497     else
0498         fmpz_set_si(f, x - m);
0499 }
0500
0501 void fmpz_mod(fmpz_t f, const fmpz_t g, const fmpz_t h);
0502 void fmpz_smod(fmpz_t f, const fmpz_t g, const fmpz_t h);
0503 void _fmpz_smod(fmpz_t r, const fmpz_t a, const fmpz_t m, int sign, fmpz_t t);
0504
0505 FMPZ_INLINE void
0506 fmpz_negmod(fmpz_t r, const fmpz_t a, const fmpz_t mod)
0507 {
0508    if (fmpz_is_zero(a))
0509       fmpz_zero(r);
0510    else
0511       fmpz_sub(r, mod, a);
0512 }
0513
0514 int fmpz_invmod(fmpz_t f, const fmpz_t g, const fmpz_t h);
0515 int fmpz_sqrtmod(fmpz_t b, const fmpz_t a, const fmpz_t p);
0516
0517 void fmpz_powm_ui(fmpz_t f, const fmpz_t g, ulong exp, const fmpz_t m);
0518 void fmpz_powm(fmpz_t f, const fmpz_t g, const fmpz_t e, const fmpz_t m);
0519
0520 void fmpz_divides_mod_list(fmpz_t xstart, fmpz_t xstride, fmpz_t xlength, const fmpz_t a, const fmpz_t b, const fmpz_t n);
0521
0522 slong _fmpz_remove(fmpz_t x, const fmpz_t f, double finv);
0523 slong fmpz_remove(fmpz_t rop, const fmpz_t op, const fmpz_t f);
0524
0525 /* GCD and LCM ***************************************************************/
0526
0527 void fmpz_gcd(fmpz_t f, const fmpz_t g, const fmpz_t h);
0528 void fmpz_gcd_ui(fmpz_t res, const fmpz_t a, ulong b);
0529 void fmpz_gcd3(fmpz_t f, const fmpz_t a, const fmpz_t b, const fmpz_t c);
0530
0531 void fmpz_gcdinv(fmpz_t d, fmpz_t a, const fmpz_t f, const fmpz_t g);
0532 void fmpz_xgcd(fmpz_t d, fmpz_t a, fmpz_t b, const fmpz_t f, const fmpz_t g);
0533 void fmpz_xgcd_canonical_bezout(fmpz_t d, fmpz_t a, fmpz_t b, const fmpz_t f, const fmpz_t g);
0534 void fmpz_xgcd_partial(fmpz_t co2, fmpz_t co1, fmpz_t r2, fmpz_t r1, const fmpz_t L);
0535
0536 void fmpz_lcm(fmpz_t f, const fmpz_t g, const fmpz_t h);
0537
0538 /* preinvn *******************************************************************/
0539
0540 void fmpz_fdiv_qr_preinvn(fmpz_t f, fmpz_t s, const fmpz_t g, const fmpz_t h, const fmpz_preinvn_t inv);
0541 void fmpz_fdiv_r_preinvn(fmpz_t f, const fmpz_t g, const fmpz_t h, const fmpz_preinvn_t inv);
0542
0543 void fmpz_preinvn_init(fmpz_preinvn_t inv, const fmpz_t f);
0544 void fmpz_preinvn_clear(fmpz_preinvn_t inv);
0545
0546 /* Combinatorics functions ***************************************************/
0547
0548 void fmpz_fac_ui(fmpz_t f, ulong n);
0549 void fmpz_bin_uiui(fmpz_t res, ulong n, ulong k);
0550
0551 void _fmpz_rfac_ui(fmpz_t r, const fmpz_t x, ulong a, ulong b);
0552 void fmpz_rfac_ui(fmpz_t r, const fmpz_t x, ulong n);
0553 void fmpz_rfac_uiui(fmpz_t r, ulong x, ulong n);
0554
0555 /* Number theoretic functions ************************************************/
0556
0557 int fmpz_jacobi(const fmpz_t a, const fmpz_t p);
0558 int fmpz_kronecker(const fmpz_t a, const fmpz_t n);
0559
0560 void fmpz_fib_ui(fmpz_t f, ulong n);
0561
0562 /* crt ***********************************************************************/
0563
0564 void _fmpz_CRT_ui_precomp(fmpz_t out, const fmpz_t r1, const fmpz_t m1, ulong r2, ulong m2, ulong m2inv, const fmpz_t m1m2, ulong c, int sign);
0565 void fmpz_CRT_ui(fmpz_t out, const fmpz_t r1, const fmpz_t m1, ulong r2, ulong m2, int sign);
0566 void fmpz_CRT(fmpz_t out, const fmpz_t r1, const fmpz_t m1, const fmpz_t r2, const fmpz_t m2, int sign);
0567
0568 /* multi CRT *****************************************************************/
0569
0570 typedef struct
0571 {
0572     slong a_idx; /* index of A */
0573     slong b_idx; /* index of B */
0574     slong c_idx; /* index of C */
0575     fmpz_t b_modulus;
0576     fmpz_t c_modulus;
0577 } _fmpz_multi_CRT_instr;
0578
0579 typedef struct
0580 {
0581     _fmpz_multi_CRT_instr * prog; /* straight line program */
0582     fmpz * moduli, * fracmoduli;
0583     fmpz_t final_modulus;
0584     slong moduli_count;
0585     flint_bitcnt_t min_modulus_bits;
0586     slong length; /* length of prog */
0587     slong alloc;  /* alloc of prog */
0588     slong localsize; /* length of outputs required in fmpz_multi_CRT_run */
0589     slong temp1loc, temp2loc, temp3loc, temp4loc;
0590     int good;   /* the moduli are good for CRT, essentially relatively prime */
0591 } fmpz_multi_CRT_struct;
0592
0593 typedef fmpz_multi_CRT_struct fmpz_multi_CRT_t[1];
0594
0595 void fmpz_multi_CRT_init(fmpz_multi_CRT_t CRT);
0596 void fmpz_multi_CRT_clear(fmpz_multi_CRT_t P);
0597
0598 void _fmpz_multi_CRT_precomp(fmpz * outputs, const fmpz_multi_CRT_t P, const fmpz * inputs, int sign);
0599 void fmpz_multi_CRT_precomp(fmpz_t output, const fmpz_multi_CRT_t P, const fmpz * inputs, int sign);
0600 int fmpz_multi_CRT_precompute(fmpz_multi_CRT_t CRT, const fmpz * moduli, slong len);
0601 int fmpz_multi_CRT(fmpz_t output, const fmpz * moduli, const fmpz * values, slong len, int sign);
0602
0603 /* multi mod *****************************************************************/
0604
0605 typedef struct
0606 {
0607     slong in_idx;
0608     slong out_idx;
0609     fmpz_t modulus;
0610 } _fmpz_multi_mod_instr;
0611
0612 typedef struct
0613 {
0614     _fmpz_multi_mod_instr * prog; /* straight line program */
0615     fmpz * moduli;
0616     slong moduli_count;
0617     flint_bitcnt_t min_modulus_bits;
0618     slong length; /* length of prog */
0619     slong alloc;  /* alloc of prog */
0620     slong localsize; /* length of tmp required in _fmpz_multi_mod_precomp */
0621     slong temp1loc;
0622     int good;   /* the moduli are good for MOD, none are zero */
0623 } fmpz_multi_mod_struct;
0624
0625 typedef fmpz_multi_mod_struct fmpz_multi_mod_t[1];
0626
0627
0628 void fmpz_multi_mod_init(fmpz_multi_mod_t P);
0629 void fmpz_multi_mod_clear(fmpz_multi_mod_t P);
0630
0631 int fmpz_multi_mod_precompute(fmpz_multi_mod_t P, const fmpz * f, slong r);
0632
0633 void _fmpz_multi_mod_precomp(fmpz * outputs, const fmpz_multi_mod_t P, const fmpz_t input, int sign, fmpz * tmp);
0634 void fmpz_multi_mod_precomp(fmpz * outputs, const fmpz_multi_mod_t P, const fmpz_t input, int sign);
0635
0636 /* multi mod/multi CRT ui ****************************************************/
0637
0638 typedef struct {
0639     nmod_t mod;
0640     ulong i0, i1, i2;
0641 } crt_lut_entry;
0642
0643 typedef struct {
0644     nmod_t mod;
0645     nmod_t mod0, mod1, mod2;
0646 } mod_lut_entry;
0647
0648 typedef struct {
0649     fmpz_multi_CRT_t crt_P;
0650     fmpz_multi_mod_t mod_P;
0651     ulong * packed_multipliers;
0652     slong * step;
0653     slong * crt_offsets;
0654     slong crt_offsets_alloc;
0655     slong * mod_offsets;
0656     slong mod_offsets_alloc;
0657     crt_lut_entry * crt_lu;
0658     slong crt_lu_alloc;
0659     slong crt_klen;
0660     mod_lut_entry * mod_lu;
0661     slong mod_lu_alloc;
0662     slong mod_klen;
0663     slong num_primes;
0664 } fmpz_comb_struct;
0665
0666 typedef fmpz_comb_struct fmpz_comb_t[1];
0667
0668 typedef struct {
0669     slong Alen, Tlen;
0670     fmpz * A, * T;
0671 } fmpz_comb_temp_struct;
0672
0673 typedef fmpz_comb_temp_struct fmpz_comb_temp_t[1];
0674
0675 void fmpz_comb_temp_init(fmpz_comb_temp_t CT, const fmpz_comb_t C);
0676 void fmpz_comb_temp_clear(fmpz_comb_temp_t CT);
0677
0678 void fmpz_comb_init(fmpz_comb_t C, nn_srcptr primes, slong num_primes);
0679 void fmpz_comb_clear(fmpz_comb_t C);
0680
0681 void fmpz_multi_mod_ui(ulong * out, const fmpz_t in, const fmpz_comb_t C, fmpz_comb_temp_t CT);
0682 void fmpz_multi_CRT_ui(fmpz_t output, nn_srcptr residues, const fmpz_comb_t comb, fmpz_comb_temp_t temp, int sign);
0683
0684 /*****************************************************************************/
0685
0686 void fmpz_lucas_chain(fmpz_t Vm, fmpz_t Vm1, const fmpz_t A, const fmpz_t m, const fmpz_t n);
0687 void fmpz_lucas_chain_full(fmpz_t Vm, fmpz_t Vm1, const fmpz_t A, const fmpz_t B, const fmpz_t m, const fmpz_t n);
0688 void fmpz_lucas_chain_double(fmpz_t U2m, fmpz_t U2m1, const fmpz_t Um, const fmpz_t Um1, const fmpz_t A, const fmpz_t B, const fmpz_t n);
0689
0690 void fmpz_lucas_chain_add(fmpz_t Umn, fmpz_t Umn1, const fmpz_t Um, const fmpz_t Um1, const fmpz_t Un, const fmpz_t Un1, const fmpz_t A, const fmpz_t B, const fmpz_t n);
0691 void fmpz_lucas_chain_mul(fmpz_t Ukm, fmpz_t Ukm1, const fmpz_t Um, const fmpz_t Um1, const fmpz_t A, const fmpz_t B, const fmpz_t k, const fmpz_t n);
0692 void fmpz_lucas_chain_VtoU(fmpz_t Um, fmpz_t Um1, const fmpz_t Vm, const fmpz_t Vm1, const fmpz_t A, const fmpz_t FLINT_UNUSED(B), const fmpz_t Dinv, const fmpz_t n);
0693
0694 int fmpz_is_probabprime_lucas(const fmpz_t n);
0695 int fmpz_is_probabprime_BPSW(const fmpz_t n);
0696 int fmpz_is_probabprime(const fmpz_t p);
0697 int fmpz_is_strong_probabprime(const fmpz_t n, const fmpz_t a);
0698
0699 int fmpz_is_prime_pseudosquare(const fmpz_t n);
0700 int fmpz_is_prime_pocklington(fmpz_t F, fmpz_t R, const fmpz_t n, nn_ptr pm1, slong num_pm1);
0701 int fmpz_is_prime_morrison(fmpz_t F, fmpz_t R, const fmpz_t n, nn_ptr pm1, slong num_pm1);
0702 int fmpz_is_prime(const fmpz_t p);
0703
0704 void fmpz_nextprime(fmpz_t res, const fmpz_t n, int proved);
0705
0706 void _fmpz_nm1_trial_factors(const fmpz_t n, nn_ptr pm1, slong * num_pm1, ulong limit);
0707 void _fmpz_np1_trial_factors(const fmpz_t n, nn_ptr pp1, slong * num_pp1, ulong limit);
0708
0709 int fmpz_divisor_in_residue_class_lenstra(fmpz_t fac, const fmpz_t n, const fmpz_t r, const fmpz_t s);
0710
0711 /* Primorial *****************************************************************/
0712
0713 void fmpz_primorial(fmpz_t res, ulong n);
0714
0715 /* Multiplicative functions **************************************************/
0716
0717 void fmpz_euler_phi(fmpz_t res, const fmpz_t n);
0718
0719 int fmpz_moebius_mu(const fmpz_t n);
0720
0721 void fmpz_divisor_sigma(fmpz_t res, ulong k, const fmpz_t n);
0722
0723 #ifdef __cplusplus
0724 }
0725 #endif
0726
0727 #endif