.. _nmod-vec:

**nmod_vec.h** -- vectors over integers mod n (word-size n)
===============================================================================

Memory management
--------------------------------------------------------------------------------


.. function:: mp_ptr _nmod_vec_init(slong len)

    Returns a vector of the given length. The entries are not necessarily
    zero.

.. function:: void _nmod_vec_clear(mp_ptr vec)

    Frees the memory used by the given vector.


Modular reduction and arithmetic
--------------------------------------------------------------------------------


.. function:: void nmod_init(nmod_t * mod, mp_limb_t n)

    Initialises the given ``nmod_t`` structure for reduction modulo `n`
    with a precomputed inverse.

.. 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_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:: mp_limb_t _nmod_add(mp_limb_t a, mp_limb_t 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:: mp_limb_t nmod_add(mp_limb_t a, mp_limb_t 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:: mp_limb_t _nmod_sub(mp_limb_t a, mp_limb_t 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:: mp_limb_t nmod_sub(mp_limb_t a, mp_limb_t 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:: mp_limb_t nmod_neg(mp_limb_t 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:: mp_limb_t nmod_mul(mp_limb_t a, mp_limb_t 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:: mp_limb_t nmod_inv(mp_limb_t a, nmod_t mod)

    Returns `a^{-1}` modulo ``mod.n``. The inverse is assumed to exist.

.. function:: mp_limb_t nmod_div(mp_limb_t a, mp_limb_t 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:: mp_limb_t nmod_pow_ui(mp_limb_t 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:: mp_limb_t nmod_pow_fmpz(mp_limb_t 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.



Random functions
--------------------------------------------------------------------------------


.. function:: void _nmod_vec_randtest(mp_ptr vec, flint_rand_t state, slong len, nmod_t mod)

    Sets ``vec`` to a random vector of the given length with entries 
    reduced modulo ``mod.n``.


Basic manipulation and comparison
--------------------------------------------------------------------------------


.. function:: void _nmod_vec_set(mp_ptr res, mp_srcptr vec, slong len)

    Copies ``len`` entries from the vector ``vec`` to ``res``.

.. function:: void _nmod_vec_zero(mp_ptr vec, slong len)

    Zeros the given vector of the given length.

.. function:: void _nmod_vec_swap(mp_ptr a, mp_ptr b, slong length)

    Swaps the vectors ``a`` and ``b`` of length `n` by actually
    swapping the entries.

.. function:: void _nmod_vec_reduce(mp_ptr res, mp_srcptr vec, slong len, nmod_t mod)

    Reduces the entries of ``(vec, len)`` modulo ``mod.n`` and set 
    ``res`` to the result.

.. function:: flint_bitcnt_t _nmod_vec_max_bits(mp_srcptr vec, slong len)

    Returns the maximum number of bits of any entry in the vector.

.. function:: int _nmod_vec_equal(mp_srcptr vec, mp_srcptr vec2, slong len)

    Returns~`1` if ``(vec, len)`` is equal to ``(vec2, len)``, 
    otherwise returns~`0`.


Arithmetic operations
--------------------------------------------------------------------------------


.. function:: void _nmod_vec_add(mp_ptr res, mp_srcptr vec1, mp_srcptr vec2, slong len, nmod_t mod)

    Sets ``(res, len)`` to the sum of ``(vec1, len)`` 
    and ``(vec2, len)``.

.. function:: void _nmod_vec_sub(mp_ptr res, mp_srcptr vec1, mp_srcptr vec2, slong len, nmod_t mod)

    Sets ``(res, len)`` to the difference of ``(vec1, len)`` 
    and ``(vec2, len)``.

.. function:: void _nmod_vec_neg(mp_ptr res, mp_srcptr vec, slong len, nmod_t mod)

    Sets ``(res, len)`` to the negation of ``(vec, len)``.

.. function:: void _nmod_vec_scalar_mul_nmod(mp_ptr res, mp_srcptr vec, slong len, mp_limb_t c, nmod_t mod)

    Sets ``(res, len)`` to ``(vec, len)`` multiplied by `c`. The element
    `c` and all elements of `vec` are assumed to be less than `mod.n`.

.. function:: void _nmod_vec_scalar_mul_nmod_shoup(mp_ptr res, mp_srcptr vec, slong len, mp_limb_t c, nmod_t mod)

    Sets ``(res, len)`` to ``(vec, len)`` multiplied by `c` using
    :func:`n_mulmod_shoup`. `mod.n` should be less than `2^{\mathtt{FLINT\_BITS} - 1}`. `c` 
    and all elements of `vec` should be less than `mod.n`.

.. function:: void _nmod_vec_scalar_addmul_nmod(mp_ptr res, mp_srcptr vec, slong len, mp_limb_t c, nmod_t mod)

    Adds ``(vec, len)`` times `c` to the vector ``(res, len)``. The element
    `c` and all elements of `vec` are assumed to be less than `mod.n`.



Dot products
--------------------------------------------------------------------------------


.. function:: int _nmod_vec_dot_bound_limbs(slong len, nmod_t mod)

    Returns the number of limbs (0, 1, 2 or 3) needed to represent the
    unreduced dot product of two vectors of length ``len`` having entries
    modulo ``mod.n``, assuming that ``len`` is nonnegative and that
    ``mod.n`` is nonzero. The computed bound is tight. In other words,
    this function returns the precise limb size of ``len`` times
    ``(mod.n - 1) ^ 2``.

.. function:: macro NMOD_VEC_DOT(res, i, len, expr1, expr2, mod, nlimbs)

    Effectively performs the computation::

        res = 0;
        for (i = 0; i < len; i++)
            res += (expr1) * (expr2);

    but with the arithmetic performed modulo ``mod``.
    The ``nlimbs`` parameter should be 0, 1, 2 or 3, specifying the
    number of limbs needed to represent the unreduced result.

.. function:: mp_limb_t _nmod_vec_dot(mp_srcptr vec1, mp_srcptr vec2, slong len, nmod_t mod, int nlimbs)

    Returns the dot product of (``vec1``, ``len``) and
    (``vec2``, ``len``). The ``nlimbs`` parameter should be
    0, 1, 2 or 3, specifying the number of limbs needed to represent the
    unreduced result.

.. function:: mp_limb_t _nmod_vec_dot_ptr(mp_srcptr vec1, const mp_ptr * vec2, slong offset, slong len, nmod_t mod, int nlimbs)

    Returns the dot product of (``vec1``, ``len``) and the values at
    ``vec2[i][offset]``. The ``nlimbs`` parameter should be
    0, 1, 2 or 3, specifying the number of limbs needed to represent the
    unreduced result.


Discrete Logarithms via Pohlig-Hellman
--------------------------------------------------------------------------------

.. function:: void nmod_discrete_log_pohlig_hellman_init(nmod_discrete_log_pohlig_hellman_t L)

    Initialize ``L``. Upon initilization ``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, mp_limb_t 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:: mp_limb_t 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, mp_limb_t y)

    Return the logarithm of ``y`` with repect to the internally stored base. ``y`` is expected to be reduced modulo the ``p``.
    The function is undefined if the logarithm does not exist.
