fmpz_mod.h – arithmetic modulo integers

Types, macros and constants

type fmpz_mod_ctx_struct

type fmpz_mod_ctx_t

The context object for arithmetic modulo integers.

Context object

void fmpz_mod_ctx_init(fmpz_mod_ctx_t ctx, const fmpz_t n)

Initialise ctx for arithmetic modulo n, which is expected to be positive.

void fmpz_mod_ctx_clear(fmpz_mod_ctx_t ctx)

Free any memory used by ctx.

void fmpz_mod_ctx_set_modulus(fmpz_mod_ctx_t ctx, const fmpz_t n)

Reconfigure ctx for arithmetic modulo n.

Conversions

void fmpz_mod_set_fmpz(fmpz_t a, const fmpz_t b, const fmpz_mod_ctx_t ctx)

Set a to b after reduction modulo the modulus.

Arithmetic

Unless specified otherwise all functions here expect their relevant arguments to be in the canonical range \([0,n)\). Comparison of elements against each other or against zero can be accomplished with fmpz_equal() or fmpz_is_zero() without a context.

int fmpz_mod_is_canonical(const fmpz_t a, const fmpz_mod_ctx_t ctx)

Return 1 if \(a\) is in the canonical range \([0,n)\) and 0 otherwise.

int fmpz_mod_is_one(const fmpz_t a, const fmpz_mod_ctx_t ctx)

Return 1 if \(a\) is \(1\) modulo \(n\) and return 0 otherwise.

void fmpz_mod_add(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx)

Set \(a\) to \(b+c\) modulo \(n\).

void fmpz_mod_add_fmpz(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx)

void fmpz_mod_add_ui(fmpz_t a, const fmpz_t b, ulong c, const fmpz_mod_ctx_t ctx)

void fmpz_mod_add_si(fmpz_t a, const fmpz_t b, slong c, const fmpz_mod_ctx_t ctx)

Set \(a\) to \(b+c\) modulo \(n\) where only \(b\) is assumed to be canonical.

void fmpz_mod_sub(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx)

Set \(a\) to \(b-c\) modulo \(n\).

void fmpz_mod_sub_fmpz(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx)

void fmpz_mod_sub_ui(fmpz_t a, const fmpz_t b, ulong c, const fmpz_mod_ctx_t ctx)

void fmpz_mod_sub_si(fmpz_t a, const fmpz_t b, slong c, const fmpz_mod_ctx_t ctx)

Set \(a\) to \(b-c\) modulo \(n\) where only \(b\) is assumed to be canonical.

void fmpz_mod_fmpz_sub(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx)

void fmpz_mod_ui_sub(fmpz_t a, ulong b, const fmpz_t c, const fmpz_mod_ctx_t ctx)

void fmpz_mod_si_sub(fmpz_t a, slong b, const fmpz_t c, const fmpz_mod_ctx_t ctx)

Set \(a\) to \(b-c\) modulo \(n\) where only \(c\) is assumed to be canonical.

void fmpz_mod_neg(fmpz_t a, const fmpz_t b, const fmpz_mod_ctx_t ctx)

Set \(a\) to \(-b\) modulo \(n\).

void fmpz_mod_mul(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx)

Set \(a\) to \(b\cdot c\) modulo \(n\).

void fmpz_mod_inv(fmpz_t a, const fmpz_t b, const fmpz_mod_ctx_t ctx)

Set \(a\) to \(b^{-1}\) modulo \(n\). This function expects that \(b\) is invertible modulo \(n\) and throws if this not the case. Invertibility may be tested with fmpz_mod_pow_fmpz() or fmpz_mod_divides().

int fmpz_mod_divides(fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx)

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.

void fmpz_mod_pow_ui(fmpz_t a, const fmpz_t b, ulong e, const fmpz_mod_ctx_t ctx)

Set \(a\) to \(b^e\) modulo \(n\).

int fmpz_mod_pow_fmpz(fmpz_t a, const fmpz_t b, const fmpz_t e, const fmpz_mod_ctx_t ctx)

Try to set \(a\) to \(b^e\) modulo \(n\). If \(e < 0\) and \(b\) is not invertible modulo \(n\), the return is \(0\). Otherwise, the return is \(1\).

Discrete Logarithms via Pohlig-Hellman

void fmpz_mod_discrete_log_pohlig_hellman_init(fmpz_mod_discrete_log_pohlig_hellman_t L)

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

void fmpz_mod_discrete_log_pohlig_hellman_clear(fmpz_mod_discrete_log_pohlig_hellman_t L)

Free any space used by L.

double fmpz_mod_discrete_log_pohlig_hellman_precompute_prime(fmpz_mod_discrete_log_pohlig_hellman_t L, const fmpz_t p)

Configure L for discrete logarithms modulo p to an internally chosen base. It is assumed that p is prime (not checked). The return is an estimate on the number of multiplications needed for one run.

const fmpz *fmpz_mod_discrete_log_pohlig_hellman_primitive_root(fmpz_mod_discrete_log_pohlig_hellman_t L)

Return the internally stored base.

void fmpz_mod_discrete_log_pohlig_hellman_run(fmpz_t x, const fmpz_mod_discrete_log_pohlig_hellman_t L, const fmpz_t y)

Set x to the logarithm of y with respect to the internally stored base. y is expected to be reduced modulo the p (this is not checked). The function is undefined if the logarithm does not exist.

int fmpz_next_smooth_prime(fmpz_t a, const fmpz_t b)

Either return \(1\) and set \(a\) to a smooth prime strictly greater than \(b\), or return \(0\) and set \(a\) to \(0\). 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.