Malachite for FLINT Users: Integers mod n
This page maps the functions of FLINT’s fmpz_mod.h, arithmetic modulo integers, onto their
Malachite counterparts: the Mod* traits, applied to
Natural
residues. It follows the organization of the
fmpz_mod.h chapter of the FLINT manual, as of FLINT
3.6.0, and is a companion to
Malachite for FLINT Users: Integers; the
mapping index lists the whole family. The conventions of
the GMP page and
the fmpz page apply here as well.
Conventions
Canonical residues are the shared ground
FLINT’s functions expect their arguments in the canonical range [0, n), and so do Malachite’s
Mod* traits,
ModAdd,
ModMul,
ModPow,
and the rest; reduction into that range is a separate, explicit step. Residues are
Naturals, so a
positive modulus is a fact of the types. Malachite enforces what FLINT trusts: passing an
unreduced operand to a Mod* function panics, where FLINT’s behavior is undefined. The
Mod*-prefixed traits (reduced operands) differ from the *Mod-suffixed ones (remainders of
division, any operands); see the fmpz page under
fmpz_negmod.
What becomes of the context
Every function in this chapter takes an fmpz_mod_ctx_t, holding the modulus and precomputed
reduction data. A Mod* function takes the modulus as an ordinary argument instead: where FLINT
writes fmpz_mod_mul(a, b, c, ctx), Malachite writes b.mod_mul(&c, &m), and there is no object
to initialize, reconfigure, or free.
For multiplication,
ModMulPrecomputed
computes a reusable Data value once, with precompute_mod_mul_data(&m), which
mod_mul_precomputed then uses; it is implemented for Natural and the primitive types.
ModPowPrecomputed
does the same for exponentiation, for the primitive types only. No single object serves every
operation; addition, subtraction, and negation need no precomputed data.
When the modulus is \(2^k\),
ModPowerOf2Add
and its relatives take k as the argument, with no precomputation.
Categories
Each function falls into one of four categories:
| meaning | |
|---|---|
| ✓ | A Malachite function does the same thing. |
| ≈ | A Malachite function serves the same purpose, but its specification differs. The notes say how. |
| — | No counterpart is needed, either because Rust handles it for you or because it is outside Malachite’s scope. The notes say which. |
| ✗ | Malachite does not fully support this yet, but will in a future version. |
Context object
| FLINT | Malachite | |
|---|---|---|
| ≈ | void fmpz_mod_ctx_init (fmpz_mod_ctx_t ctx, const fmpz_t n) |
ModMulPrecomputed |
| — | void fmpz_mod_ctx_clear (fmpz_mod_ctx_t ctx) |
|
| ≈ | void fmpz_mod_ctx_set_modulus (fmpz_mod_ctx_t ctx, const fmpz_t n) |
ModMulPrecomputed |
fmpz_mod_ctx_init, fmpz_mod_ctx_set_modulus. Keep the modulus as a
Natural and,
for repeated multiplication, pass the Data from precompute_mod_mul_data(&m) to each
mod_mul_precomputed. The rows are ≈ because the precomputation covers only multiplication. To
change the modulus, compute new Data.
fmpz_mod_ctx_clear. The Data value and the modulus are dropped like any other value.
Conversions
| FLINT | Malachite | |
|---|---|---|
| ✓ | void fmpz_mod_set_fmpz (fmpz_t a, const fmpz_t b, const fmpz_mod_ctx_t ctx) |
Mod, ModEuclidean |
fmpz_mod_set_fmpz. A
Natural
reduces with b.mod_op(&m); an
Integer
reduces with
ModEuclidean,
whose remainder lies in [0, n), as FLINT’s does.
Arithmetic
The context argument becomes &m, and each function maps to the Mod* trait of the same name.
| FLINT | Malachite | |
|---|---|---|
| ✓ | int fmpz_mod_is_canonical (const fmpz_t a, const fmpz_mod_ctx_t ctx) |
ModIsReduced |
| ✓ | int fmpz_mod_is_one (const fmpz_t a, const fmpz_mod_ctx_t ctx) |
PartialEq |
| ✓ | void fmpz_mod_add (fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx) |
ModAdd, ModAddAssign |
| ✓ | void fmpz_mod_add_fmpz (fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx) |
ModAdd, Mod |
| ✓ | void fmpz_mod_add_ui (fmpz_t a, const fmpz_t b, ulong c, const fmpz_mod_ctx_t ctx) |
ModAdd, Mod |
| ✓ | void fmpz_mod_add_si (fmpz_t a, const fmpz_t b, slong c, const fmpz_mod_ctx_t ctx) |
ModAdd, ModEuclidean |
| ✓ | void fmpz_mod_sub (fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx) |
ModSub, ModSubAssign |
| ✓ | void fmpz_mod_sub_fmpz (fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx) |
ModSub, Mod |
| ✓ | void fmpz_mod_sub_ui (fmpz_t a, const fmpz_t b, ulong c, const fmpz_mod_ctx_t ctx) |
ModSub, Mod |
| ✓ | void fmpz_mod_sub_si (fmpz_t a, const fmpz_t b, slong c, const fmpz_mod_ctx_t ctx) |
ModSub, ModEuclidean |
| ✓ | void fmpz_mod_fmpz_sub (fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx) |
ModSub, Mod |
| ✓ | void fmpz_mod_ui_sub (fmpz_t a, ulong b, const fmpz_t c, const fmpz_mod_ctx_t ctx) |
ModSub, Mod |
| ✓ | void fmpz_mod_si_sub (fmpz_t a, slong b, const fmpz_t c, const fmpz_mod_ctx_t ctx) |
ModSub, ModEuclidean |
| ✓ | void fmpz_mod_neg (fmpz_t a, const fmpz_t b, const fmpz_mod_ctx_t ctx) |
ModNeg, ModNegAssign |
| ✓ | void fmpz_mod_mul (fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx) |
ModMul, ModMulPrecomputed |
| ✓ | void fmpz_mod_inv (fmpz_t a, const fmpz_t b, const fmpz_mod_ctx_t ctx) |
ModInverse |
| ✓ | int fmpz_mod_divides (fmpz_t a, const fmpz_t b, const fmpz_t c, const fmpz_mod_ctx_t ctx) |
ModDiv |
| ✓ | void fmpz_mod_pow_ui (fmpz_t a, const fmpz_t b, ulong e, const fmpz_mod_ctx_t ctx) |
ModPow, ModPowAssign |
| ✓ | int fmpz_mod_pow_fmpz (fmpz_t a, const fmpz_t b, const fmpz_t e, const fmpz_mod_ctx_t ctx) |
ModPow, ModInverse |
fmpz_mod_is_canonical, fmpz_mod_is_one. a.mod_is_reduced(&m) tests canonicality.
fmpz_mod_is_one is a == 1, except when n is 1: FLINT then answers true, while the
canonical residue is 0 and a == 1 is false.
Addition, subtraction, negation. b.mod_add(&c, &m), b.mod_sub(&c, &m), and
b.mod_neg(&m), each with an Assign form. In the nine mixed variants only one operand is
assumed canonical (b, or c for the reversed subtractions); reduce the other first, with
Mod for a ulong,
ModEuclidean
for an slong, and, for an fmpz, Mod against the modulus as an Integer followed by
Natural::exact_from (the remainder is nonnegative but is returned as an Integer), then apply
the canonical operation. For the reversed subtractions,
fmpz_mod_fmpz_sub and its ui/si forms, reduce b and write b_reduced.mod_sub(&c, &m).
fmpz_mod_mul. b.mod_mul(&c, &m); in a loop over one modulus, use
mod_mul_precomputed, as under Conventions.
fmpz_mod_inv. b.mod_inverse(&m). Where FLINT throws when b is not invertible,
mod_inverse returns Option.
fmpz_mod_divides. b.mod_div(&c, &m) solves \(a c \equiv b \pmod n\), succeeding whenever
gcd(c, n) divides b, even when c is not invertible; FLINT’s flag-plus-output protocol
becomes an Option. When the
solution is not unique, both functions return the same particular solution. For the full
solution set, see fmpz_divides_mod_list
on the fmpz page.
fmpz_mod_pow_ui, fmpz_mod_pow_fmpz. b.mod_pow(&e, &m), with a
Natural
exponent of any size, covers both rows. For a negative exponent, which fmpz_mod_pow_fmpz
accepts when b is invertible, call b.mod_inverse(&m), whose
None corresponds to FLINT’s
0 return, then mod_pow with the exponent’s absolute value.
Discrete Logarithms via Pohlig-Hellman
Malachite has no counterpart to the five fmpz_mod_discrete_log_pohlig_hellman functions or to
fmpz_next_smooth_prime.