.. _nmod: **nmod.h** -- integers mod n (word-size n) =============================================================================== Modular reduction and arithmetic -------------------------------------------------------------------------------- .. function:: void nmod_init(nmod_t * mod, ulong n) Initialises the given ``nmod_t`` structure for reduction modulo `n` with a precomputed inverse. .. macro:: NMOD_BITS(mod) Macro giving the number of bits in ``mod.n``. .. macro:: NMOD_CAN_USE_SHOUP(mod) Macro returning whether Shoup's algorithm can be used for preconditioned multiplication mod ``mod.n``. .. macro:: NMOD_RED2(r, a_hi, a_lo, mod) Macro to set `r` to `a` reduced modulo ``mod.n``, where `a` consists of two limbs ``(a_hi, a_lo)``. The ``mod`` parameter must be a valid ``nmod_t`` structure. It is assumed that ``a_hi`` is already reduced modulo ``mod.n``. .. macro:: NMOD_RED(r, a, mod) Macro to set `r` to `a` reduced modulo ``mod.n``. The ``mod`` parameter must be a valid ``nmod_t`` structure. .. macro:: NMOD2_RED2(r, a_hi, a_lo, mod) Macro to set `r` to `a` reduced modulo ``mod.n``, where `a` consists of two limbs ``(a_hi, a_lo)``. The ``mod`` parameter must be a valid ``nmod_t`` structure. No assumptions are made about ``a_hi``. .. macro:: NMOD_RED3(r, a_hi, a_me, a_lo, mod) Macro to set `r` to `a` reduced modulo ``mod.n``, where `a` consists of three limbs ``(a_hi, a_me, a_lo)``. The ``mod`` parameter must be a valid ``nmod_t`` structure. It is assumed that ``a_hi`` is already reduced modulo ``mod.n``. .. macro:: NMOD_MUL_PRENORM(res, a, b, mod) Macro to set `r` to `ab` modulo ``mod.n``. The ``mod`` parameter must be a valid ``nmod_t`` structure. It is assumed that `a`, `b` are already reduced modulo ``mod.n`` and that either `a` or `b` is prenormalised by left-shifting by ``mod.norm``. .. macro:: NMOD_MUL_FULLWORD(res, a, b, mod) Macro to set `r` to `ab` modulo ``mod.n``. The ``mod`` parameter must be a valid ``nmod_t`` structure. It is assumed that `a`, `b` are already reduced modulo ``mod.n`` and that ``mod.n`` is exactly ``FLINT_BITS`` bits large. .. macro:: NMOD_ADDMUL(r, a, b, mod) Macro to set `r` to `r + ab` reduced modulo ``mod.n``. The ``mod`` parameter must be a valid ``nmod_t`` structure. It is assumed that `r`, `a`, `b` are already reduced modulo ``mod.n``. .. function:: ulong _nmod_add(ulong a, ulong b, nmod_t mod) Returns `a + b` modulo ``mod.n``. It is assumed that ``mod`` is no more than ``FLINT_BITS - 1`` bits. It is assumed that `a` and `b` are already reduced modulo ``mod.n``. .. function:: ulong nmod_add(ulong a, ulong b, nmod_t mod) Returns `a + b` modulo ``mod.n``. No assumptions are made about ``mod.n``. It is assumed that `a` and `b` are already reduced modulo ``mod.n``. .. function:: ulong _nmod_sub(ulong a, ulong b, nmod_t mod) Returns `a - b` modulo ``mod.n``. It is assumed that ``mod`` is no more than ``FLINT_BITS - 1`` bits. It is assumed that `a` and `b` are already reduced modulo ``mod.n``. .. function:: ulong nmod_sub(ulong a, ulong b, nmod_t mod) Returns `a - b` modulo ``mod.n``. No assumptions are made about ``mod.n``. It is assumed that `a` and `b` are already reduced modulo ``mod.n``. .. function:: ulong nmod_neg(ulong a, nmod_t mod) Returns `-a` modulo ``mod.n``. It is assumed that `a` is already reduced modulo ``mod.n``, but no assumptions are made about the latter. .. function:: ulong nmod_mul(ulong a, ulong b, nmod_t mod) Returns `ab` modulo ``mod.n``. No assumptions are made about ``mod.n``. It is assumed that `a` and `b` are already reduced modulo ``mod.n``. .. function:: ulong _nmod_mul_fullword(ulong a, ulong b, nmod_t mod) Returns `ab` modulo ``mod.n``. Requires that ``mod.n`` is exactly ``FLINT_BITS`` large. It is assumed that `a` and `b` are already reduced modulo ``mod.n``. .. function:: ulong nmod_inv(ulong a, nmod_t mod) Returns `a^{-1}` modulo ``mod.n``. The inverse is assumed to exist. .. function:: ulong nmod_div(ulong a, ulong b, nmod_t mod) Returns `ab^{-1}` modulo ``mod.n``. The inverse of `b` is assumed to exist. It is assumed that `a` is already reduced modulo ``mod.n``. .. function:: int nmod_divides(ulong * a, ulong b, ulong c, nmod_t mod) If `a\cdot 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. .. function:: ulong nmod_pow_ui(ulong a, ulong e, nmod_t mod) Returns `a^e` modulo ``mod.n``. No assumptions are made about ``mod.n``. It is assumed that `a` is already reduced modulo ``mod.n``. .. function:: ulong nmod_pow_fmpz(ulong a, const fmpz_t e, nmod_t mod) Returns `a^e` modulo ``mod.n``. No assumptions are made about ``mod.n``. It is assumed that `a` is already reduced modulo ``mod.n`` and that `e` is not negative. Discrete Logarithms via Pohlig-Hellman -------------------------------------------------------------------------------- .. function:: void nmod_discrete_log_pohlig_hellman_init(nmod_discrete_log_pohlig_hellman_t L) Initialize ``L``. Upon initialization ``L`` is not ready for computation. .. function:: void nmod_discrete_log_pohlig_hellman_clear(nmod_discrete_log_pohlig_hellman_t L) Free any space used by ``L``. .. function:: double nmod_discrete_log_pohlig_hellman_precompute_prime(nmod_discrete_log_pohlig_hellman_t L, ulong p) Configure ``L`` for discrete logarithms modulo ``p`` to an internally chosen base. It is assumed that ``p`` is prime. The return is an estimate on the number of multiplications needed for one run. .. function:: ulong nmod_discrete_log_pohlig_hellman_primitive_root(const nmod_discrete_log_pohlig_hellman_t L) Return the internally stored base. .. function:: ulong nmod_discrete_log_pohlig_hellman_run(const nmod_discrete_log_pohlig_hellman_t L, ulong y) Return the logarithm of ``y`` with respect to the internally stored base. ``y`` is expected to be reduced modulo the ``p``. The function is undefined if the logarithm does not exist.