nmod.h – integers mod n (word-size n)

Modular reduction and arithmetic

void nmod_init(nmod_t *mod, ulong n)

Initialises the given nmod_t structure for reduction modulo \(n\) with a precomputed inverse.

NMOD_BITS(mod)

Macro giving the number of bits in mod.n.

NMOD_CAN_USE_SHOUP(mod)

Macro returning whether Shoup’s algorithm can be used for preconditioned multiplication mod mod.n.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

ulong nmod_inv(ulong a, nmod_t mod)

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

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.

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.

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.

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

void nmod_discrete_log_pohlig_hellman_init(nmod_discrete_log_pohlig_hellman_t L)

Initialize L. Upon initialization L is not ready for computation.

void nmod_discrete_log_pohlig_hellman_clear(nmod_discrete_log_pohlig_hellman_t L)

Free any space used by L.

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.

ulong nmod_discrete_log_pohlig_hellman_primitive_root(const nmod_discrete_log_pohlig_hellman_t L)

Return the internally stored base.

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.