nmod_vec.h – vectors over integers mod n (word-size n)¶
Memory management¶
-
mp_ptr
_nmod_vec_init
(slong len)¶ Returns a vector of the given length. The entries are not necessarily zero.
-
void
_nmod_vec_clear
(mp_ptr vec)¶ Frees the memory used by the given vector.
Modular reduction and arithmetic¶
-
void
nmod_init
(nmod_t * mod, mp_limb_t n)¶ Initialises the given
nmod_t
structure for reduction modulo \(n\) with a precomputed inverse.
-
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)
. Themod
parameter must be a validnmod_t
structure. It is assumed thata_hi
is already reduced modulomod.n
.
-
NMOD_RED
(r, a, mod)¶ Macro to set \(r\) to \(a\) reduced modulo
mod.n
. Themod
parameter must be a validnmod_t
structure.
-
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)
. Themod
parameter must be a validnmod_t
structure. No assumptions are made abouta_hi
.
-
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)
. Themod
parameter must be a validnmod_t
structure. It is assumed thata_hi
is already reduced modulomod.n
.
-
NMOD_ADDMUL
(r, a, b, mod)¶ Macro to set \(r\) to \(r + ab\) reduced modulo
mod.n
. Themod
parameter must be a validnmod_t
structure. It is assumed that \(r\), \(a\), \(b\) are already reduced modulomod.n
.
-
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 thatmod
is no more thanFLINT_BITS - 1
bits. It is assumed that \(a\) and \(b\) are already reduced modulomod.n
.
-
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 aboutmod.n
. It is assumed that \(a\) and \(b\) are already reduced modulomod.n
.
-
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 thatmod
is no more thanFLINT_BITS - 1
bits. It is assumed that \(a\) and \(b\) are already reduced modulomod.n
.
-
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 aboutmod.n
. It is assumed that \(a\) and \(b\) are already reduced modulomod.n
.
-
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 modulomod.n
, but no assumptions are made about the latter.
-
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 aboutmod.n
. It is assumed that \(a\) and \(b\) are already reduced modulomod.n
.
-
mp_limb_t
nmod_inv
(mp_limb_t a, nmod_t mod)¶ Returns \(a^{-1}\) modulo
mod.n
. The inverse is assumed to exist.
-
mp_limb_t
nmod_div
(mp_limb_t a, mp_limb_t b, nmod_t mod)¶ Returns \(a^{-1}\) modulo
mod.n
. The inverse of \(b\) is assumed to exist. It is assumed that \(a\) is already reduced modulomod.n
.
-
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 aboutmod.n
. It is assumed that \(a\) is already reduced modulomod.n
.
Random functions¶
-
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 modulomod.n
.
Basic manipulation and comparison¶
-
void
_nmod_vec_set
(mp_ptr res, mp_srcptr vec, slong len)¶ Copies
len
entries from the vectorvec
tores
.
-
void
_nmod_vec_zero
(mp_ptr vec, slong len)¶ Zeros the given vector of the given length.
-
void
_nmod_vec_swap
(mp_ptr a, mp_ptr b, slong length)¶ Swaps the vectors
a
andb
of length \(n\) by actually swapping the entries.
-
void
_nmod_vec_reduce
(mp_ptr res, mp_srcptr vec, slong len, nmod_t mod)¶ Reduces the entries of
(vec, len)
modulomod.n
and setres
to the result.
-
mp_bitcnt_t
_nmod_vec_max_bits
(mp_srcptr vec, slong len)¶ Returns the maximum number of bits of any entry in the vector.
-
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¶
-
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)
.
-
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)
.
-
void
_nmod_vec_neg
(mp_ptr res, mp_srcptr vec, slong len, nmod_t mod)¶ Sets
(res, len)
to the negation of(vec, len)
.
-
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\).
-
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\) usingn_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\).
-
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¶
-
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 modulomod.n
, assuming thatlen
is nonnegative and thatmod.n
is nonzero. The computed bound is tight. In other words, this function returns the precise limb size oflen
times(mod.n - 1) ^ 2
.
-
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
. Thenlimbs
parameter should be 0, 1, 2 or 3, specifying the number of limbs needed to represent the unreduced result.
-
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
). Thenlimbs
parameter should be 0, 1, 2 or 3, specifying the number of limbs needed to represent the unreduced result.
-
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 atvec2[i][offset]
. Thenlimbs
parameter should be 0, 1, 2 or 3, specifying the number of limbs needed to represent the unreduced result.