include/flint/fmpz_mod.h

0001 /*
0002     Copyright (C) 2017 - 2021 Daniel Schultz
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_MOD_H
0013 #define FMPZ_MOD_H
0014
0015 #ifdef FMPZ_MOD_INLINES_C
0016 #define FMPZ_MOD_INLINE
0017 #else
0018 #define FMPZ_MOD_INLINE static inline
0019 #endif
0020
0021 #include "fmpz_mod_types.h"
0022
0023 #ifdef __cplusplus
0024 extern "C" {
0025 #endif
0026
0027 /* all of the data we need to do arithmetic mod n ****************************/
0028
0029 /*
0030     Currently operations are special cased according to
0031         if      n < 2^FLINT_BITS     -> add1, sub1, mul1 using nmod
0032         else if n = 2^FLINT_BITS     -> add2s, sub2s, mul2s
0033         else if n < 2^(2*FLINT_BITS) -> add2, sub2, mul2
0034         else                         -> addN, subN, mulN
0035
0036     A special case for the multiplication for 3-word shows no signs of
0037     diminishing returns, but it is not implemented currently.
0038 */
0039
0040 void fmpz_mod_ctx_init(fmpz_mod_ctx_t ctx, const fmpz_t n);
0041 void fmpz_mod_ctx_init_ui(fmpz_mod_ctx_t ctx, ulong n);
0042 void fmpz_mod_ctx_init_rand_bits(fmpz_mod_ctx_t ctx, flint_rand_t state, flint_bitcnt_t max_bits);
0043 void fmpz_mod_ctx_init_rand_bits_prime(fmpz_mod_ctx_t ctx, flint_rand_t state, flint_bitcnt_t max_bits);
0044
0045 void fmpz_mod_ctx_clear(fmpz_mod_ctx_t ctx);
0046
0047 FMPZ_MOD_INLINE const fmpz * fmpz_mod_ctx_modulus(const fmpz_mod_ctx_t ctx)
0048 {
0049     return ctx->n;
0050 }
0051
0052 void fmpz_mod_ctx_set_modulus(fmpz_mod_ctx_t ctx, const fmpz_t n);
0053 void fmpz_mod_ctx_set_modulus_ui(fmpz_mod_ctx_t ctx, ulong n);
0054
0055 int fmpz_mod_is_canonical(const fmpz_t a, const fmpz_mod_ctx_t ctx);
0056
0057 void fmpz_mod_assert_canonical(const fmpz_t a, const fmpz_mod_ctx_t ctx);
0058
0059 int fmpz_mod_is_one(const fmpz_t a, const fmpz_mod_ctx_t ctx);
0060
0061 int fmpz_mod_equal_fmpz(const fmpz_t a, const fmpz_t b, const fmpz_mod_ctx_t ctx);
0062 int fmpz_mod_equal_si(const fmpz_t a, slong b, const fmpz_mod_ctx_t ctx);
0063
0064 void fmpz_mod_set_fmpz(fmpz_t a, const fmpz_t b, const fmpz_mod_ctx_t ctx);
0065 void fmpz_mod_set_ui(fmpz_t a, ulong b, const fmpz_mod_ctx_t ctx);
0066 void fmpz_mod_set_si(fmpz_t a, slong b, const fmpz_mod_ctx_t ctx);
0067
0068 void _fmpz_mod_add1(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx);
0069 void _fmpz_mod_add2s(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t FLINT_UNUSED(ctx));
0070 void _fmpz_mod_add2(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx);
0071 void _fmpz_mod_addN(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx);
0072
0073 FMPZ_MOD_INLINE
0074 void fmpz_mod_add(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx)
0075 {
0076     (ctx->add_fxn)(a, b, c, ctx);
0077 }
0078
0079 void fmpz_mod_add_fmpz(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx);
0080 void fmpz_mod_add_ui(fmpz_t a, const fmpz_t b, ulong c, const fmpz_mod_ctx_t ctx);
0081 void fmpz_mod_add_si(fmpz_t a, const fmpz_t b, slong c, const fmpz_mod_ctx_t ctx);
0082
0083 void _fmpz_mod_sub1(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx);
0084 void _fmpz_mod_sub2s(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t FLINT_UNUSED(ctx));
0085 void _fmpz_mod_sub2(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx);
0086 void _fmpz_mod_subN(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx);
0087
0088 FMPZ_MOD_INLINE
0089 void fmpz_mod_sub(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx)
0090 {
0091     (ctx->sub_fxn)(a, b, c, ctx);
0092 }
0093
0094 void fmpz_mod_sub_fmpz(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx);
0095 void fmpz_mod_sub_ui(fmpz_t a, const fmpz_t b, ulong c, const fmpz_mod_ctx_t ctx);
0096 void fmpz_mod_sub_si(fmpz_t a, const fmpz_t b, slong c, const fmpz_mod_ctx_t ctx);
0097 void fmpz_mod_fmpz_sub(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx);
0098 void fmpz_mod_ui_sub(fmpz_t a, ulong b, const fmpz_t c, const fmpz_mod_ctx_t ctx);
0099 void fmpz_mod_si_sub(fmpz_t a, slong b, const fmpz_t c, const fmpz_mod_ctx_t ctx);
0100
0101 void fmpz_mod_neg(fmpz_t a, const fmpz_t b, const fmpz_mod_ctx_t ctx);
0102
0103 void _fmpz_mod_mul1(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx);
0104 void _fmpz_mod_mul2s(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t FLINT_UNUSED(ctx));
0105 void _fmpz_mod_mul2(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx);
0106 void _fmpz_mod_mulN(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx);
0107
0108 FMPZ_MOD_INLINE
0109 void fmpz_mod_mul(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx)
0110 {
0111     (ctx->mul_fxn)(a, b, c, ctx);
0112 }
0113
0114 void fmpz_mod_mul_fmpz(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx);
0115 void fmpz_mod_mul_ui(fmpz_t a, const fmpz_t b, ulong c, const fmpz_mod_ctx_t ctx);
0116 void fmpz_mod_mul_si(fmpz_t a, const fmpz_t b, slong c, const fmpz_mod_ctx_t ctx);
0117
0118 void fmpz_mod_addmul(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_t d, const fmpz_mod_ctx_t ctx);
0119
0120 int fmpz_mod_is_invertible(const fmpz_t a, const fmpz_mod_ctx_t ctx);
0121
0122 void fmpz_mod_inv(fmpz_t a, const fmpz_t b, const fmpz_mod_ctx_t ctx);
0123
0124 int fmpz_mod_divides(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx);
0125
0126 void fmpz_mod_pow_ui(fmpz_t a, const fmpz_t b, ulong pow, const fmpz_mod_ctx_t ctx);
0127 int fmpz_mod_pow_fmpz(fmpz_t a, const fmpz_t b, const fmpz_t pow, const fmpz_mod_ctx_t ctx);
0128
0129 void fmpz_mod_rand(fmpz_t a, flint_rand_t state, const fmpz_mod_ctx_t ctx);
0130 void fmpz_mod_rand_not_zero(fmpz_t a, flint_rand_t state, const fmpz_mod_ctx_t ctx);
0131
0132 /* discrete logs a la Pohlig - Hellman ***************************************/
0133
0134 typedef struct {
0135     fmpz_t gammapow;
0136     ulong cm;
0137 } fmpz_mod_discrete_log_pohlig_hellman_table_entry_struct;
0138
0139 typedef struct {
0140     slong exp;
0141     ulong prime;
0142     fmpz_t gamma;
0143     fmpz_t gammainv;
0144     fmpz_t startingbeta;
0145     fmpz_t co;
0146     fmpz_t startinge;
0147     fmpz_t idem;
0148     ulong cbound;
0149     ulong dbound;
0150     fmpz_mod_discrete_log_pohlig_hellman_table_entry_struct * table; /* length cbound */
0151 } fmpz_mod_discrete_log_pohlig_hellman_entry_struct;
0152
0153 typedef struct {
0154     fmpz_mod_ctx_t fpctx;
0155     fmpz_t pm1;      /* p - 1 */
0156     fmpz_t alpha;    /* p.r. of p */
0157     fmpz_t alphainv;
0158     slong num_factors;  /* factors of p - 1*/
0159     fmpz_mod_discrete_log_pohlig_hellman_entry_struct * entries;
0160 } fmpz_mod_discrete_log_pohlig_hellman_struct;
0161 typedef fmpz_mod_discrete_log_pohlig_hellman_struct fmpz_mod_discrete_log_pohlig_hellman_t[1];
0162
0163 void fmpz_mod_discrete_log_pohlig_hellman_init(fmpz_mod_discrete_log_pohlig_hellman_t L);
0164
0165 void fmpz_mod_discrete_log_pohlig_hellman_clear(fmpz_mod_discrete_log_pohlig_hellman_t L);
0166
0167 double fmpz_mod_discrete_log_pohlig_hellman_precompute_prime(fmpz_mod_discrete_log_pohlig_hellman_t L, const fmpz_t p);
0168
0169 void fmpz_mod_discrete_log_pohlig_hellman_run(fmpz_t x, const fmpz_mod_discrete_log_pohlig_hellman_t L, const fmpz_t y);
0170
0171 FMPZ_MOD_INLINE
0172 const fmpz * fmpz_mod_discrete_log_pohlig_hellman_primitive_root(fmpz_mod_discrete_log_pohlig_hellman_t L)
0173 {
0174     return L->alpha;
0175 }
0176
0177 int fmpz_next_smooth_prime(fmpz_t a, const fmpz_t b);
0178
0179 /* Declare dead functions *****************************************************/
0180
0181 #define fmpz_mod_ctx_get_modulus_mpz_read_only _Pragma("GCC error \"'fmpz_mod_ctx_get_modulus_mpz_read_only' is deprecated. Use 'fmpz_mod_ctx_modulus' instead.\"")
0182
0183 #ifdef __cplusplus
0184 }
0185 #endif
0186
0187 #endif