nmod.h

Sets mod to the modulus n, computing norm and ninv. Requires n \ne 0.

Return x \bmod n in [0, n), for any x.

Return a + b, a - b and -a modulo n, for reduced operands and any n.

Branch-free versions of nmod_add and nmod_sub. Require n \le 2^{\mathtt{FLINT\_BITS} - 1}; for larger n the result is wrong.

Returns (a + b) \bmod n for any a and b.

Returns ab \bmod n for reduced operands and any n.

Returns ab \bmod n for reduced operands. Requires mod.norm = 0, that is, n \ge 2^{\mathtt{FLINT\_BITS} - 1}. It saves the normalisation shift of nmod_mul.

Returns ab \bmod n for any a and b.

Return s + ab and ab + cd modulo n, for reduced operands. nmod_addmul forms s + ab as a two-word integer and reduces it once.

Returns a^{-1} \bmod n for reduced a. Throws an exception if \gcd(a, n) \ne 1.

Returns a b^{-1} \bmod n for reduced a and b. Throws an exception if \gcd(b, n) \ne 1.

If ac \equiv b \pmod n has a solution, sets *a to one solution and returns 1; otherwise returns 0. Unlike nmod_div, this works when c is not invertible. Requires reduced b and c.

Return a^{\mathit{exp}} \bmod n for reduced a, with a^0 = 1 (which is 0 when n = 1). For a negative exponent, nmod_pow_fmpz returns (a^{-1})^{-\mathit{exp}} and throws FLINT_IMPINV if a is not invertible modulo n.

Returns a^{\mathit{exp}} \bmod n for any a.

Returns 2^{\mathit{exp}} \bmod n.

The algorithms behind nmod_pow_ui and nmod_2_pow_ui, with the same results. The first two require \mathit{exp} \ge 1 (they do not terminate for \mathit{exp} = 0), and _nmod_pow_ui_redc requires odd n. _nmod_2_pow_ui_binexp accepts any n and any exponent.

For prime n and reduced a: if a is a square modulo n, sets *res to the square root in [0, n/2] and returns 1; otherwise sets *res to 0 and returns 0. Primality is not checked. For composite n, a return value of 1 still gives a genuine square root, but 0 does not prove that none exists.

For odd n and a < n, finds the least square root of a modulo n by exhaustive search in O(n) steps. Returns 1 and sets *res to the root, or returns 0 and sets *res to 0 if there is none. The answer is correct for composite n too.

Initialise L and free its memory. An initialised L must be set up with nmod_discrete_log_pohlig_hellman_precompute_prime before it is used.

Sets up L for the prime p, which is not checked, freeing any earlier data. Returns an estimate of the number of multiplications modulo p needed by one call to nmod_discrete_log_pohlig_hellman_run.

Returns the base g of the logarithms, the least primitive root modulo p.

Returns the x \in [0, p - 1) with g^x \equiv y \pmod p. Requires 0 < y < p.

Initialise ctx for the standard and fast functions modulo n, which must be odd.

Returns whether n < 2^{\mathtt{FLINT\_BITS} - 2}, the condition for the fast functions.

Return the Montgomery form x R \bmod n of x. nmod_redc_set_nmod requires x < n; nmod_redc_set_ui accepts any x.

Returns x R^{-1} \bmod n in [0, n), converting from Montgomery form. Any word x is accepted, in particular a lazy residue.

Negation, addition, subtraction and multiplication in Montgomery form, for inputs and output in [0, n). Negation, addition and subtraction are the same as for ordinary residues.

The same operations on lazy residues: inputs and output are in [0, 2n). Require n < 2^{\mathtt{FLINT\_BITS} - 2}.

Returns a lazy residue in [0, 2n) congruent to 2x, for x \in [0, 2n).

Reduces a lazy residue x \in [0, 2n) to [0, n).

Return a^{\mathit{exp}} with a and the result in Montgomery form, by binary exponentiation. Require \mathit{exp} \ge 1. The fast version takes and returns lazy residues.

Return the Montgomery form of 2^{\mathit{exp}}, for any \mathit{exp}. The fast version returns a lazy residue.

Initialise ctx for the half functions modulo n, which must be odd with n < 2^{\mathtt{FLINT\_BITS}/2 - 1}.

Returns whether n < 2^{\mathtt{FLINT\_BITS}/2 - 2}, the condition for the half_fast functions.

Convert to and from Montgomery form with R = 2^{\mathtt{FLINT\_BITS}/2}. nmod_redc_half_set_nmod requires x < n and nmod_redc_half_set_ui accepts any x. nmod_redc_half_get_nmod returns a value in [0, n) for any x < nR, in particular for lazy residues.

Addition, subtraction and multiplication in Montgomery form, for inputs and output in [0, n).

The same on lazy residues in [0, 2n). Require n < 2^{\mathtt{FLINT\_BITS}/2 - 2}.

Return x R^{-1} \bmod n for any word x. n_redc_fast returns a value in [0, n], which may need one more subtraction of n.

Return a value congruent to x R^{-1} modulo n, for a two-word x. n_ll_redc requires x < nB and returns a value in [0, n). n_ll_redc_fast requires x + (B - 1) n < B^2 and returns a value below x/B + n.

Return a value congruent to ab R^{-1} modulo n. n_mulmod_redc requires ab < nB (for example a, b < n) and returns a value in [0, n). n_mulmod_redc_fast maps a, b \in [0, 2n) to [0, 2n) when n < 2^{\mathtt{FLINT\_BITS} - 2}.

Returns a B \bmod n for a < n, given ninv and norm as stored in an nmod_t for n. This is one division step with the precomputed inverse.

The same with R = 2^{\mathtt{FLINT\_BITS}/2}. The reductions require x + (R - 1) n < B, and the ranges of inputs and outputs are those of the corresponding nmod_redc_half functions. n_to_redc_half_preinv ignores norm.

Construct the two-word integer \mathit{hi} B + \mathit{lo}, and return the high or the low word of x.

Return (x + y) \bmod B^2, and the full product xy of two words.

Initialise ctx for the ring \mathbb{Z}/n\mathbb{Z} in the given representation and return GR_SUCCESS. If n = 0, return GR_DOMAIN; if n violates the restrictions of the representation, return GR_UNABLE. In both cases ctx is not initialised.

Initialises ctx like gr_ctx_init_nmod, copying the nmod_t that nmod_t_ref points to instead of recomputing it.