fmpz_mod.h

Initialises ctx for arithmetic modulo n. Throws an exception if n \le 0.

Initialise ctx with a random modulus, for testing: 2 + m with m a random integer of at most max_bits bits (from fmpz_randtest_unsigned), respectively the least probable prime (fmpz_nextprime without proof) greater than such an m. The modulus can have slightly more than max_bits bits.

Frees the memory used by ctx.

Returns a pointer to the modulus n, valid as long as the context is not cleared or changed.

Changes the modulus of the initialised context ctx to n, which must be positive. Residues computed for the old modulus are not reduced.

Sets a to b \bmod n in [0, n), for any integer b.

fmpz_mod_is_canonical returns 1 if 0 \le a < n and 0 otherwise. fmpz_mod_assert_canonical throws an exception if a is not canonical, in every build.

Returns 1 if a is 1 modulo n, that is, if a = 1 or n = 1, and 0 otherwise.

Return 1 if the canonical residue a is congruent to the integer b modulo n (any b), and 0 otherwise.

Set a to b + c, b - c and -b modulo n, for canonical b and c.

Set a to b + c or b - c modulo n, for canonical b and any integer c. The sum is computed exactly and reduced with fmpz_mod.

Set a to b - c modulo n, for any integer b and canonical c.

Sets a to bc modulo n, for canonical b and c, with the function selected by the context: nmod_mul for one-word moduli, a two-limb Barrett reduction with at most two corrections for two-limb moduli, and fmpz_mul followed by fmpz_mod (or fmpz_fdiv_r_preinvn above 20 limbs) otherwise.

Set a to bc modulo n, for canonical b and any integer c. The product is computed exactly and reduced.

Sets a to b + cd modulo n. The sum is computed exactly with fmpz arithmetic and reduced once, so b, c and d may be any integers.

Returns 1 if \gcd(a, n) = 1, that is, if a is invertible modulo n, and 0 otherwise. Works for any integer a.

Sets a to b^{-1} modulo n, for canonical b. Throws an exception (FLINT_IMPINV) if b is not invertible; test first with fmpz_mod_is_invertible when this is possible.

If the congruence ac \equiv b \pmod n has a solution, sets a to one solution in [0, n) and returns 1; otherwise returns 0 and leaves a undefined. b and c must be canonical.

Sets a to b^e modulo n, for canonical b. 0^0 = 1.

Sets a to b^e modulo n and returns 1, for canonical b and any integer e. If e < 0 and b is not invertible, returns 0 and leaves a undefined.

Sets a to a uniformly random residue in [0, n).

Sets a to a random nonzero residue: it draws up to three uniformly random residues and returns the first nonzero one, or 1 if all three are zero. (For n = 1 there is no nonzero residue, and the result is the non-canonical value 1.)

Initialise L, which is not ready for computation until fmpz_mod_discrete_log_pohlig_hellman_precompute_prime is called, and free the memory used by L.

Configures L for logarithms modulo p to the base of the least primitive root modulo p, and returns an estimate of the number of multiplications modulo p that one call of fmpz_mod_discrete_log_pohlig_hellman_run needs. p must be prime, which is not checked.

Returns a pointer to the primitive root \alpha used as the base of the logarithms.

Sets x to the logarithm of y to the base \alpha, the integer x \in [0, p - 1) with \alpha^x \equiv y \pmod p. y must be reduced modulo p and nonzero (not checked); if no logarithm is found, which can only happen for invalid input, an exception is thrown.

Sets a to a prime p > b for which p - 1 is smooth and returns 1, or sets a to 0 and returns 0 if there is none. Such primes are suitable for fmpz_mod_discrete_log_pohlig_hellman_precompute_prime.

For n < 2^{\mathtt{FLINT\_BITS}}, with nmod_add, nmod_sub and nmod_mul and the nmod_t stored in the context.

For n = 2^{\mathtt{FLINT\_BITS}}, with wrapping word arithmetic.

For 2^{\mathtt{FLINT\_BITS}} < n < 2^{2\mathtt{FLINT\_BITS}}, with two- and three-limb arithmetic; _fmpz_mod_mul2 is the Barrett reduction of Two-limb Barrett reduction in fmpz_mod.

For any modulus, with fmpz arithmetic; _fmpz_mod_mulN reduces with fmpz_mod, or with fmpz_fdiv_r_preinvn when the context has a precomputed inverse.