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.