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 modulon
, 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 modulon
.
Conversions¶
-
void fmpz_mod_set_fmpz(fmpz_t a, const fmpz_t b, const fmpz_mod_ctx_t ctx)¶
Set
a
tob
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)\) and0
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 return0
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()
orfmpz_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 initializationL
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 modulop
to an internally chosen base. It is assumed thatp
is prime. 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 ofy
with respect to the internally stored base.y
is expected to be reduced modulo thep
. 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.