1.. _fmpz-mod: 2 3**fmpz_mod.h** -- arithmetic modulo integers 4=============================================================================== 5 6Description. 7 8Types, macros and constants 9------------------------------------------------------------------------------- 10 11.. type:: fmpz_mod_ctx_struct 12 13.. type:: fmpz_mod_ctx_t 14 15 The context object for arithmetic modulo integers. 16 17 18Context object 19-------------------------------------------------------------------------------- 20 21 22.. function:: void fmpz_mod_ctx_init(fmpz_mod_ctx_t ctx, const fmpz_t n) 23 24 Initialise ``ctx`` for arithmetic modulo ``n``, which is expected to be positive. 25 26.. function:: void fmpz_mod_ctx_clear(fmpz_mod_ctx_t ctx) 27 28 Free any memory used by ``ctx``. 29 30.. function:: void fmpz_mod_ctx_set_modulus(fmpz_mod_ctx_t ctx, const fmpz_t n) 31 32 Reconfigure ``ctx`` for arithmetic modulo ``n``. 33 34Arithmetic 35-------------------------------------------------------------------------------- 36 37Unless specified otherwise all functions here expect their relevant arguments to be in the canonical range `[0,n)`. 38Comparison of elements against each other or against zero can be accomplished with func::fmpz_equal or func::fmpz_is_zero without a context. 39 40.. function:: int fmpz_mod_is_canonical(const fmpz_t a, const fmpz_mod_ctx_t ctx) 41 42 Return ``1`` if `a` is in the canonical range `[0,n)` and ``0`` otherwise. 43 44.. function:: int fmpz_mod_is_one(const fmpz_t a, const fmpz_mod_ctx_t ctx) 45 46 Return ``1`` if `a` is `1` modulo `n` and return ``0`` otherwise. 47 48.. function:: void fmpz_mod_add(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx) 49 50 Set `a` to `b+c` modulo `n`. 51 52.. function:: void fmpz_mod_add_fmpz(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx); 53 void fmpz_mod_add_ui(fmpz_t a, const fmpz_t b, ulong c, const fmpz_mod_ctx_t ctx); 54 void fmpz_mod_add_si(fmpz_t a, const fmpz_t b, slong c, const fmpz_mod_ctx_t ctx); 55 56 Set `a` to `b+c` modulo `n` where only `b` is assumed to be canonical. 57 58.. function:: void fmpz_mod_sub(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx) 59 60 Set `a` to `b-c` modulo `n`. 61 62.. function:: void fmpz_mod_sub_fmpz(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx); 63 void fmpz_mod_sub_ui(fmpz_t a, const fmpz_t b, ulong c, const fmpz_mod_ctx_t ctx); 64 void fmpz_mod_sub_si(fmpz_t a, const fmpz_t b, slong c, const fmpz_mod_ctx_t ctx); 65 66 Set `a` to `b-c` modulo `n` where only `b` is assumed to be canonical. 67 68.. function:: void fmpz_mod_fmpz_sub(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx); 69 void fmpz_mod_ui_sub(fmpz_t a, ulong b, const fmpz_t c, const fmpz_mod_ctx_t ctx); 70 void fmpz_mod_si_sub(fmpz_t a, slong b, const fmpz_t c, const fmpz_mod_ctx_t ctx); 71 72 Set `a` to `b-c` modulo `n` where only `c` is assumed to be canonical. 73 74.. function:: void fmpz_mod_neg(fmpz_t a, const fmpz_t b, const fmpz_mod_ctx_t ctx) 75 76 Set `a` to `-b` modulo `n`. 77 78.. function:: void fmpz_mod_mul(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx) 79 80 Set `a` to `b*c` modulo `n`. 81 82.. function:: void fmpz_mod_inv(fmpz_t a, const fmpz_t b, const fmpz_mod_ctx_t ctx) 83 84 Set `a` to `b^{-1}` modulo `n`. 85 This function expects that `b` is invertible modulo `n` and throws if this not the case. 86 Invertibility maybe tested with func:`fmpz_mod_pow_fmpz` or func:`fmpz_mod_divides`. 87 88.. function:: int fmpz_mod_divides(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx) 89 90 If `a*c = b \mod n` has a solution for `a` return `1` and set `a` to such a solution. Otherwise return `0` and leave `a` undefined. 91 92.. function:: void fmpz_mod_pow_ui(fmpz_t a, const fmpz_t b, ulong e, const fmpz_mod_ctx_t ctx) 93 94 Set `a` to `b^e` modulo `n`. 95 96.. function:: int fmpz_mod_pow_fmpz(fmpz_t a, const fmpz_t b, const fmpz_t e, const fmpz_mod_ctx_t ctx) 97 98 Try to set `a` to `b^e` modulo `n`. 99 If `e < 0` and `b` is not invertible modulo `n`, the return is `0`. Otherwise, the return is `1`. 100 101 102Discrete Logarithms via Pohlig-Hellman 103-------------------------------------------------------------------------------- 104 105.. function:: void fmpz_mod_discrete_log_pohlig_hellman_init(fmpz_mod_discrete_log_pohlig_hellman_t L) 106 107 Initialize ``L``. Upon initialization ``L`` is not ready for computation. 108 109.. function:: void fmpz_mod_discrete_log_pohlig_hellman_clear(fmpz_mod_discrete_log_pohlig_hellman_t L) 110 111 Free any space used by ``L``. 112 113.. function:: double fmpz_mod_discrete_log_pohlig_hellman_precompute_prime(fmpz_mod_discrete_log_pohlig_hellman_t L, const fmpz_t p) 114 115 Configure ``L`` for discrete logarithms modulo ``p`` to an internally chosen base. It is assumed that ``p`` is prime. 116 The return is an estimate on the number of multiplications needed for one run. 117 118.. function:: const fmpz * fmpz_mod_discrete_log_pohlig_hellman_primitive_root(const fmpz_mod_discrete_log_pohlig_hellman_t L) 119 120 Return the internally stored base. 121 122.. function:: void fmpz_mod_discrete_log_pohlig_hellman_run(fmpz_t x, const fmpz_mod_discrete_log_pohlig_hellman_t L, const fmpz_t y) 123 124 Set ``x`` to the logarithm of ``y`` with respect to the internally stored base. ``y`` is expected to be reduced modulo the ``p``. 125 The function is undefined if the logarithm does not exist. 126 127 128.. function:: int fmpz_next_smooth_prime(fmpz_t a, const fmpz_t b) 129 130 Either return `1` and set `a` to a smooth prime strictly greater than `b`, or return `0` and set `a` to `0`. 131 The smooth primes returned by this function currently have no prime factor of `a-1` greater than `23`, but this should not be relied upon. 132 133