mpn_mod.h

Initialises ctx to the ring \mathbb{Z}/n\mathbb{Z} with elements stored as arrays of as many limbs as n. Returns GR_DOMAIN if n \le 0 and GR_UNABLE if n does not have between MPN_MOD_MIN_LIMBS and MPN_MOD_MAX_LIMBS limbs; in both cases ctx is not initialised and must not be cleared. The underscore version takes n as nlimbs limbs, of which the top one must be nonzero.

Initialises ctx to \mathbb{Z}/n\mathbb{Z} for a random modulus, for testing. With probability 1/2 the modulus is one of a few primes of the form 2^k \pm c for k between 64 and 1024 (flagged as prime with probability 1/2); otherwise it is a random integer with an admissible number of limbs.

The gr methods for writing a description of the ring (Integers mod n (mpn)) and for freeing the context. Use gr_ctx_write and gr_ctx_clear.

Return or set the primality flag of the modulus. mpn_mod_ctx_set_is_field always returns GR_SUCCESS; nothing is checked. These are the gr_ctx_is_field and gr_ctx_set_is_field methods (the flag also answers gr_ctx_is_integral_domain and gr_ctx_is_unique_factorization_domain).

The methods behind gr_ctx_is_pretend_field, gr_ctx_set_is_pretend_field and gr_ctx_recover_zero_divisor. While the ring pretends to be a field, an inversion of a nonzero non-unit x fails with GR_UNABLE instead of GR_DOMAIN and records \gcd(x, n), a nontrivial factor of n, in the context (only the first one found is kept). mpn_mod_ctx_recover_zero_divisor sets res to the recorded factor and returns GR_SUCCESS, or sets res to zero and returns GR_UNABLE if none was recorded.

mpn_mod_init sets the \ell limbs at x to zero, mpn_mod_clear does nothing (elements own no memory) and mpn_mod_swap swaps the limbs of x and y.

Set res to a copy of x, to 0, to 1 and to n - 1.

Set res to x \bmod n, for any integer x.

Sets res to x \bmod n, where x \ge 0 is given by the xn limbs at x (\mathit{xn} \ge 0; the top limb may be zero). This is the reduction used throughout the module for unreduced sums and products. res may be the same pointer as x but must not overlap it otherwise.

Sets res to the element v of the ring v_ctx, converted to \mathbb{Z}/n\mathbb{Z}. Elements of another mpn_mod ring and of an fmpz_mod ring (gr_ctx_init_fmpz_mod) with the same modulus are copied directly; all other cases go through gr_generic_set_other (integers, rationals with invertible denominator, and so on). Returns GR_DOMAIN or GR_UNABLE when there is no such conversion.

Sets res to the integer in [0, n) represented by x.

Set res to a random element. mpn_mod_rand draws uniformly from [0, n) (fmpz_randm); mpn_mod_randtest uses fmpz_randtest_mod, which favours special values such as 0, 1 and n - 1 and values with long runs of zero or one bits, for testing.

Writes x in decimal, as an integer in [0, n).

Return T_TRUE if x = 0, x = 1, x = n - 1 or x = y, and T_FALSE otherwise. Since residues are reduced, these compare limbs.

Set res to -x, x + y and x - y modulo n, with one conditional correction. Two-limb moduli use the inline functions flint_mpn_negmod_2, flint_mpn_addmod_2 and flint_mpn_submod_2.

Set res to x + y or x - y modulo n, for reduced x and any integer y.

Set res to xy and x^2 modulo n.

Set res to xy \bmod n, for reduced x and any integer y. The product x |y| is formed exactly and reduced with mpn_mod_set_mpn (an fmpz with more limbs than n is reduced first).

Set res to res + xy or res - xy modulo n. The product is reduced before it is added.

Sets res to x_1 y_1 + x_2 y_2 \bmod n with a single reduction of the unreduced sum (flint_mpn_fmmamod_preinvn), which costs little more than one modular multiplication.

Sets res to x^{-1} \bmod n and returns GR_SUCCESS if \gcd(x, n) = 1. Otherwise returns GR_DOMAIN, or GR_UNABLE if x is nonzero and the ring pretends to be a field (recording \gcd(x, n), see Context objects); res is then left unchanged.

Sets res to x y^{-1} \bmod n, computing the inverse with mpn_mod_inv. If y is not invertible, sets res to zero and returns the status of mpn_mod_inv, even if some z with yz = x exists.

Set res to x^e \bmod n, with 0^0 = 1. A negative exponent requires x to be invertible and otherwise gives the status of mpn_mod_inv.

Test whether x is a square, and compute a square root of x.

Zero, clear (a no-op), copy and swap vectors, limb by limb.

Elementwise negation, addition, subtraction and multiplication. Two-limb moduli use inlined fixed-size code with the modulus kept in registers.

Set res to x y, y x, res + x y and res - x y elementwise, for a vector x and a scalar y.

Set res to s + \sum_i a_i b_i, or s - \sum_i a_i b_i if subtract is nonzero, where s is initial (zero if initial is NULL), a_i = vec1[i] and b_i = vec2[i], vec2[len - 1 - i] or the entries of the strided vectors (strides counted in elements, possibly negative).

Set C = AB. mpn_mod_mat_mul chooses between classical multiplication with delayed reduction (gr_mat_mul_classical with the dot product above), Waksman's algorithm with delayed reduction and multimodular multiplication via nmod_mat_mul. See Matrix multiplication over Z/nZ for multiword n.

Solve LX = B or UX = B for a triangular matrix with invertible diagonal (unit diagonal, not read, if unit is nonzero), choosing gr_mat_nonsingular_solve_tril_classical (resp. _triu_) when B has fewer rows or columns than a cutoff depending on \ell (700 for \ell = 2, 200 for \ell = 3, down to 20 for \ell \ge 12), and the block recursive versions otherwise, whose products use mpn_mod_mat_mul.

LU decomposition with the conventions of gr_mat_lu: PA = LU with the permutation in P, L unit lower triangular and U in row echelon form, both stored in the output, and the rank in *rank. If rank_check is nonzero, the decomposition stops with rank 0 as soon as the matrix is found to be singular. Returns GR_DOMAIN (or GR_UNABLE when pretending to be a field) if a nonzero pivot is not invertible.

Sets res to the determinant of the square matrix A, using cofactor expansion up to 4 \times 4, the division-free Berkowitz algorithm for 5 \times 5, and LU decomposition otherwise. If the LU decomposition meets a non-invertible pivot (for a composite modulus), the determinant is computed with the Berkowitz algorithm instead, so the function works for every modulus. Returns GR_DOMAIN if A is not square.

Sets the m + 1 coefficients at res to the characteristic polynomial of the m \times m matrix mat, with the Berkowitz algorithm for m \le 11 and Danilevsky's algorithm (_gr_mat_charpoly_danilevsky) for larger m. Danilevsky's algorithm divides by pivots, so for a composite modulus it can fail; the function then falls back to the division-free Berkowitz algorithm, and always succeeds. This is the method behind gr_mat_charpoly.

Reduces row m of A against the previous rows, with the conventions of gr_mat_reduce_row; used by gr_mat_minpoly_field. The row is kept unreduced in 2\ell + 1 limbs per entry during the elimination. Returns GR_DOMAIN (or GR_UNABLE when pretending) if a new pivot is not invertible.

Low and middle products with automatic choice of algorithm. These are the _gr_poly_mullow and _gr_poly_mulmid methods of the ring.

Schoolbook multiplication: each output coefficient is an unreduced dot product of fixed limb size, reduced once.

Karatsuba multiplication on unreduced integer coefficients (_flint_mpn_poly_mulmid_karatsuba), recursing down to schoolbook multiplication when the shorter operand is shorter than cutoff; a cutoff of -1 selects the tuned value. The coefficients are reduced only at the end.

Middle product without intermediate reductions, choosing between the schoolbook algorithm and Karatsuba with the tuned cutoff of _flint_mpn_poly_mulmid, with output sizes given by _flint_mpn_poly_mulmid_slimbs. This is what _mpn_mod_poly_mulmid uses for short and medium lengths.

Multiplication by Kronecker substitution: the coefficients are packed into integers with 2b + \lfloor \log_2 \min(\mathit{len1}, \mathit{len2}) \rfloor + 1 bits per coefficient, the integers are multiplied with flint_mpn_mul and the output coefficients are extracted and reduced.

Multiplication with the small-prime FFT of fft_small: the coefficients are reduced modulo up to eight 50-bit primes, multiplied by number-theoretic transforms and reconstructed by Chinese remaindering. Returns GR_UNABLE, writing nothing, if fft_small is not available or the product of eight primes is too small for the coefficients of the integer product, which limits n to about 190 bits (196 bits for very short, 189 bits for lengths around 10^5).

Power series inversion Q = B^{-1} \bmod x^{\mathit{len}} and division Q = A / B \bmod x^{\mathit{len}}, with the conventions of _gr_poly_inv_series and _gr_poly_div_series (the constant term of B must be invertible). They use the basecase algorithms up to a tuned length of B (between 66 and 370 depending on the size of n; always for \mathit{lenB} \le 20) and Newton iteration above it.

Division with remainder A = QB + R and the quotient alone, with the conventions of _gr_poly_divrem (\mathit{lenA} \ge \mathit{lenB} \ge 1, Q with room for \mathit{lenA} - \mathit{lenB} + 1 and R for \mathit{lenB} - 1 coefficients, leading coefficient of B invertible). _mpn_mod_poly_divrem uses the delayed-reduction basecase when \mathit{lenA}, \mathit{lenB} or \mathit{lenA} - \mathit{lenB} is at most a cutoff (between 38 and 166 depending on the size of n), and Newton division otherwise; _mpn_mod_poly_div uses _gr_poly_div_basecase up to the series division cutoff and _gr_poly_div_newton above it. Return GR_DOMAIN (or GR_UNABLE when pretending) if the leading coefficient of B is not invertible.

Schoolbook division with remainder. The preinv1 version takes the inverse invL of the leading coefficient of B; the other computes it and returns GR_DOMAIN (or GR_UNABLE) if it does not exist.

Division with remainder in the case \mathit{lenA} = \mathit{lenB} + 1, where the quotient q_1 x + q_0 has two coefficients, given the inverse invL of the leading coefficient of B. Require \mathit{lenB} \ge 2.

Greatest common divisor and extended gcd, with the conventions of _gr_poly_gcd and _gr_poly_xgcd. They use the Euclidean algorithm (_gr_poly_gcd_euclidean, _gr_poly_xgcd_euclidean), whose division steps are _mpn_mod_poly_divrem_q1_preinv1, if either length is below 240, and the half-gcd algorithm (_gr_poly_gcd_hgcd, _gr_poly_xgcd_hgcd with inner cutoff 80 and outer cutoff 240) otherwise; see Half-GCD. The modulus should be prime, or the ring should pretend to be a field: a non-invertible leading coefficient gives GR_DOMAIN (GR_UNABLE when pretending, recording a factor of n).

The methods of the ring behind gr_ctx_init_gr_poly_transformed_repr and gr_ctx_init_gr_poly_transformed_cyclic_repr. They initialise ctx to a ring of transformed polynomials over the mpn_mod ring base, either for polynomials of length up to len_bound (linear), or for products modulo x^N - 1, where N is the least power of two that is at least *len and at least 256 and is written back to *len (cyclic). Each element may accumulate up to terms_bound products of two converted polynomials. Return GR_UNABLE if fft_small is not available, the modulus is too large, or the workload model predicts no gain over ordinary multiplication or exceeds the memory budget flint_fft_small_max_transformed_ring_size.

Conversions between mpn_mod coefficient vectors and fft_small operands, the analogues of fft_small_fft_nmod and fft_small_export_nmod_range, declared only when FLINT_HAVE_FFT_SMALL is set. fft_small_fft_mpn_mod reduces the an coefficients at a modulo each prime of the plan P and transforms them with truncation itrunc (at least an, at most the plan's ztrunc). fft_small_export_mpn_mod_range inverse-transforms X, reconstructs the coefficients of index \mathit{zl} \le i < \mathit{zh} (within the plan's window) by Chinese remaindering, reduces them modulo n and writes the \mathit{zh} - \mathit{zl} results to z; the reconstructed integers must be nonnegative and below half the product of the primes.

Returns the status of a failed inversion of the residue x, given g = \gcd(x, n) in gsize limbs: GR_DOMAIN if x = 0 or the ring does not pretend to be a field; otherwise GR_UNABLE, after recording g as the zero divisor of the context if none was recorded and 1 < g < n.

Sets the len elements at res to uniformly random residues with mpn_mod_rand.