fq_nmod.h

Initialises ctx as a context for \mathbb{F}_{p^d}, p = prime, d = deg \ge 1, with the generator printed as var. The defining polynomial is the Conway polynomial if (p, d) is in FLINT's table, and otherwise a polynomial with the least possible number of nonzero terms (nmod_poly_minimal_irreducible).

Initialise ctx with the Conway polynomial for (p, d). The first function throws FLINT_ERROR if the polynomial is not in FLINT's table; the second returns 0 in that case (leaving ctx uninitialised) and 1 on success, and does not set the flag is_conway.

Initialises ctx with a monic irreducible polynomial of degree d with the least possible number of nonzero terms, as computed by nmod_poly_minimal_irreducible: a binomial x^d + a if one exists, otherwise a trinomial, tetranomial or pentanomial, the smallest in a fixed order. The polynomial is deterministic but in general not primitive.

Initialises ctx as a context for \mathbb{F}_p[x]/(f), where f is modulus, an irreducible polynomial of degree d \ge 1 over \mathbb{F}_p and p is its modulus. f need not be monic and is copied. Irreducibility is not checked.

Deprecated versions of fq_nmod_ctx_init_ui, fq_nmod_ctx_init_conway_ui and _fq_nmod_ctx_init_conway_ui taking the prime as an fmpz_t, which must fit in a word.

Initialises ctx as a random field for testing, defined by a Conway polynomial, multiplied by a random nonzero constant with probability 1/2 (to test non-monic moduli). The prime and degree are chosen by _nmod_poly_conway_rand according to type as for fq_ctx_init_randtest.

Initialises ctx with a random monic modulus that is usually reducible, for testing: primes of up to 20 bits for type 0 and 1, of up to 10 bits for 2 and 3, degrees up to 30 for even and up to 15 for odd type.

Frees the memory used by ctx.

Returns a pointer to the defining polynomial.

Returns the degree d.

Returns the characteristic p.

Sets f to q = p^d.

Print p, d and the defining polynomial to file, respectively stdout, as fq_ctx_fprint.

Initialise rop as zero; fq_nmod_init2 allocates space for d coefficients. The context is needed for the modulus p.

Frees the memory used by rop.

Copy, swap, and set to 0, 1 or the generator (the class of x, or the root of the defining polynomial if d = 1), as fq_set, fq_swap, fq_zero, fq_one and fq_gen.

Set rop to the image of the integer x in \mathbb{F}_p.

If b lies in \mathbb{F}_p, sets a to its representative in [0, p) and returns 1; otherwise returns 0.

Convert between an element and its representative in \mathbb{F}_p[x]. fq_nmod_get_nmod_poly also sets the modulus of a to p. fq_nmod_set_nmod_poly reduces a polynomial of any length modulo the defining polynomial; its modulus must be p.

Convert between a and the d \times 1 column vector of its coefficients, as fq_get_fmpz_mod_mat and fq_set_fmpz_mod_mat.

Return whether op1 equals op2, whether op is 0, respectively 1.

Compares the representatives of a and b and returns -1, 0 or 1: a shorter representative is smaller, and representatives of the same length are compared coefficientwise from the constant term up. This is a total order for sorting, unrelated to the field structure.

Return whether op is invertible; the second version also sets rop to a nontrivial factor of a reducible modulus, as fq_is_invertible_f.

Set rop to \mathit{op1} + \mathit{op2}, \mathit{op1} - \mathit{op2}, \mathit{op1} - 1, respectively -\mathit{op1}.

Set rop to \mathit{op1} \cdot \mathit{op2}, respectively \mathit{op}^2, with nmod_poly_mul followed by fq_nmod_reduce.

Set rop to op times the image of the integer x in \mathbb{F}_p.

Set rop to \mathit{op1}^{-1}, respectively \mathit{op1} / \mathit{op2}. Throw FLINT_ERROR on division by zero.

Sets rop to the monic GCD of the representative of op and the modulus and inv to the corresponding inverse, as fq_gcdinv.

Set rop to \mathit{op1}^e for e \ge 0 (with \mathit{op1}^0 = 1); fq_nmod_pow throws FLINT_ERROR for e < 0 and reduces e modulo q - 1 when e \ge p.

Sets (rop, 2d - 1) to (op, len) raised to the power e \ge 0, reduced (the result in the first d coefficients), as _fq_pow. Requires 1 \le \mathit{len} \le d and no aliasing.

Square root (returning 0 if op is not a square), squareness test and p-th root, as fq_sqrt, fq_is_square and fq_pth_root.

Set rop to \mathit{op}^{p^e}, as fq_frobenius and _fq_frobenius (the underscore version requires 1 \le \mathit{len} \le d, 1 \le e < d and space for 2d - 1 coefficients).

Set rop to the norm, respectively the trace, of the element, an integer in [0, p), computed by a resultant, respectively from the traces of the powers of the generator, as fq_norm and fq_trace. The underscore versions require a nonzero element with 1 \le \mathit{len} \le d.

Multiplicative order (returning 0 for zero, 1 for a primitive element and -1 otherwise) and primitivity test, as fq_multiplicative_order and fq_is_primitive.

Uniformly random elements (rand), random elements for testing (randtest, often sparse) and random elements with a monic representative of degree d - 1 (randtest_dense), as for fq.

Print the representative of op in the format of nmod_poly_fprint: the length, the modulus p, and the coefficients from the constant term up.

Print the representative as a polynomial in the variable name of the context, such as 3*a^2+1.

Return the plain, respectively readable, representation as a newly allocated string, to be freed with flint_free.

Pack the coefficients of op into bit_size-bit fields of an integer, and unpack and reduce, as fq_bit_pack and fq_bit_unpack.

Reduces the polynomial rop, of length at most 2d with reduced coefficients, modulo the defining polynomial, in place. Longer inputs are only allowed for a sparse defining polynomial (they trigger an assertion failure in debug builds and give wrong results otherwise); fq_nmod_set_nmod_poly reduces polynomials of any length.

Reduce (R, lenR), with coefficients in [0, p) and \mathit{lenR} \le 2d (any length for the sparse version), modulo the defining polynomial in place, leaving the result in the first d coefficients. _fq_nmod_sparse_reduce eliminates the high coefficients with the nonzero terms of f, with special code for p = 2 (exclusive or), for moduli whose nonzero coefficients are all 1 (subtractions only), and for p < 2^{\mathtt{FLINT\_BITS}/2} (Barrett reduction of a single-word product); _fq_nmod_dense_reduce uses Newton division with the precomputed inverse. _fq_nmod_reduce chooses the sparse version if f has at most five nonzero terms. See Reduction modulo the defining polynomial.