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.